Fall 2024: CSE 317 : Introduction to Algorithms

Sample Questions

Question 1 [10 points]

Let X = ⟨x1 , x2 , . . . , xn ⟩ be a sequence of n integers. We say the sequence S = ⟨s1 , s2 , . . . , sn ⟩
is the sequence of partial sums the sequence X, if:
s 1 = x1
s 2 = x1 + x2 = s 1 + x2
s3 = x1 + x2 + x3 = s2 + x3
..
.
sn = x1 + x2 + · · · + xn = sn−1 + xn
Design a parallel algorithm with n processors to compute partial sums.
Question 2 [5 points]
Design a sequence algorithm for the problem from previous question to computer partial
sums. Also, provide the worst-case running time of your algorithm.
Question 3 [50 points]
Prove following problems to NP-complete. [Note: These are really difficult problems.]
(a) Name: Graph 3-Colorability 3col
Input: An n-node undirected graph G(V, E) with node set V and edge set E.
Question: Can each node of G(V, E) be assigned exactly one of three colors – Red,
Blue, Green – in such a way that no two nodes which are joined by an edge, are assigned
the same color?
(b) Name: Monochromatic triangle mono triangle
Input: An n-node undirected graph G(V, E) with node set V and edge set E.
Question: Can the edges, E, of G be partitioned into two disjoint sets E1 and E2 , in
such a way that neither of the two graphs G1 (V, E1 ) or G2 (V, E2 ) contains a triangle,
i.e. a set of three distinct nodes u, v, w such that {u, v}, {u, w}, {v, w} are all edges?
(c) Name: Multiprocessor Scheduling multiprocessor scheduling
Input: A set, T , of tasks and for each task t in T a positive (integer) running time
len(t). A positive integer D, called the deadline.
Question: Is there a 2-processor schedule for the tasks that completes within the
deadline, D, i.e. is there a function σ : T → N such that both of the following hold:
• For all u ≥ 0 the number of tasks t in T for which σ(t) ≤ u < σ(t) + len(t) is at
most 2.
• For all tasks t, σ(t) + len(t) ≤ 0
(d) Name: Maximum 2-Satisfiability max 2 sat
Input: A set of m clauses C1 , C2 , . . . , Cm over n Boolean valued variables Xn , where
each clause depends on two distinct variables from Xn ; a positive integer k with k ≤ m.
Question: Is there an assignment of Boolean values to the variables Xn such that at
least k distinct clauses take the value true under the assignment?
(e) Name: Shortest Common Superstring shortest common superstring
Input: A finite set R = {r1 , r2 , . . . , rm } of binary strings (sequences of 0 and 1);
positive integer k.
Question: Is there a binary string w of length at most k such that every string in R
is a substring of w, i.e. for each r in R, w can be decomposed as w = w0 rw1 where w0 ,
w1 are (possibly empty) binary strings?
Question 4 [10 points]
Given an array of n elements containing all but one of the integers from 1 to n + 1. Design
an O(n) algorithm to find the missing integer. Assume that the input array is not sorted.
Also, provide the worst-case running time of your algorithm.

Question 5 [10 points]

Divide and conquer is a technique where the input problem is decomposed into subproblems
of smaller sizes recursively and solutions of these subproblems are used to construct a solution
to the main input problem.
(a) (5 points) Explain the difference between dynamic programming and divide and con-
quer technique.
(b) (5 points) The Fibonacci sequence is a famous mathematical sequence. The first and
second Fibonacci numbers are 1 and 1. The n-th Fibonacci number is defined as the
sum of the previous two Fibonacci numbers, where n > 2. Design an O(n) dynamic
programming algorithm to compute the n-th Fibonacci number.

Question 6 [10 points]

Given an array of distinct integers A = ⟨a1 , . . . , an ⟩ where n > 0. A pair of elements (ai , aj )
where i < j and ai > aj is called an inversion.
(a) Design an O(n log n) divide and conquer algorithm that counts the number of inversions
in A.
(b) Analyze the time complexity of your algorithm using the Master Theorem.

Question 7 [10 points]

IBA has a wonderful architecture consisting of many interconnected buildings and pathways
(streets). Suppose the n buildings at IBA are labeled as 1, ..., n and n−1 two-way streets. 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
streets. Setting up a lamp in front of a building lights all the streets adjacent to it. Design
an O(n) dynamic programing algorithm to find the minimum number of lamps required to
light all the streets at IBA.

Question 8 [10 points]

Consider five matrices of following respective sizes:

M1 : 3 × 4, M2 : 4 × 8, M3 : 8 × 2, M4 : 2 × 9.

Use dynamic programing

Q to find the minimum number of scalar multiplications required to
compute the product 4j=1 Mj as well as an optimal parenthesization.

Question 9 [10 points]

Given a directed graph G = (V, E) with n vertices and m edges. Design an O(n + m)
algorithm to find the number of strongly connected components in G. Also, provide the
worst-case running time of your algorithm.

Question 10 [10 points]

Let A = [a1 , a2 , . . . , an ] be an array of n integers and x be an integer. Design an efficient
algorithm to find if for any two elements ai and aj in A such that |ai −aj | = x. Also, provide
the worst-case running time of your algorithm.

Question 11 [10 points]

Let S = {x1 , x2 , . . . , xn } be a set of n positive integers. Design a randomized algorithm
with probability 1 − 1/n that finds an element x ∈ S such that x is the upper half when S
is sorted.

Page 2
Question 12 [10 points]
Let A = ⟨a1 , a2 , . . . , an ⟩ be a sequence of n elements that contains exactly k occurrences of
the element x, here 1 ≤ k ≤ n. Design a randomized algorithm to find an index j such that
aj = x. Compute the expected running time of your algorithm.

Question 13 [10 points]

Let A1 , A2 , . . . , An be n arrays of integers where each array Ai is sorted in non-decreasing
order and has corresponding size ni . Design an efficient greedy algorithm to merge all
the arrays into a single sorted array. Also, provide the worst-case running time of your
algorithm.

Question 14 [10 points]

Let G = (V, E) be an undirected graph such that for every edge e ∈ E, ce > 0 is the cost of
the edge e.
Prove/disprove following statements:
(a) Let e be an edge with the minimum cost in G then every minimum spanning tree of G
contains the edge e.
(b) Let e be an edge with maximum cost in G then no minimum spanning tree of G contains
the edge e.
(c) Let all the costs of edges be unique then there is a unique minimum spanning tree of
G (regardless of starting vertex).
(d) Let all the costs of edge be the same then there are multiple minimum spanning trees
of G.
(e) Let v be a vertex in G with degree 1 then v is not included in any minimum spanning
tree of G.
(f) Let e = (u, v) be an edge with the maximum cost in G and degree of v is 1 then e is
included in every minimum spanning tree of G.

Page 3