CS608 Algorithms & Computing Theory
Midterm Exam
Sung-Hyuk Cha
(March 13, 2019 version 1.)
Exam questions are based on materials covered in CS 608 on Spring of 2019.
Do not turn the cover page until announced.
.1. This test consists of five parts (25 pnts each) and each part has five ques-
tions (5 pnts each). 125 points in total.
.2. Students with 90 points or higher: A.
Students with 85 points or higher: A-.
Students with 80 points or higher: B+.
Students with 75 points or higher: B.
Students with 70 points or higher: B-.
Students with 65 points or higher: C+
Students with 60 points or higher: C
Students with 55 points or higher: C-
Students with 50 points or higher: D
.3. You have 2 hours and 30 minites to complete the exam. (6:15pm∼8:45pm)
.4. Only a simple calculator, pencils, and erasers are allowed.
Master Theorem: T (n) = aT (nb ) + f(n) where a ≥ 1 and b ≥ 1.
Case 1: If f(n) = O(nlogb a−) for some > 0,
T (n) = Θ(nlogb a)
Case 2: If f(n) = Θ(nlogb a logk n) for some k ≥ 0,
T (n) = Θ(nlogb a logk+1 n)
Case 3: If f(n) = Ω(nlogb a+) for some > 0
and af(n/b) ≤ cf(n) for some c < 1,
T (n) = Θ(f(n))
1
I Sum of odd numbers
Consider the problem of adding the first n odd numbers.
I.1. Formulate the problem.
I.2. Derive a closed form.
I.3. Prove the correctness of your closed form.
I.4. Derive a first order linear recurrence relation of the problem.
I.5. Devise an algorithm using inductive programming.
II Alternating permutation - checking up-down
Consider the problem of checking whether a given a sequence A1∼n of n num-
bers is a up-down alternating sequence.
Problem II.X Checking up-down sequence
Input: A sequence A of n quantifiable elements
Output:
true ∀i ∈ {1, · · · , n− 1},
{
ai < ai+1 if i is odd
ai > ai+1 if i is even
false otherwise
For example, isupdown(〈5, 9, 1, 4, 2〉) returns true and isupdown(〈5, 2, 1, 9, 4, 3〉)
returns false.
II.1. Derive a first order linear recurrence relation of Problem II.X.
II.2. Devise an inductive programming algorithm for Problem II.X.
II.3. Devise a dvide and conquer algorithm for Problem II.X.
II.4. Illustrate your algorithm proposed in II.3 on the following toy example:
A = 2 11 3 10 7 9 1 5 4 8 6
II.5. Provide the computational time complexity of your divide and conquer
algorithm provided in II.3.
2
III Divide recurrence relation
Consider the following recurrence in eqn (1).
T (n) =
{
1 if n = 1
2T (n/2) + 1 if n > 1
(1)
III.1. Find the equivalent closed asymptotic notation for eqn (1) using the Mas-
ter Theorem.
III.2. Prove the solution of the divide recurrence in eqn. (2) is T (n) = 2n − 1
for any positive integer n using strong induction.
T (n) =
{
1 if n = 1
T (
⌊
n
2
⌋
) + T (
⌈
n
2
⌉
) + 1 if n > 1
(2)
III.3. Devise a strong inductive programming algorithm to find T (n) in eqn. (2)
and analyze the computational time and space complexities.
III.4. Devise a memoization algorithm to find T (n) in eqn. (2) and analyze the
computational time and space complexities.
III.5. Illustrate your algorithm based on the memoization method in d) for T (61)
and analyze the computational time and space complexities. (Hint: show
the table.)
3
IV Unbounded equality knapsack minimization
There are three missiles (blue, red, and yellow) with different points gained and
energy required. The problem, V (n), is to score exactly n points using as little
energy as possible. Note that if the points gained is short or exceeds m, it is a
loss. Exactly m points earned using the least energy is a winner.
missile blue red yellow
energy E 1 3 4
point P 1 5 6
IV.1. Formulate the problem.
IV.2. Design a greedy algorithm and prove the correctness or incorrectness of
the proposed algorithm.
IV.3. Devise a strong inductive programming (conventionally known as dynamic
programming) algorithm.
Hint: A recurrence relation of the problem is given in eqn (3).
V (n) =

∞ 〈impossible〉 if n < 0
0 if n = 0
min
1≤i≤k
(V (n− pi) + ei) if n > 0
(3)
IV.4. Illustrate the algorithm proposed in IV.3 on the above toy example:
IV.5. Devise a memoization algorithm.
4
V Cycle number
Consider the problem of finding the cycle number, a.k.a., Stirling number of the
first kind, or SNF in short, as defined in eqn (4).
Problem V.1 Cycle number (Stirling number of the first kind)
Input: n, k where n, k ∈ Z
Output: S(n, k) =
1 if k = n = 0
0 if (k = 0 ∧ n > 0) ∨ k > n
S(n− 1, k − 1) + (n− 1)S(n− 1, k) if 0 < k < n
(4)
S C G R
G R
CS
S R G C S G R C
R G
C
S R
C
R S
C
S G
C
G S
C
S R
G
R S
GS
G
G
R
R
C
C
1
0 1
0 1
0 2 3 1
1
0 6 11 6
0 24 50
0 120
0 720 21 1
15 1
10 1
1
35
274 225
1624 735 175
85
1764
S(n = 4, k = 2) = 11 SNF triangle
V.1. Find the value of S(5, 2) and the number of recursive calls when the na¨ıve
recursive algorithm in eqn (4) is used. (Hint: draw the recursion tree.)
V.2. Describe a memoization algorithm to compute S(n, k).
V.3. Provide the number of recursive calls necessary to compute S(6, 3) when
the algorithm provided in V.2 is used.
V.4. Provide a strong inductive programming algorithm to compute S(n, k).
V.5. Provide the computational time and space complexities of the algorithm
provided in V.4.
5
















































































































































































学霸联盟