CSE 101 Midterm Exam Page 1 of 12
1. Analyzing algorithms [23 points]
Consider the following procedure whose input is a positive integer n:
procedure Operation(n: a positive integer)
1. R := 1
2. for (k := 1; k <= n− 1; k + +)
3. R := R + 2 ∗ k + 1;
4. return R;
1.a. [10 points] Consider the inputs n = 2, 3, 6 to the above algorithm. What does the algorithm return?
Explain with your own words the purpose of the algorithm.
CSE 101 Midterm Exam Page 2 of 12
The pseudocode is reproduced again for convenience:
procedure Operation(n: a positive integer)
1. R := 1
2. for (k := 1; k <= n− 1; k + +)
3. R := R + 2 ∗ k + 1;
4. return R;
1.b. [8 points] Prove the Correctness of the algorithm. Make sure to clearly state the loop invariant.
Include the appropriate diagrams if necessary.
CSE 101 Midterm Exam Page 3 of 12
The pseudocode is reproduced again for convenience:
procedure Operation(n: a positive integer)
1. R := 1
2. for (k := 1; k <= n− 1; k + +)
3. R := R + 2 ∗ k + 1;
4. return R;
1.c. [5 points] Give a time analysis of the algorithm. Find both a lower bound AND an upper bound
for the asymptotic running time, and show that the bounds are tight. You may use that the arithmetic
operations take constant time.
CSE 101 Midterm Exam Page 4 of 12
2. Assignment Problem [20 points]
There are 4 employees (A, B, C, D) and 4 tasks to be done (1, 2, 3, 4). Each employee is different and
takes different time to complete a task. Each employee can only do one task, and each employee should
get 1 task. Assign tasks to employees such that the total amount of time required to complete the work is
minimal.
T1 T2 T3 T4
A 8 6 17 9
B 3 8 5 6
C 10 12 11 9
D 6 13 8 7
2.a. [4 points] Compute a feasible solution with ”Smallest-Number-Heuristic”.
CSE 101 Midterm Exam Page 5 of 12
2.b. [14 points] Solve the problem with Branch-and-Bound :
1.Use the solution value of 2.a. as the first Upper Bound UB1.
2.Use the ”Row-min-strategy” and always continue at that vertex with the smallest lower bound.
3.Number the vertices in the order they are constructed.
4.You can cross out a vertex when all assignments are done (that comes out of the Upper Bound
calculation) or if a Lower Bound is >= to an Upper Bound.
CSE 101 Midterm Exam Page 6 of 12
2.c. [2 points] How many vertices do you not have to compute when you use Branch-And-Bound instead
of Complete Enumeration (for this problem instance)?”
CSE 101 Midterm Exam Page 7 of 12
3. 0-1 Knapsack [22 points]
You are going on a vacation to Hawaii and you are only going to carry one bag which has a capacity of
25 lbs. You also have various items you want to take with you, unfortunately you can’t take everything.
You have marked every item with a value and it’s weight. Now, it’s your job to maximize the value of the
items packed without exceeding the weight.
A B C
Values 50 30 60
Weights(lbs) 10 5 15
relative values
3.a. [3 points] Apply the largest-relative-value heuristic to this instance to find a feasible solution.
CSE 101 Midterm Exam Page 8 of 12
3.b. [9 points] Use Complete Enumeration to solve this problem instance. Build the full binary tree.
CSE 101 Midterm Exam Page 9 of 12
3.c. [8 points] Solve the problem with Branch-and-Bound :
1.Use the solution value of 3.a. as the first Lower Bound LB1.
2.Selection Rule: Take at first that object with the largest value.
3.Graph Traversal: Best-First-Search (best=largest upper bound).
4.Number the vertices in the order they are constructed.
5.Use relative values to calculate Upper Bounds and Lower Bounds within a vertex.
6.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.
CSE 101 Midterm Exam Page 10 of 12
3.d. [2 points] How many vertices do you not have to compute when you use Branch-And-Bound instead
of Complete Enumeration (for this problem instance)?”
CSE 101 Midterm Exam Page 11 of 12
4. Theoretical Questions [15 points]
3 points:What is the best, worst and average running time complexity of Min Sort?
2 points:What are the number of comparisons and swaps of Insertion Sort in the best case and in the worst
case?
5 points:If we modify the partitioning algorithm of Quicksort and use the median of the list as the pivot, what
will be the best and worst case running time of Quicksort using our modified partitioning? Assume
that the median of a list can be computed in O(n).
5 points:Explain Branch-and-bound: Use the terms Optimization, Minimization, Maximization, Lower Bounds,
Upper Bounds, cross out a vertex. Compare Branch-and-bound with Complete enumeration.
CSE 101 Midterm Exam Page 12 of 12
ON THIS PAGE YOU CAN EARN EXTRA POINTS
Bonus.
Given a number n, design an algorithm to print all possible combination of parenthesis where the number
of opening parenthesis is exactly equal to n. For example
�n = 1 : ()
�n = 2 : (()), ()()
�n = 3 : ((())), ()(()), (())(), (()()), ()()()
Provide pseudo code for your algorithm.