Description
1. Textbook [Kleinberg & Tardos] Chapter 2, page 69, problem #8.
2. Textbook [Kleinberg & Tardos] Chapter 3, page 107, problem #4 .
3. Textbook [Kleinberg & Tardos] Chapter 3, page 107, problem #11 .
4. List the following functions in increasing asymptotic order. Between each adjacent functions
in your list, indicate whether they are asymptotically equivalent (f(n) ∈ Θ(g(n)), you may use
the notation that f(n) ≡ g(n)) or if one is strictly less than the other (f(n) ∈ o(g(n)) and use
the notation that f(n) ≺ g(n)).
5n
3 + log n 2
n 3
n/2 2
n/3 √
lg n
ln n 2
√
lg n min{n
2
, 1045n}
Pn
i=1 i
77 n
ln 4
bn
2/45c dn
2/45e n
2/45 lg √
n lg lg n
Pn
i=1 1/i Pn
i=1 1/i2 Pn
i=1(i
2 + 5i)/(6i
4 + 7) ln(n!) (lg n)
√
lg n
5. An Euler tour of a graph G is a closed walk through G that traverses every edge of G exactly
once.
(a) Prove that a connected graph G has an Euler tour if and only if every vertex has even
degree.
(b) Describe and analyze an algorithm to compute an Euler tour in a given graph, or correctly
report that no such tour exists.
6. Prove that any connected acyclic graph with n ≥ 2 vertices have at least two vertices with
degree 1. Notice that you should not use any known properties of trees and your proof should
follow from the definitions directly.
∗Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA,
jgao@cs.stonybrook.edu.
1