CSE 317: Design and Analysis of Algorithms
Sample Questions: Final
1. Consider the following algorithm divide:
Algorithm: divide
Input: y, z ∈ N
Output: The product q, r ∈ N s.t., y = qz + r
1. r ← y, q ← 0, w ← z
2. while w ≤ y
3. w ← 2w
4. while w > z
5. q ← 2q, w ← ⌊w/2⌋
6. if w ≤ r then
7. r ← r − w, q ← q + 1
8. return (q, r)
(a) Trace the steps of the algorithm for: divide(10, 3).
(b) Prove that this algorithm is correct.
(c) Express the time complexity of this algorithm in O-notations.
2. Let A[1 . . . n] be an array of n elements. An element x is called a majority element if it
occurs at least ⌈n/2⌉ times in A. Assume that a majority element is guaranteed to exist.
(a) Design a Monte Carlo randomized algorithm that outputs a majority element of A.
(b) Prove that your algorithm outputs the correct answer with probability at least 1 − 1/n.
(c) Analyze the expected running time of your algorithm.
You may assume that equality comparisons between array elements take constant time.
3. Show following problems are in NP.
(a) Dominating set problem: Given an undirected graph G = (V, E), a subset of
vertices D ⊆ V is called a dominating set if for every vertex u ∈ V \ D, there is a
vertex v ∈ D such that {u, v} ∈ E.
Question: Given an undirected graph G and an integer k, does G contain a dominating
set of size at most k?
(b) Hamiltonian path problem: Given an undirected graph G = (V, E), a path in G
that visits each vertex v ∈ V exactly once is called Hamiltonian path.
Question: Given an undirected graph G, does G contain a Hamiltonian path?
4. Let A be an array of n elements such that only log2 n elements in A are unique. For example,
if A = ⟨9, 0, 0, 9, 1, 0, 1, 9⟩ then |A| = 8 however only log2 8 = 3 elements in A are unique
i.e., 0, 1, 9.
Solve following questions to sort A in ascending order.
(a) Design an O(n log n) algorithm to sort A.
(b) Design an O(n log log n) algorithm to sort A.
(c) Design an O(n) algorithm to sort A.
5. (10 points) You are given an integer array nums = ⟨a1 , a2 , . . . , an ⟩ of n non-negative in-
tegers, where each element ai represents the maximum jump length from position i. You
start at the first index of the array, and your goal is to reach the last index in the minimum
possible number of jumps.
Design a dynamic programming algorithm to compute the minimum number of jumps re-
quired to reach the last index. If it is not possible to reach the last index, your algorithm
should return −1.
Example 1:
Input: ⟨2, 3, 1, 1, 4⟩, Output: 2
Explanation: Jump one step from index 1 to index 2, then three steps to the last index.
Example 2:
Input: ⟨3, 2, 1, 0, 4⟩, Output: −1
Explanation: You will always get stuck at index 4, whose maximum jump length is 0,
making it impossible to reach the last index.
6. Given a sequence of numbers a1 , a2 , . . . , an , n ≥ 3 of distinct integers, a triplet ai , aj , ak is
called a strange triplet if ai > aj > ak whenever i < j < k. Compute the average number
of strange triplets in any given sequence of unique numbers uniformly drawn from the set
of integers.
7. Consider following randomized strategy to check if the given input number q is prime?
Algorithm: prime
Input: A positive integer N ≥ 2
Output: true if N is prime, false otherwise with some error probability p
√ √
1. a ← random-prime( N ) // a is random prime betwen 2 and N
√ √
2. b ← random-prime( N ) // b is random prime betwen 2 and N
3. if ab = N then return true
4. else return false
Find the probability of error in the above algorithm.
8. Let G = (V, E) be a directed acyclic graph and s and t be two vertices in G. Design a
dynamic programming algorithm compute the number of all directed paths between s and
t.
9. Let G = (V, E) be a directed acyclic graph, a vertex s ∈ V is called a universal sink without
any outgoing edges such that every other vertex u ∈ V has a directed path to v. Design an
efficient algorithm find a universal sink vertex in any given DAG.
10. IBA is planning to build a new campus with n buildings labeled as 1, . . . , n. There will be
n − 1 two-way streets in this new campus.
A street si = (ai , bi ) connects buildings ai and bi where 1 ≤ ai < bi ≤ n and 1 ≤ i ≤ n − 1.
We know that starting from any building we can reach any other building walking through
the campus streets. Setting up a lamp in front of a building lights all the streets adjacent
to it. Design an O(n) dynamic programming algorithm to find the minimum number of
lamps required to light all the campus streets.
Page 2