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
Problem 3
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
Which of the following is largest asymptotically
1
Problem 4
log3 n, log2 n, log10 n
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
Algorithm 2 Check Numbers
Problem 6
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
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:
2
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.
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.
3