advertisement

CS3001, Algorithm Design and Analysis Tutorial 2 — Coursework Questions 6) The following functions fi (n) (1 ≤ i ≤ 7) are given: (en )2 40 ∗ n2 − n, 14 log n4 , 27 ∗ n2 + 3 ∗ n + 1, 3 4 14(log n) , 100n log n, e 2 n, a) Arrange these functions according to O (such that fi (n) = O (fi+1 )). (Justify your assertions!) (3 Points) b) Assume these functions are runtimes for 7 algorithms that all solve the same problem. For which values of n (nearest integer) which algorithm has the shortest runtime? (2 Points) c) Assume you have an algorithm whose runtime is T (n) = n2 log(n). For what ranges of n (order of magnitude estimate) this algorithm will run in a second, an hour and a week on a 200MHz Processor, assuming one instruction is executed in one clock cycle. (1 Points) 7) We define 4 procedures A-D as follows: A(n): B(n): C(n): D(n): for i ∈ {1, . . . , n} do print “hello”;od; for i ∈ {1, . . . , n} do A(i);od; for i ∈ {1, . . . , n} do B(i);od; for i ∈ {1, . . . , n} do C(i);od; Give estimates, as Θ classes, for the run time of each procedure. (4 Points) 8) An (undirected) graph is called a tree if it has only one connected component (i.e. it is connected) and it has no cycles. A tree Not a tree Show: a) A connected undirected graph G = (V, E) is a tree if and only if |E| = |V | − 1. Hint: You have to show: i) “tree ⇒ |E| = |V | − 1” and ii)“|E| = |V | − 1 ⇒ tree”. Use induction on |V |. For the induction step, showP first that in both cases there must be a vertex of degree 1 (a leaf ). (For ii), remember that 2 |E| = v∈V deg(v).) Then remove this vertex. (The resulting graph will have one edge and one vertex less and will still be a tree.) (3 Points) b) A connected undirected graph G = (V, E) is a tree if and only if for two vertices u, v ∈ V there is exactly one path between u and v. (1 Points) Hand in solutions October 9th before the tutorial. 1