CSE 101 Midterm Exam Page 1 of 10
1. Analyzing an algorithm [23 points]
In the following problem, the notation a % b denotes the modulus operator, finding the remainder after
division of a by b. If a % b = 0, then we say that b divides a.
Consider the following procedure:
procedure myProcedure(A = (a1, . . . , an), D = (d1, . . . , dn): lists of n distinct positive integers, n ≥ 1)
1. count = 0
2. for (i = 1; i ≤ n; i++)
3. j = 1
4. found = False
5. while (j ≤ n and not found)
6. if (ai % dj == 0)
7. count++
8. found = True
9. j++
10. return count
1.a. [8 points]
i. [3 points] Consider the input A = (25, 32, 13, 77, 19), D = (2, 3, 5, 7, 11) to the above algorithm.
What does the algorithm return?
myProcedure((25, 32, 13, 77, 19), (2, 3, 5, 7, 11)) =
ii. [5 points] Explain with your own words the general purpose of the algorithm.
CSE 101 Midterm Exam Page 2 of 10
The pseudocode is reproduced again for convenience:
procedure myProcedure(A = (a1, . . . , an), D = (d1, . . . , dn): lists of n distinct positive integers, n ≥ 1)
1. count = 0
2. for (i = 1; i ≤ n; i++)
3. j = 1
4. found = False
5. while (j ≤ n and not found)
6. if (ai % dj == 0)
7. count++
8. found = True
9. j++
10. return count
1.b. [10 points] Prove that the algorithm is correct. Clearly state your Induction Hypothesis and
where it is used in your Induction Step.
CSE 101 Midterm Exam Page 3 of 10
The pseudocode is reproduced again for convenience:
procedure myProcedure(A = (a1, . . . , an), D = (d1, . . . , dn): lists of n distinct positive integers, n ≥ 1)
1. count = 0
2. for (i = 1; i ≤ n; i++)
3. j = 1
4. found = False
5. while (j ≤ n and not found)
6. if (ai % dj == 0)
7. count++
8. found = True
9. j++
10. return count
1.c. [5 points] Analyze the Running Time of the algorithm (in terms of number of comparisons):
i. [3 points] What is the least upper bound for the runtime of myProcedure? Prove your claim.
ii. [2 points] What is the greatest lower bound for the runtime of myProcedure? Prove your claim.
CSE 101 Midterm Exam Page 4 of 10
2. Assignment Problem [20 points]
There are 4 employees (A,B,C,D) and 4 tasks to be done (T1, T2, T3, T4). Each employee takes a certain
amount of time to complete a task. Each employee can only do one task, and each employee should get 1
task.
Our goal in this problem is to assign these tasks to the employees such that the total amount of time
required to complete the work is minimal.
T1 T2 T3 T4
A 7 9 8 2
B 3 6 7 4
C 1 5 8 8
D 9 7 4 6
2.a. [4 points] Compute a feasible solution with Smallest-Number-Heuristic. Box your final answer.
2.b. [2 points] If you were to solve this problem instance using Complete Enumeration, how many
vertices would be calculated? Box your final answer.
CSE 101 Midterm Exam Page 5 of 10
2.c. [14 points] Solve the problem with Branch-and-Bound : Use the solution value of the Smallest-
Number-Heuristic as the first Best Upper Bound, UB1.
i. Branch: Level = Agent, and continue always at that vertex with the smallest Lower Bound.
ii. Lower Bound: Use the Row-Min-Strategy. If this is ≥ the current Best Upper Bound, cross out this
vertex; otherwise, proceed.
iii. Upper Bound: Use the Smallest-Number-Heuristic. If this is < the Best Upper Bound, set this as the newest Best Upper Bound and immediately cross out any open vertices with a Lower Bound ≥ this new Best Upper Bound. iv. Crossing out a vertex: all assignments are done or its Upper Bound is ≤ its Lower Bound. v. Number each vertex in the order they are constructed. Box and clearly number each vertex, and indicate its Lower Bound, and (if calculated), its Upper Bound. CSE 101 Midterm Exam Page 6 of 10 3. Scheduling [22 points] You’ve been given n = 8 tasks, each with the following processing times and deadlines: A B C D E F G H pj (processing times) 1 2 3 4 7 9 14 16 dj (deadlines) 5 6 15 4 20 25 21 17 It’s clear that you won’t be able to complete all of the tasks before their deadlines, so you have to create a schedule for completing the tasks. 3.a. [10 points] First, you decide that you want to come up with a schedule that minimizes the maximum lateness. i. What algorithm should you choose to find the optimal scheduling? ii. Execute the algorithm you chose on the given problem instance. pj dj Cj Lj Maximum Lateness = CSE 101 Midterm Exam Page 7 of 10 3.b. [12 points] You then change your mind and decide that you want to come up with a schedule that mimimizes the number of delayed tasks. i. What algorithm should you choose to find the optimal scheduling? ii. Execute the algorithm you chose on the given problem instance. pj dj Cj Lj Number of delayed tasks = CSE 101 Midterm Exam Page 8 of 10 4. Theoretical Questions [15 points] 4.a. [3 points] Analyze the running time of Bubble Sort (in terms of number of comparisons): i What is the least upper bound for the runtime of Bubble Sort? Prove your claim. i What is the greatest lower bound for the runtime of Bubble Sort? Prove your claim. 4.b. [3 points] Analyze the running time of Binary Search (in terms of number of comparisons): i What is the least upper bound for the runtime of Binary Search? Prove your claim. i What is the greatest lower bound for the runtime of Binary Search? Prove your claim. CSE 101 Midterm Exam Page 9 of 10 4.c. [3 points] Is it possible for Ω(1), Ω(log n) and Ω(n) to all be bounds on the running time of the same algorithm? Explain your answer. 4.d. [6 points] Consider the following algorithm. procedure myProcedure(n: a positive integer) 1. k = 0 2. for i = 1, i ≤ n, i++ 3. for j = 1, i ≤ n, i++ 4. k++ Find an asymptotically tight bound on this algorithm, and justify your answer with mathematical proof. What value will k have after the algorithm terminates? CSE 101 Midterm Exam Page 10 of 10 ON THIS PAGE YOU CAN EARN EXTRA POINTS Bonus. [10 points] Suppose that each person in a group of n people votes for exactly two people from a slate of candidates to fill two positions on a committee (so 2n total votes cast). Of the top two finishers, each candidate wins a position only if they receive more than n/2 votes. Bonus.a. [6 points] Devise a divide-and-conquer algorithm that (1) finds the top two finishers, and (2) determines who (if either of them) wins a position on the committee. Bonus.b. [4 points] Use the Master Theorem to give a big-O estimate for the number of comparisons needed by the algorithm you devised in part (a).