Description
1. Arrange these functions under the Big-O notation in increasing order of
growth rate with g(n) following f(n) in your list if and only if f(n) =
O(g(n)) (here, log(x) is the natural logarithm1 of x, with the base
being the Euler’s number e) :
2
log(n)
, 2
3n
, 3
2n
, nn log(n)
, log(n), n log(n
2
), nn
2
, log(n!), log(log(n
n
)).
2. Show by induction that for any positive integer k, (k
3 + 5k) is divisible
by 6.
3. Show that 13 + 23 + · · · + n
3 =
n
2
(n+1)2
4
for every positive integer n using
induction.
4. Consider the following prime filtering algorithm that outputs all the
prime numbers in 2, . . . , n (the pseudo code is presented in Algorithm 1).
• Please prove this algorithm is correct (that is, a positive integer k
that 2 ≤ k ≤ n is a prime if and only if isP rime(k) = True).
• Please calculate the time complexity under the Big-O notation.
Algorithm 1 Prime Filtering
1: Input: a positive integer n ≥ 2
2: initialize the Boolean array isP rime such that isP rime(i) = True for i = 2, . . . , n
3: for i = 2 . . . n do
4: for j = 2 . . .
n
i
do
5: if i × j ≤ n then
6: isP rime(i × j) ← False
7: end if
8: end for
9: end for
5. Amy usually walks from Amy’s house (“H”) to SGM (“S”) for CSCI 570.
On her way, there are six crossings named from A to F. After taking
the first course, Amy denotes the six crossings, the house, and SGM
as 8 nodes, and write down the roads together with their time costs (in
minutes) in Figure 1. Could you find the shortest path from Amy’s house
to SGM? You need to calculate the shortest length, and write down all
the valid paths.
1https://en.wikipedia.org/wiki/Natural_logarithm
A
D
B
E
C
F
5
6 7
6
4
8 6
5
4 3
Figure 1: Problem 4’s Graph
6. According to the Topological Sort for DAG described in Lecture 1, please
find one possible topological order of the graph in Figrue 2. In addition,
could you find all the possible topological orders?
A
D
B
E
C
F
G
Figure 2: Problem 5’s Graph
7. A binary tree2
is a rooted tree in which each node has two children at
most. A complete binary tree is a special type of binary tree where all
the levels of the tree are filled completely except the lowest level nodes
which are filled from as left as possible. For a complete binary tree T
with k nodes, suppose we number the node from top to down, from left
to right with 0, 1, 2, …, (k −1). Please solve the following two questions:
• For any of the left most node of a layer with label t, suppose it has
2https://en.wikipedia.org/wiki/Binary_tree
at least one child, prove that its left child is 2t + 1.
• For a node with label t and suppose it has at least one child, prove
that its left child is 2t + 1.
8. Consider a full binary tree (all nodes have zero or two children) with
k nodes. Two operations are defined: 1) removeLastNodes(): removes
nodes whose distance equals the largest distance among all nodes to the
root node; 2) addTwoNodes(): adds two children to all leaf nodes. The
cost of either adding or removing one node is 1. What is the time complexity of these two operations, respectively? Suppose the time complexity to obtain the list of nodes with the largest distance to the root and
the list of leaf nodes is both O(1).
9. Given a sequence of n operations, suppose the i-th operation cost 2j−1
if i = 2j
for some integer j; otherwise, the cost is 1. Prove that the
amortized cost per operation is O(1).
10. Consider a singly linked list as a dictionary that we always insert at
the beginning of the list. Now assume that you may perform n insert
operations but will only perform one last lookup operation (of a random
item in the list after n insert operations). What is the amortized cost
per operation?
