CSE 101 Final Exam Page 1 of 21
1. Analyzing algorithms [18 points]
1.a. [13 points] Write McNaughton’s algorithm to solve the problem P | pmtn | Cmax in Pseudocode.
Input: n jobs J1, . . . , Jn with processing times p1, …, pn and the number m of processors.
Solution:
CSE 101 Final Exam Page 2 of 21
1.b. [5 points] Analyze the running time of the algorithm by giving both the best-case and worst-case
time. Are the bounds tight?
Solution:
CSE 101 Final Exam Page 3 of 21
2. Knapsack problem [15 points]
A set of items each with a value and a weight is given in the following table. The capacity of the knapsack
is 11.
A B C D
values 21 20 16 30
weights 3 4 2 5
relative values 7 5 8 6
2.a. [3 points] Apply the largest-relative-value heuristic to this instance to find a feasible solution.
Solution:
2.b. [12 points] Solve the problem with Branch-and-Bound. Use the solution value of 2.a. as the first
Lower Bound LB1. Selection Rule: Take at first that object with the largest value. Graph Traversal:
Best-First-Search (best=largest upper bound). Use relative values to calculate Upper Bounds and Lower
Bounds within a vertex. You can cross out a vertex when the capacity is reached (that comes out of the
Lower Bound – computation) or if an Upper Bound is <= to a Lower Bound.
Solution:
CSE 101 Final Exam Page 4 of 21
3. Bin Packing [15 points]
Nine books with given thickness (in cm) have to be stacked on shelves. Each shelf has a width of 10 cm.
book 1 2 3 4 5 6 7 8 9
thickness 3 4 6.5 3.5 4 7 1 1.5 5
3.a. [5 points] Apply the First-Fit-Decreasing-algorithm to the given problem instance.
Solution:
3.b. [10 points] Provide Pseudocode for the First-Fit-Decreasing-algorithm.
Solution:
CSE 101 Final Exam Page 5 of 21
4. Scheduling [14 points]
4.a. [9 points] A student from the CSE department has a busy schedule and hastily agreed to perform
the following tasks until certain deadlines. Now, he can see that he won’t be able to process all the tasks
until their given deadlines. Instead, he wants to come up with a schedule that maximizes the number
of tasks that can be completed until their deadlines. What algorithm should the student choose?
Execute this algorithm on the given problem instance.
A B C D E F G H
durations 4 1 2 3 16 7 14 9
deadlines 4 5 6 15 17 20 21 25
Solution:
CSE 101 Final Exam Page 6 of 21
4.b. [5 points] Jobs A,B,C, . . . , H with corresponding processing times 5, 3, 8, 2, 7, 10, 1, 15 have to be
scheduled without preemptions on three parallel and identical processors. Draw the optimal schedule
in the given Gantt-Chart.
Solution:
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
P3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
CSE 101 Final Exam Page 7 of 21
5. Graph Algorithms [24 points]
5.a. [8 points] Find the BFS ordering of the following graph starting at vertex A. Use the solution tree
as we did in the class.
A E K G
C
F
D
M
J
N
H
I
B
L
Solution:
CSE 101 Final Exam Page 8 of 21
5.b. [8 points] Find the Topological Sorting of the following graph and use the solution method (Tarjan’s
algorithm) that we used in the class.
A B C
DEF
G
1 5
3
6
-10
9
6
8
9 1
-6
Solution:
CSE 101 Final Exam Page 9 of 21
5.c. [8 points] Find the single-source-shortest-paths starting at vertex A to all other vertices of the fol-
lowing graph. Use Bellman’s algorithm and use the solution-tree as we did in the class.
A B C
DEF
G
1 5
3
6
-10
9
6
8
9 1
-6
Solution:
CSE 101 Final Exam Page 10 of 21
6. Linear Programming [22 points]
Two goods A and B have to be produced with limited resources R1 and R2. Each unit of good A requires
15 units of resource R1 and 10 units of resource R2. Each unit of good B requires 10 units of resource
R1 and 15 units of resource R2. There are 30 units of resource R1 and 30 units of resource R2 available.
Profits for A and B are 10 dollars for each unit. What is the number of units of goods A and B that have
to be produced in order to maximize the total profit?
6.a. [4 points] Formulate the mathematical program.
Solution:
6.b. [6 points] Solve the problem graphically.
Solution:
CSE 101 Final Exam Page 11 of 21
6.c. [6 points] How do you choose the Pivot-Element in the Simplex Algorithm? When does the Simplex
Algorithm terminate?
Solution:
6.d. [6 points] Give an interpretation of the optimal Simplex table:
A B R1 R2
B 0 1 3
5
−2
5
6
A 1 0 −2
5
3
5
6
0 0 2 2 120
a. What is the optimal production program?
b. What is the optimal total value?
c. How would the production program and the profit change if there would be one more unit of resource
R1 available?
Solution:
CSE 101 Final Exam Page 12 of 21
7. Algorithms and Proofs [32 points]
7.a. [8 points] There are n jobs J1, . . . , Jn with processing times p1, . . . , pn and m processors. The com-
pletion time of the solution given by the LPT algorithm is CLPTmax and the optimal solution that minimizes
the maximum completion time is C∗max. Let Jk with processing time pk be that job that determines the
maximum completion time of LPT. Prove the following inequality:
CLPTmax ≤ C
∗
max + pk
(
1−
1
m
)
Solution:
CSE 101 Final Exam Page 13 of 21
7.b. [8 points] Consider the problem of scheduling n jobs J1, . . . , Jn on one processor with processing
times pj and deadlines dj. Prove why in Moore’s algorithm it is always optimal to move - among those
jobs that come until the first job has a delay - the job with the largest processing time to the end.
Solution:
CSE 101 Final Exam Page 14 of 21
7.c. [8 points] Provide arguments that you can use in a proof i) why Dijkstra’s algorithm is optimal for
SSSP and ii) why Bellman’s algorithm is optimal for SSSP.
Solution:
CSE 101 Final Exam Page 15 of 21
7.d. [8 points] The Subset Sum-problem is the following problem: Does there exist a subset of positive
integers {a1, . . . , an} such that the sum of the subset equals a given positive integer k? Given Subset Sum
is NP-complete, provide a polynomial time reduction to prove that the decision version of Bin Packing
(does there exist an assignment of the items with weights {w1, . . . , wn} into bins of capacity C such that
the total number of bins used is less or equal to a given number k?) is NP-complete. Prove that this
reduction is valid.
Solution:
CSE 101 Final Exam Page 16 of 21
8. Dynamic Programming [20 points]
Consider a row of n coins of values v1, . . . , vn, where n is even. We play a game against an opponent
by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it
from the row permanently, and receives the value of the coin. Determine the maximum possible amount
of money we can definitely win if we move first.
a. Provide a high-level description of your algorithm.
b. Provide a time analysis of your algorithm.
Solution:
CSE 101 Final Exam Page 17 of 21
Solution:
CSE 101 Final Exam Page 18 of 21
9. Graph algorithms [20 points]
You are new to college and are overwhelmed by the number of available courses. You want to do all the
courses of computer science but you can’t decide how should you go about it because every courses has
pre-requisite courses. You decide to write a program to help you decide the order of the courses. There
are a total of n courses, and you are given pair of prerequisite courses in form of (a, b) where a is required
to take b. There may be multiple correct orders but you have to find out only one possible order.
a. Provide a high-level description of your algorithm.
b. Provide a time analysis of your algorithm.
Solution:
CSE 101 Final Exam Page 19 of 21
Solution:
CSE 101 Final Exam Page 20 of 21
10. Independent Set [20 points]
In an unweighted undirected graph, an independent set is a subset of nodes that have no edge between
any pair of them. The Independent-Set-Problem is the problem of finding the largest independent set in
a given graph. Consider solving this problem with Branch and Bound.
a. Come up with a heuristic that gives a feasible solution. Would this solution serve as a first Upper
Bound or a first Lower Bound in the Branch and Bound setting?
b. How to solve this problem with Complete Enumeration?
c. What would be an Upper Bound and a Lower Bound at each vertex of the Complete Enumeration?
These two bounds help us formulate the Branch and Bound algorithm to solve the problem without
unnecessary branchings of the original Complete Enumeration algorithm.
Solution:
CSE 101 Final Exam Page 21 of 21
Solution: