CSCI 570 – HW 1 Due Sunday Feb. 07 (by 23:30)
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))
2log𝑛, (√2)log𝑛, 𝑛(log𝑛)3, 2√2log𝑛 , 22𝑛, 𝑛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 ith 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.