Description
Asymptotic Analysis
1. Kleinberg, Jon. Algorithm Design (p. 67, q. 3, 4). Take the following list of functions and arrange them
in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your
list, then it should be the case that f(n) is O(g(n)).
(a) f1(n) = n
2.5
f2(n) = √
2n
f3(n) = n + 10
f4(n) = 10n
f5(n) = 100n
f6(n) = n
2
log n
(b) g1(n) = 2log n
g2(n) = 2n
g3(n) = n(log n)
g4(n) = n
4/3
g5(n) = n
log n
g6(n) = 2(2n)
g7(n) = 2(n
2
)
CS 577 Assignment 2 – Asymptotic Analysis & Graphs
2. Kleinberg, Jon. Algorithm Design (p. 68, q. 5). Assume you have a positive, non-decreasing function f
and a positive, increasing function g such that g(n) ≥ 2 and f(n) is O(g(n)). For each of the following
statements, decide whether you think it is true or false and give a proof or counterexample.
(a) log2
f(n) is O(log2
g(n))
(b) 2
f(n)
is O(2g(n)
)
(c) f(n)
2
is O(g(n)
2
)
Page 2 of 7
CS 577 Assignment 2 – Asymptotic Analysis & Graphs
3. Kleinberg, Jon. Algorithm Design (p. 68, q. 6). You’re given an array A consisting of n integers. You’d
like to output a two-dimensional n-by-n array B in which B[i, j] (for i < j) contains the sum of array
entries A[i] through A[j] — that is, the sum A[i] + A[i + 1] + … + A[j]. (Whenever i ≥ j, it doesn’t
matter what is output for B[i, j].) Here’s a simple algorithm to solve this problem.
f o r i = 1 to n
f o r j = i + 1 to n
add up a r ra y e n t r i e s A[ i ] through A[ j ]
s t o r e the r e s u l t i n B[ i , j ]
e n d fo r
e n d fo r
(a) For some function f that you should choose, give a bound of the form O(f(n)) on the running time
of this algorithm on an input of size n (i.e., a bound on the number of operations performed by the
algorithm).
(b) For this same function f, show that the running time of the algorithm on an input of size n is also
Ω(f(n)). (This shows an asympto tically tight bound of Θ(f(n)) on the running time.)
(c) Although the algorithm provided is the most natural way to solve the problem, it contains some
highly unnecessary sources of inefficiency. Give a different algorithm to solve this problem, with an
asymptotically better running time. In other words, you should design an algorithm with running
time O(g(n)), where limn→∞
g(n)
f(n) = 0.
Page 3 of 7
CS 577 Assignment 2 – Asymptotic Analysis & Graphs
Graphs
4. Given the following graph, list a possible order of traversal of nodes by breadth-first search and by
depth-first search. Consider node 1 to be the starting node.
5
4
3
2
1
9
8
7
6
5. Kleinberg, Jon. Algorithm Design (p. 108, q. 5). A binary tree is a rooted tree in which each node has
at most two children. Show by induction that in any binary tree the number of nodes with two children
is exactly one less than the number of leaves.
Page 4 of 7
CS 577 Assignment 2 – Asymptotic Analysis & Graphs
6. Kleinberg, Jon. Algorithm Design (p. 108, q. 7). Some friends of yours work on wireless networks, and
they’re currently studying the properties of a network of n mobile devices. As the devices move around,
they define a graph at any point in time as follows:
There is a node representing each of the n devices, and there is an edge between device i
and device j if the physical locations of i and j are no more than 500 meters apart. (If so,
we say that i and j are “in range” of each other.)
They’d like it to be the case that the network of devices is connected at all times, and so they’ve constrained the motion of the devices to satisfy the following property: at all times, each device i is within
500 meters of at least n
2
of the other devices. (We’ll assume n is an even number.) What they’d like to
know is: Does this property by itself guarantee that the network will remain connected?
Here’s a concrete way to formulate the question as a claim about graphs.
Claim: Let G be a graph on n nodes, where n is an even number. If every node of G has
degree at least n
2
, then G is connected.
Decide whether you think the claim is true or false, and give a proof of either the claim or its negation.
Page 5 of 7
CS 577 Assignment 2 – Asymptotic Analysis & Graphs
Coding Question
7. Implement depth-first search in either C, C++, C#, Java, or Python. Given an undirected graph with
n nodes and m edges, your code should run in O(n + m) time. Remember to submit a makefile along
with your code, just as with week 1’s coding question.
Input: the first line contains an integer t, indicating the number of instances that follows. For each
instance, the first line contains an integer n, indicating the number of nodes in the graph. Each of the
following n lines contains several space-separated strings, where the first string s represents the name
of a node, and the following strings represent the names of nodes that are adjacent to node s. You can
assume that the nodes are listed line-by-line in lexicographic order (0-9, then A-Z, then a-z), and the
adjacent nodes of a node are listed in lexicographic order. For example, consider two consecutive lines
of an instance:
0, F
B, C, a
Note that 0 < B and C < a.
Input constraints:
• 1 ≤ t ≤ 1000
• 1 ≤ n ≤ 100
• Strings only contain alphanumeric characters
• Strings are guaranteed to be the names of the nodes in the graph.
Output: for each instance, print the names of nodes visited in depth-first traversal of the graph, with
ties between nodes visiting the first node in input order. Start your traversal with the first node in input
order. The names of nodes should be space-separated, and each line should be terminated by a newline.
Sample:
Input:
2
3
A B
B A
C
9
1 2 9
2 1 6 5 3
4 6
6 2 4
5 2
3 2 7
7 3
8 9
9 1 8
Output:
A B C
1 2 6 4 5 3 7 9 8
The sample input has two instances. The first instance corresponds to the graph below on the left. The
second instance corresponds to the graph below on the right.
Page 6 of 7
CS 577 Assignment 2 – Asymptotic Analysis & Graphs
A
B
C
5
4
3
2
1
9
8
7
6