Algorithm Design COMP3027/3927 Tutorial questions The University of Sydney 2019 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?
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
Solution: Answer should be:
√nn√33 n, log2 n, logn,n,nlogn, n ,n
Sort the following function in decreasing order of asymptotic growth n 2n 1
n1.5,2n, , ,n!,1.5n,2log2 n,nlog2 n 2n n10
1
Solution: Answer should be:
2n 1n
2n
n!,2n, ,1.5n,n1.5,2log2 n,nlog2 n , n10
Problem 3
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. The upper bound captures the worst case running time of an algorithm. Some instances might require the algorithm to perform more steps than others. Some instances might allow the algorithm to terminate faster. A lower bound for the running time is a “best-case” running time in the worst-case. If an algorithm is Ω(f(n)), for example, then there exists an instance that will take at least f(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
Solution: They are all equal. This is because:
logb a = logd a logd b
Solution: Proof is by induction on n.
Base case: If n = 1 then the claim is trivially true.
Induction hypothesis: Assume that the sum of the first n natural is n(n + 1)/2.
Induction step: Next we want to prove the statement for n+1. From the definition of S(n) we know S(n+1) = S(n)+n+1, and from the induction hypothesis we know S(n) = n(n+1)/2, and therefore S(n + 1) = S(n) + n + 1 = n(n + 1)/2 + n + 1 = (n + 2)(n + 1)/2.
Solution: first iteration prints 1 star, second prints two, third prints 3 and so on. Total
number of stars is
n n(n + 1) 2
1 + 2 + · · · + n
j = 2 ∈ O(n )
j=1
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
Solution: An upper bound is O(n · m). The lower bound is Ω(n · m). Ask the students to come up with a specific example input for this (which is easy).
Problem 6
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. 2. Using the Ω-notation, lowerbound the running time of summing-up.
Solution:
1. Thenumberofiterationsisn+n−1+···+1=n,whichisboundedbyn2. Inthe 2
iteration corresponding to indices (i, j) we need to scan j − i + 1 entries from A, so it takes O(j − i + 1) = O(n). Thus, the overall time is O(n3).
2. In an implementation of this algorithm, Line 3 would be computed with a for loop; when i < 1 n and j > 3 n, this loop would iterate least n/2 times, which takes Ω(n)
44
time. There are n2/16 pairs (i,j) of this kind, which is Ω(n2). Thus, the overall time
is Ω(n3).
3
Problem 7 [COMP3927 only]
Come up with an implementation of the Gale-Shaply algorithm for finding a stable matching that keeps track of the number of proposals made during the execution.
1. Design a generic instance where the number of proposals is O(n).
2. Design a generic instance where the number of proposals is Ω(n2). In both cases, n is the number of men/women in the instance.
Solution:
1. We only sketch the instance. Consider the following preference lists
m1 w1 w2 ··· wn−1 m2 w2 w3 ··· wn
.
wn w1
w1 m1 m2 ··· mn−1 mn w2 m1 m2 ··· mn−1 mn
.
(1)
(2)
wn m1 m2 ··· mn−1 mn Each man proposes to a free woman, so there only n proposals.
mn wn w1 ··· wn−2 wn−1
2. We only sketch the instance. Consider the following preference lists
m1 w1 w2 m2 w1 w2
.
mn w1 w2
··· wn−1 wn ··· wn−1 wn
··· wn−1 wn
w1 m1 m2 w2 m1 m2
.
wn m1 m2
··· mn−1 mn ··· mn−1 mn
··· mn−1 mn
Imagine mn proposes first, followed by mn−1 and so on up to m1. Each man proposes to w1, who progressively gets a better partners and ends up with m1. This involves n proposals.
In a second round, mn proposes to w2, followed by mn−1, and so on up to m2. Again, w2 gets progressively better partners and ends up with m2. This involves another n−1 proposals.
This keeps going on until mn finally proposes to wn and the algorithm terminates, having made a total of n + n − 1 + · · · + 1 = Ω(n2) proposals.
4