Algorithm Design COMP3027/3927 Tutorial questions The University of Sydney 2020 Semester 1 Tutorial 1 School of Computer Science
Pre-tutorial questions
Do you know the basic concepts of this week’s lecture content? These questions are only to test yourself. They will not be explicitly discussed in the tutorial, and no solutions will be given to them.
1. Running times
(a) What is an algorithm’s worst case running time?
(b) What does it mean when we say that the algorithm runs in polynomial time?
(c) What does it mean mean we say that an algorithm is efficient?
(d) Look at the table with the running times in the slides. Can you explain the reason for these numbers?
2. Asymptotic analysis
(a) Can you explain the ideas of the O(·), Θ(·) and Ω(·) functions? Why do we use these functions? (b) What does it mean that these functions are transitive and additive?
3. Basic data structures (revision)
(a) What are linked lists, queues, stacks and balanced binary trees? What sort of operations are usually supported by these structures?
(b) What is the height of a balanced binary tree containing n elements?
4. Graph terminology (revision)
(a) What is a graph G(V, E)?
(b) Graphs are usually represented either as an adjacency matrix or as an adjacency list. Can you
explain the two representations?
(c) What are the advantages/disadvantages between the two different representations?
(d) What is a simple path in a graph?
(e) What is a cycle in a graph?
(f) What is a tree? If a tree has n vertices, how many edges does it have?
(g) What is the difference between a rooted tree and an unrooted tree?
(h) What is a bipartite graph?
5. Graph traversals (revision)
(a) What is the difference between BFS and DFS? (b) Explain the two search algorithms BFS and DFS.
1
Tutorial
Problem 1
Sort the following functions in increasing order of asymptotic growth
3nn√√3 n,n ,nlogn, logn, log2 n, n, n
Problem 2
Sort the following function in decreasing order of asymptotic growth
n 2n 1 n1.5,2n, , ,n!,1.5n,2log2 n,nlog2 n
Which of the following is largest asymptotically
log3 n, log2 n, log10 n
Problem 4
Use induction to prove that the sum S(n) of the first n natural numbers is n(n + 1)/2. Problem 5
1. For each of the following pseudo-code fragments, give an upper bound for their running time using the big-Oh notation.
2. Typically, our goal is to prove an upper bound on the worst case running time of an algorithm. Some- times, we want to prove a lower bound instead. Such a lower bound would show that there are “bad” instances which would cause the algorithm to take a long time. More formally, we say that an algorithm is Ω(f(n)) if there exists constants n0,c > 0 such that for every n ≥ n0, there exists an instance of size n such that the algorithm takes at least cf(n) steps.
For the second algorithm shown below, give a lower bound for the running time.
Algorithm 1 Stars
1: for i = 1,…,n do
2: print ”*” i times 3: end for
2n n10
Problem 3
2
Algorithm 2 Check Numbers
1:
2: 3: 4: 5: 6: 7: 8: 9:
10: 11:
procedure CheckNumbers(A,B)
◃ A and B are two lists of integers with |A| = n ≤ |B| = m
count = 0
for
end for
end procedure
i = 1,…,n do for j = i . . . m do
if A[i] ≥ B[j] then count = count +1 break
end if end for
Problem 6
An undirected graph G = (V,E) is said to be bipartite if its vertex set V can be partition into two sets A and B such that E ⊆ A × B. Design an O(n + m) algorithm to test if a given input graph is bipartite using the following guide:
1. Suppose we run BFS from some vertex s ∈ V and obtain layers L1,…,Lk. Let (u,v) be some edge in E. Showthatifu∈Li andv∈Lj then|i−j|≤1.
2. Suppose we run BFS on G. Show that if there is an edge (u, v) such that u and v belong to the same layer then the graph is not bipartite
3. Suppose G is connected and we run BFS. Show that if there are no intra-layer edges then the graph is bipartite
4. Put together all the above to design an O(n + m) time algorithm for testing bipartiteness.
Problem 7
Given an array A consisting of n integers A[0], A[1], . . . , A[n − 1], we want to compute the upper triangle
matrix
C[i][j]= A[i]+A[i+1]+···+A[j] j−i+1
for 0 ≤ i ≤ j < n. Consider the following algorithm for computing C: Algorithm 3 summing-up
1: 2: 3: 4: 5: 6: 7: 8: 9:
function summing-up((A)) for i=0,...,n−1do
for j=i,...,n−1do
add up entries A[i] through A[j] and divide by j − i + 1 store result in C[i][j]
end for end for
return C end function
1. Using the O-notation, upperbound the running time of summing-up. 3
2. Using the Ω-notation, lowerbound the running time of summing-up.
Problem 8
[Optional] Give an O(n) time algorithm to detect whether a given undirected graph contains a cycle. If the answer is yes, the algorithm should produce a cycle. (Assume adjacency list representation.)
Problem 9
[COMP3927 only] Recall the streaming algorithm for majority. Let k > 0 be the value of the counter at the end of the stream. In the lecture, we saw an example where k = 1 and yet there is no absolute majority. For what values of k can we be sure that there is an absolute majority?
4