Description

Neel Gupta
Problem 1. Arrange the following functions by asymptotic time complexity using big-O notation.
a) 2logn
b) 23n
c) nnlogn
d) log n
e) n log(n2)
f) nn2
g) log(log(nn))
Answer: log n ⊂ log(log(nn)) ⊂ 2logn ⊂ n log n2 ⊂ 23n ⊂ nnlogn ⊂ nn2
2logn = n
23n = (23)n = 8n
nnlogn = 2log(nnlogn) = 2nlogn∗logn = 2n(logn)2
n log(n2) = 2n log n nn2 = 2lognn2 = 2n2 logn
log(log(nn)) = log(n log n)
Corrections:
log n = log(log(nn)) ⊂ 2logn ⊂ n log n2 ⊂ 23n ⊂ nnlogn ⊂ nn2 f(n) is said to be O(g(n)) iff f(n) ≤ cg(n) ∀n > n0 where c > 0, n0 > 0 Prove f(n) = log(n log n) is O(log n). log(log nn) = log(n log n) ≤ log(n2) = 2log n is O(log n)
∴ log(log nn) is O(log n)
Problem 2. Given functions f1, f2, g1, g2 such that f1(n) = O(g1(n)) and f2(n) = O(g2(n)), decide whether each statement is true or false and
briefly explain why.
a) f1(n)/f2(n) = O(g1(n)/g2(n))
b) f1(n) + f2(n) = O(max(g1(n), g2(n)))
c) f12(n) = O(g12(n))
d) log f1(n) = O(log g1(n))
a) Answer: True
∃N ∈ N and c1, c2 ∈ R s.t. ∀n ∈ N and n ≥ N,
f1(n) ≤ c1g1(n)
f2(n) c2g2(n)
= (c1/c2)g1(n)/g2(n) (∵ c1/c2 ∈ R)
∴ f1(n)/f2(n) = O(g1(n)/g2(n))
b) Answer: True
f1(n) + f2(n) ≤ c1g1(n) + c2g2(n))
≤ c1 ∗ max(g1(n), g2(n)) + c2 ∗ min(g1(n), g2(n))
≤ (c1 + c2) max(g1(n), g2(n))
= O(max(g1(n), g2(n))
∴ f1(n) + f2(n) = O(max(g1(n), g2(n)))
c) Answer: True
∃N ∈ N and c ∈ R s.t. ∀n ∈ N and n ≥ N,
0 ≤ f1(n) ≤ cg1(n) (∵ f1(n) = O(g1(n)))
02 ≤ f12(n) ≤ (cg1(n))2
= c2g12(n) (∵ c2 ∈ R)
∴ f12(n) = O(g12(n))
d) Answer: False
Consider the following counterexample.
Let f1(n) = 1 and g1(n) = 2 log2 f1(n) = 0 ̸= O(1) = 1 = log2 g1(n)
∴ log f1(n) ̸= O(log g1(n))
Corrections:
(a): False
Consider the following counter example:
f1(n) = n3, g1(n) = n3 f2(n) = n, g2(n) = n3
f1(n) 2 ̸= O(1) = g1(n) = n
f2(n) g2(n)
Big-O is an upper bound, but not necessarily a tight upper bound.
Problem 3. Given an undirected graph G with n nodes and m edges, design an algorithm in O(m + n) to detect whether G contains a cycle. Your algorithm should output a cycle if there is one.
Answer: The following problem can be solved using a depth-first search (DFS) approach where we go down successive levels and see if a neighbor of a deeper node has already been found as a neighbor of a previous node using a list of size n to keep store of visited nodes.
Let v¯ be a list of size n where vi is j if xj visited xi, and 0 otherwise procedure DETECTCYCLES(G, xi, xj, v¯) visit xi, so set vi to j, the index of i’s parent for each neighbor xk of xi do if vk is already not 0 then if xk is not xi’s child then return true
end if
else if detectCycles(G,xi,xk, v¯) then return true
end if end for return false end procedure
while G has unvisited nodes do Let x1 be the root or first unvisited node
detectCycles(G, 0, x1, v¯)
end while
The time complexity of this algorithm is O(n + m), and the space complexity of the algorithm is O(n). The algorithm terminates in a finite amount of time since for each connected undirected graph, the algorithm will return false after traversing all neighbors then all neighbors of those those neighbors until every piece of the connected graph has been visited. This DFS traversal takes O(n + m) since only after visiting every node in
G through potentially every edge can we deduce whether our graph has a cycle or not.
Problem 4. Given an array A of n integers, return an n-by-n matrix B in which B[i, j] (for i < j) contains the sum of array entries A[i] to A[j].

Algorithm 1 Simple algorithm to achieve this

for i = 1,2,…, n do
for j = i + 1,i + 2,…, n do
Add up array entires A[i] through A[j]
Store result in B[i, j] end for
end for

a) For some function f, give an upper bound in the form O(f(n)) on the runtime of this algorithm on an input of size n.
b) For this same function f, show that the runtime of this algorithm on an input of size n is also Ω(f(n)).
c) Although this simple algorithm is the most natural way to solve this problem, it contains some highly unnecessary sources of inefficiency. Give a different algorithm to solve this problem with an asymptotically better running time.
Answer:
a) The first loop will make n iterations, and the second will loop will make n more iterations at each of those iterations. At each of these iterations, we want to sum up the ith to jth element which takes O(j − i + 1). In the worst case, this will be take O(n) time per each n2 iterations, so an upper bound on the runtime of this algorithm could be O(n3).
b) By showing that this algorithm is Θ(n3), we can imply that the run-
time of this algorithm is also Ω(n3).
Consider the time when i ≤ n/4 and j ≥ 3n/4,
n
then j
2
∴ A[i] + … + A[j] ≥ n/2
There are (n4)2 iterations where i ≤ n/4 and j ≥ 3n/4, and at each of these iterations, at least n/2 work is done.
f(n) is Ω(n3).
c) This task can be completed in O(n2) time by precomputing the sums.

Algorithm 2 More optimized algorithm to achieve the same task

for i = 1,2,…, n do
B[i,i + 1] ← A[i] + A[i + 1] ▷ computing the running sum end for for j = 2,3,…, n do for k = 1,2,…, n do newIdx ← j + k
B[i, newIdx] ← B[i, newIdx − 1] + A[j] end for
end for

There are O(n) operations to compute running sums for the first column of the matrix. Then for each of the n iterations, there are up to n more iterations, resulting in a runtime of f(n) = n + (n − 2) ∗ n = O(n2).
Problem 5. Consider a researcher’s Erdos Number, which for Paul Erdos was 0, for researchers who wrote papers with him was 1, for researchers who wrote papers with researchers who wrote papers with him was 2, and so on, that represents how many degrees of freedom of writing are between writers and Erdos himself. Suppose we have a database of all mathematical papers ever written along with their authors.
a) Explain how to represent this data as a graph.
b) Explain how we would compute the Erdos number for a particular researcher.
c) Explain how we would determine all researchers with Erdos numbers at most two.
Answer:
a) Let G be an undirected graph where authors are nodes and an edgebetween nodes X and Y represent whether author X cowrote a paper with author Y. This graph could represent mathematicians and their authorship to be able to compute Erdos Numbers
b) To compute the Erdos Number of a particular researcher, find thenumber of minimum number edges which are taken to connect the particular researcher to Paul Erdos, then that number of edges is the researcher’s Erdos number.
c) Beginning at the root who is Paul Erdos, conducting a breadth-firstsearch on his node would mean going through the graph G level by level where Erdos number is given by level of depth. All researchers with Erdos numbers at most 2 would be whoever would be visited after running BFS beginning with Erdos’s coauthors then visiting the coauthors of Erdos’s coauthors, and upon visiting someone who is 3 levels away from Erdos, the search should terminiate, resulting with the set of authors visited as being those with Erdos number of at most 2.
Problem 6. Given a directed acyclic graph, give a linear time algorithm to determine if there is a simple path that visits all vertices.
Answer:
By conducting a topological sort on a DAG, we can see whether ”all prerequisites have been met” or a simple path exists between all vertices.
This algorithm runs in O(n). At each iteration, there can be up to |E| or m iterations to neighboring nodes, so for each n nodes, there can be up to m amounts of work, so the runtime for the algorithm will be less than

Algorithm 3 Algorithm to see if there exists a path visits all verticies

Let G be a DAG
Let v be a list of in-degrees for n nodes Let t be an empty list for the result ordering
for every node i in G do
vi ← in-degree of node i
end for
Let q be a queue initialized to all nodes with in-degree 0
while q is not empty do
if all nodes have been dequeued then return false
end if dequeue from q to get node i add i to the topological ordering t
for all out going edges (i, j) do vj ← vj − 1
if vj is 0 then
add u to q
else if vj is -1 then return false
end if end for
end while if t has n elements then return true
else return false end if

or equal to mn, but since m is a constant and cannot occur everytime, the runtime is O(n). This algorithm is based on creating a topological ordering of all nodes, and if not, it returns false after doing some constant amount of work on each node, thus taking linear time.