Spring 2023
CSE 317: Design and Analysis of Algorithms
Instructions, topics, and practice questions for the Final Exam [All sections]
1 Instructions
1. PLEASE READ THESE INSTRUCTIONS CAREFULLY.
2. Use of calculators, mobile, or any other communication devices is strictly prohibited for
the entirety of the exam period.
3. Please submit your devices in your bag at the front of the examination room.
4. You may keep writing material with you on your desk.
5. Read all questions carefully before you start answering.
6. Prioritize which questions to attempt first.
7. You may ask for extra sheets for your rough work, scribbling, future planning etc., any-
thing on extra sheet(s) will not be graded.
8. Do as many questions as you can in the given time.
9. Please write your name and student ID on this question paper clearly.
10. Please do not use pencils or red/green/yellow pens for answers that you want to be graded.
11. Please write your answers in the provided space, anything on the extra sheet(s) will not
be graded.
12. Instructors will not entertain any queries during the exam.
13. Please attach all extra sheets with your answer book.
14. Please write clearly and legibly and avoid overwriting.
15. When writing an algorithm, a clear description in English will suffice. Pseudocode is not
required. Be sure to argue that your algorithm is correct (a formal proof is not needed),
and analyze the asymptotic running time of your algorithm. Even if your algorithm does
not meet a requested bound, you may receive partial credit for inefficient solutions that
are correct.
16. Pay attention to the instructions for each question.
17. Acquisition of answers through unfair means will automatically cancel your exam.
18. Keep track of the time.
19. Your answer(s) will not be graded if unreadable (by the instructors).
20. Your exam will not be graded if you don’t follow these instructions.
2 Topics
For the final exam following topics are included:
1. Asymptotic Notations
2. Recurrences
3. Divide and Conquer Algorithms
4. Greedy Algorithms
5. Dynamic Programming
6. Randomized Algorithms
7. Computational Complexity
Please note that our emphasis will be mostly on the topics covered after the midterm exam
however you are expected to know the topics covered before the midterm exam as well.
3 Practice Questions
Following are some practice questions.
Page 2
1. [Analysis of Randomized Binary Search.] Consider a variation of binary search al-
gorithm in which instead of choosing the middle value in the current search window [l, r],
the algorithm select an element uniformly at random in each iteration. (i.e., instead of
m = (l + r)/2, we choose m uniformly at random from [l, r]). Given that the probability of
i-th value being selected as m during an execution of the algorithm is 1/|j − i + 1|, where
j is the index of target value, find the expected number of comparisons that the algorithm
makes in the worst case.
[Hint: Express the number of comparisons as the sum of indicator random variables.]
Page 3
2. Prove following problems NP.
(a) subset-sum: Given P a set of integers S and an integer t, does there exist a subset
S ′ ⊆ S such that x∈S ′ x = t?
P
(b) 2-partition: Given a set of integers S such that P |S| = n andP x∈S x = 2B, can S be
partitioned into two subsets S1 and S2 such that x∈S1 x = x∈S2 x = B?
P
(c) 3-partition: Given a set of integers S such that |S| P = 3n and x∈S x = 3B, can S
be partitioned into n subsets S1 , S2 , . . . , Sn such that x∈Si x = B for all i?
(d) 3-dimensional-matching: Given three disjoint sets X, Y , and Z, each of size n, and
a set T ⊆ X × Y × Z, is there a subset T ′ ⊆ T such that |T ′ | = n and no two elements
of T ′ agree in any coordinate?
(e) vertex-cover: Given a graph G = (V, E) and an integer k, is there a subset V ′ ⊆ V
such that |V ′ | ≤ k and every edge in E is incident on at least one vertex in V ′ ?
(f) hamiltoniancycle: Given an undirected graph G = (V, E), the hamiltonian cycle
problem asks whether there is a cycle that visits every vertex exactly once.
Page 4
3. Consider the following algorithm that takes as input a positive integer n and outputs a
random prime number in the range [2, n]. Compute the expected running time of this
algorithm.
Algorithm: random-prime
Input: A positive integer n ≥ 2.
Output: A random prime number in the range [2, n].
1. Let P = {2, 3, 5, 7, 11, . . .} // P is the set of all prime numbers
2. Let S = {2, 3, 4, . . . , n}.
3. while S ̸= ∅
4. x = random(S) // pick a random element x from S
5. if x ∈ P then return x
6. else remove x from S
7. return“failure”.
Page 5
4. Let A[1..n] be an array of n distinct positive numbers and k ≤ n be some positive integer.
Give a randomized algorithm that return a random sample of k elements from A. The
algorithm should run in O(n) time. Prove that your algorithm is correct and analyze its
running time.
Page 6
5. Let A[1..n] be an array of n numbers such that not all numbers are unique. We say that A[i]
is a majority element if it occurs at least ⌈n/2⌉ times in A. Give a Monte Carlo randomized
algorithm that finds a majority element in A. Prove that your algorithm is correct and
analyze its running time.
Page 7
6. Let A[1..n1 ], B[1..n2 ], and C[1..n3 ] be three arrays of numbers of sizes n1 , n2 , and n3 ,
respectively. All these arrays are sorted in ascending order and individually they contain
unique elements, however they may share elements with other arrays i.e., intersection of
any of these two arrays may not be empty. Give a greedy algorithm that merges these three
arrays in descending order such that it minimizes the total number of comparisons required
to merge. Prove that your algorithm is correct and analyze its running time.
[Fact: You may use the merge algorithm from the mergesort that merges two sorted
arrays of sizes m and n and uses m + n − 1 comparisons.]
Page 8
7. Apply Prim’s algorithm on the following graph starting from vertex a and show the order
in which the edges are added to the minimum spanning tree. Also show the total weight of
the minimum spanning tree.
a
7
8
5 b c
7
9 5
15
d e
6 9
8
11
f g
Page 9
8. Let G = (V, E) be a directed graph with n vertices and m edges. Let s be a vertex in V and
w : E → R be a weight function on the edges. Let d[v] be the length of the shortest path
from s to v for all v ∈ V . Let d[v] = ∞ if there is no path from s to v. Let d[s] = 0. Let
p[v] be the predecessor of v in the shortest path from s to v for all v ∈ V . Let p[v] = “NIL”
if there is no path from s to v. Let p[s] = “NIL”. Let Q be a priority queue that stores the
vertices of V and supports the following operations:
• insert(Q, v): Inserts vertex v into Q.
• decrease-key(Q, v, k): Decreases the key of vertex v to k.
• extract-min(Q): Removes and returns the vertex with the minimum key from Q.
• empty(Q): Returns “true” if Q is empty, otherwise returns “false”.
• contains(Q, v): Returns “true” if Q contains vertex v, otherwise returns “false”.
• size(Q): Returns the number of vertices in Q.
• keys(Q): Returns the keys of all vertices in Q.
• vertices(Q): Returns all vertices in Q.
• build-heap(Q): Builds a heap from the vertices in Q.
• heapify(Q, i): Heapifies the subtree rooted at index i.
• parent(i): Returns the index of the parent of the vertex at index i.
• left(i): Returns the index of the left child of the vertex at index i.
• right(i): Returns the index of the right child of the vertex at index i.
• swap(Q, i, j): Swaps the vertices at indices i and j.
Give an algorithm that computes d[v] and p[v] for all v ∈ V using the above operations.
Prove that your algorithm is correct and analyze its running time.
Page 10