CISC 7200X. Analysis of Algorithms
Fall 2016
Announcements:

Final Exam Grades

Problem 2: Both parts can be accomplished with
k+1=log_2(n)+1 comparisons.

2a: Find i such that A[i1] < x <= A[i]
then check if A[i] <= x+k.

2b: Find i such that x=A[i]
then check if A[i+k]=x+k.

Problem 3: O(n) for a(i); O(n+m) for b(i); and
O(n^2) for a(ii) and b(ii).

Problem 1:

n(n+1) for part (a) and therefore T(n)=Theta(n^2) for part (c).

6n3 for part (b) and therefore T(n)=Theta(n) for part (d).

log_2(n^100)=Theta(log_10(n)) for part (e).

The time complexity of the code is Theta(n) for part (f).

n=Theta(k^2) ==> Theta(k^2)=Theta(n+k) for part (g).

The minimum possible number of leaves in a tree is
either 1 or 2 for part (h).

The maximum number of edges in a bipartite graph
with 2n vertices is n^2 for part (i).

The only false statement in part (j) is the firts:
Every bipartite graph is a tree".
Information:
Classes:
Assignments: