CSC165H1 Problem Set 4

CSC165H1 Problem Set 4

1. [12 marks] algorithm analysis
Read over the code for has odd. Assume that number list contains entries from f0; 1; 2; 3; 4g, with duplicates
allowed. Answer the questions below, assuming that n = len(number list)
Page 1/2
CSC165H1, Fall 2019 Problem Set 4
1 def has_odd(number_list) -> bool:
2 for i in range(len(number_list)):
3 if number_list[i] % 2 == 1:
4 return True
5 return False
(a) [3 marks] Find a good upper bound, U(n), for W Chas odd(n). Prove that your upper bound is correct.
(b) [3 marks] Find a lower bound, L(n), for W Chas odd(n) that is in the same asymptotic complexity
class as U(n) (that's what I mean by \good" in the previous part). Prove that your lower bound is
correct, then state and justify a simple big-Theta complexity class for W Chas odd(n)
(c) [3 marks] If has odd returns True after examining k entries in number list, count this as k steps. If an
has odd examines all n entries in number list and proceeds to return False count this as n + 1 steps.
Using these assumptions, show how to calculate the average number of steps for all inputs to has odd
of length 2.
(d) [3 marks] Use the step-counting assumptions in the previous part to devise a formula for the average
number of steps for all inputs to has odd of length n. You may  nd it useful to recall (where r is
some positive real number)
i=Xn1
i=0
iri =
nrn
r  1
+
r  r
n+1
(r  1)2
Show your work.
2. [18 marks] graph connectivity
Answer the questions below. Assume jV j is  nite and positive.
(a) [3 marks] Prove that for all undirected graphs G = (V; E), if C is a cycle in G and e is an edge in
C, then removing e leaves C connected. Notice that this is used in Example 6.8, so you cannot use
Example 6.8 as proof, nor can you use the fact that this is asserted without proof in the paragraph
just before Example 6.8.
(b) [3 marks] Prove or disprove: In every undirected graph G = (V; E) with all vertices having degree at
least bjV j=3c, for every 3 distinct vertices u; v; w 2 V there is a path of length no more than 2 from
u to v, or from v to w, or from w to u.
(c) [3 marks] Prove or disprove: If graph G = (V; E) has an odd number of vertices with even degree,
then jV j is odd.
(d) [3 marks] Prove or disprove: Every undirected graph G = (V; E) with at least 13 vertices, all vertices
having degree at least jV j  7, is connected.
(e) [3 marks] Prove that every undirected graph G = (V; E) with every vertex having degree at least 5,
has a cycle.
(f) [3 marks] Prove or disprove: If G = (V; E) is an undirected graph where every vertex has degree at
least 4 and u 2 V , then there are at least 64 distinct paths in G that start at u.
Pag