Data Structure and Programming, Spring 2021
Midterm Exam
Lecturer: Pei-Yuan Wu
TAs: Mark Chang, Shu-Han Yang, and Gi-Luen Huang
04/22/2021
This exam contains 9 problems and 100 pts in total.
1. Warm-Up Complexity Analysis. (10 pts)
Please analyze the time complexities for each of the following questions.
(a) (5 pts) The best case time complexity of quick sort. (cf. Figure.1)
(b) (5 pts) The worst case time complexity of binary search. (cf. Figure.2)
1
Figure 1: The sample code for quick sort.
2
Figure 2: The sample code for binary search
2. Recurrence Complexity Analysis. (15 pts)
Find time complexity of T (n) in Θ notation. Please justify your answer.
(Assume T (n) ∈ Θ(1) for n ≤ 4.)
n
(a) (3 pts) T (n) = 4T (n/3) + log n .
5
(b) (3 pts) T (n) = 4T (n/2) + n 2 .
(c) (3 pts) T (n) = 4T ( n2 ) + n2 (log n)2 .
(d) (3 pts) T (n) = 9T ( n4 ) + 2n .
(e) (3 pts) T (n) = T (n − 2) + 6T (n − 4) + 1.
3. Link of Asymptotic Notations. (12 pts)
Assume all functions are positive. Prove or disprove (with counter exam-
ple) the following statements:
(a) (3 pts) If T (n) ∈ ω(φ(n)), then T (n) ∈ Ω(φ(n)) and T (n) ∈
/ Θ(φ(n)).
(b) (3 pts) If T (n) ∈ Ω(φ(n)) and T (n) ∈
/ Θ(φ(n)), then T (n) ∈ ω(φ(n)).
(c) (3 pts) If f (n) ∈
/ O(g(n)), then g(n) ∈ O(f (n)).
(d) (3 pts) If f (n) ∈ o(g(n)), then f (n) ∈ O(g(n)).
4. Magnitude of Growth Comparison (12 pts)
In the following questions, please compare the magnitude of growth (in
either Θ, o, or ω notations). Please justify your answers.
3
(a) (3 pts) log(n!) v.s. log(nn ).
(b) (3 pts) dlog nen v.s. n100 · 100n .
(c) (3 pts) dlog nen v.s. n!.
(d) (3 pts) dlog2 ne! v.s. log(n!).
4
5. Approximation of Factorials. (12 pts)
In this question we will derive a good approximation to the factorial n!.
For m = 1, 2, 3, ..., define
f (x) = (m + 1 − x) log m + (x − m) log(m + 1)
if m ≤ x < m + 1, and
x
g(x) = − 1 + log m
m
1
if m − 2 ≤ x < m + 12 .
(a) (3 pts) Draw the graphs of f and g, and justify that f (x) ≤ log x ≤
g(x) for x ≥ 1.
(b) (3 pts) Show that
Z n
1
f (x)dx = log(n!) − log n.
1 2
(c) (3 pts) Show that
Z n
1 1 1
g(x)dx = log(n!) − log n + − .
1 2 8 8n
(d) (3 pts) Show that
7 n!
e8 < √ < e.
(n/e)n n
R
(Hint: log x dx = x log x − x + C.)
Side note: This is a less precise result of the Stirling’s formula
n! √
lim n
√ = 2π ≈ e0.918 .
n→∞ (n/e) n
6. Implement Stack/Queue with Singly-Linked List (10 pts)
Consider the UnorderedList discussed in class (cf. Figure.3 and Figure.4).
(a) (5 pts) Describe how to implement a stack using UnorderedList.
The operations Push and Pop should take O(1) time.
(b) (5 pts) Describe how to implement a queue using UnorderedList.
The operations Enqueue and Dequeue should take O(1) time.
Note that in both implementations you should use no more than constant
storage beyond what is needed for the linked list itself.
5
Figure 3: The sample code of Node class.
6
Figure 4: The sample code of UnorderedList class.
7. Bell Number. (9 pts)
The Bell numbers denoted Bn count the number of different ways to par-
tition a set that has exactly n elements. The first few Bell numbers are:
B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 203, ...
The initial case B0 = 1 and B1 = 1 since the empty set ∅ has only one
partition: n o
∅ ,
7
and the one-element set {a} has only one partition, too:
n o
{a} .
Furthermore, B2 = 2 and B3 = 5 since the 2-element set {a, b} has 2
distinct partitions: n o n o
{a}, {b} , {a, b} ,
and 3-element set {a, b, c} has 5 distinct partitions:
n o n o n o n o n o
{a}, {b}, {c} , {a}, {b, c} , {b}, {a, c} , {c}, {a, b} , {a, b, c} .
(a) (3 pts) Please derive a recurrence relation for Bn .
(b) (3 pts) Please design an algorithm CompB(n) to compute Bn for
any integer n ≥ 0.
(c) (3 pts) Please analyze the time complexity of the algorithm you
designed above. (Grading will depend on the efficiency of your algo-
rithm).
8. Finding the Missing Integer. (10 pts)
An array (A[k])nk=1 contains all the integers from 0 to n except one. It
would be easy to determine the missing integer in O(n) time by using an
auxiliary array (B[k])nk=0 to record which numbers appear in A. In this
problem, however, we cannot access an entire integer in A with a single
operation. The elements in A are represented in binary, and the only
operation we can use to access them is “fetch the j’th bit of A[i]”, which
takes constant time.
Show that if we use only this operation, we can still determine the missing
integer in O(n) time.
9. Minimum Cost For Tickets. (10 pts)
In a country popular for train travel, you have planned some train travel-
ling one year in advance. There are three types of train tickets:
• A 1-day pass is sold for 1 dollar;
• A 3-day pass is sold for 2 dollars;
• A 7-day pass is sold for 4 dollars.
The passes allow that many days of consecutive travel. For example, if we
get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6,
7, and 8.
Suppose you plan to travel in days 2, 5, 7, 9, 11, 13, 14, 15, 17, 21, 22,
24, 25, 27, 30. How will you buy your tickets so as to minimize the total
cost? Please elaborate which kind of tickets to buy at which days, as well
as the total cost.
