CSCI 570 – HW 1 solution

Description

1. Arrange the following functions in increasing order of growth rate with g(n) following
f(n) in your list if and only if f(n) = O(g(n))
2
log 𝑛
, (√2)
log 𝑛
, 𝑛 (log 𝑛)
3
, 2
√2 log 𝑛
, 2
2
𝑛
, 𝑛 log 𝑛 , 2
𝑛
2

2. Give a linear time algorithm based on BFS to detect whether a given undirected graph
contains a cycle. If the graph contains a cycle, then your algorithm should output one. It should
not output all cycles in the graph, just one of them. You are NOT allowed to modify BFS, but
rather use it as a black box. Explain why your algorithm has a linear time runtime complexity.

3. A binary tree is a rooted tree in which each node has at most two children. Show by
induction that in any nonempty binary tree the number of nodes with two children is exactly one
less than the number of leaves.

4. Prove by contradiction that a complete graph K5 is not a planar graph. You can use facts
regarding planar graphs proven in the textbook.

5. Suppose we perform a sequence of n operations on a data structure in which the i
th
operation costs i if i is an exact power of 2, and 1 otherwise. Use aggregate analysis to determine
the amortized cost per operation.

6. We have argued in the lecture that if the table size is doubled when it’s full, then the
amortized cost per insert is acceptable. Fred Hacker claims that this consumes too much space.
He wants to try to increase the size with every insert by just two over the previous size. What is
the amortized cost per insertion in Fred’s table?

7. You are given a weighted graph G, two designated vertices s and t. Your goal is to find a
path from s to t in which the minimum edge weight is maximized i.e. if there are two paths with
weights 10→1→5 and 2→7→3 then the second path is considered better since the minimum
weight (2) is greater than the minimum weight of the first (1). Describe an efficient algorithm to
solve this problem and show its complexity.