University of Waterloo
CS240 Winter 2020
Assignment 1
Due Date: Wednesday, January 29 at 5:00pm
Please read http://www.student.cs.uwaterloo.ca/~cs240/w20/guidelines.pdf for
guidelines on submission. This assignment contains both written problems and a pro-
gramming problem. Submit your written solutions electronically as a PDF with file name
a1Submit.pdf using MarkUs. We will also accept individual question files named a1q1.pdf,
a1q2.pdf, ... , a1q7.pdf if you wish to submit questions as you complete them.
Problem 7b contains a programming question; submit your solution electronically as a file
named teampq.cpp.
Note: you may assume all logarithms are base 2 logarithms: log = log2.
Problem 1 [4+4+4+4=16 marks]
Provide a complete proof of the following statements from first principles (i.e., using the
original definitions of order notation).
a) 27n7 + 17n3 log n + 2020 is O(n9)
b) n2(log n)1.0001 is Ω(n2)
c) n
2
n+logn
is Θ(n)
d) nn is ω(n20)
Problem 2 [4+4+4+4=16 marks]
For each pair of the following functions, fill in the correct asymptotic notation among Θ,
o, and ω in the statement f(n) ∈ unionsq(g(n)). Prove the relationship using any relationship or
technique that described in class.
a) f(n) = n2 + 27n log n + 2020 versus g(n) = n2 log n + 2020
b) f(n) = 10n + 99n10 versus g(n) = 75n + 25n27
c) f(n) =
√
n versus g(n) = (log n)7
d) f(n) = log log n versus g(n) = (log log log n)8
1
Problem 3 [4+4+4+4=16 marks]
Prove or disprove each of the following statements. To prove a statement, you should provide
a formal proof that is based on the definitions of the order notations. To disprove a statement,
you can either provide a counter example and explain it or provide a formal proof. All
functions are positive functions.
a) f(n) 6∈ o(g(n)) and f(n) 6∈ ω(g(n))⇒ f(n) ∈ Θ(g(n))
b) f(n) ∈ Θ(g(n)) and h(n) ∈ Θ(g(n))⇒ f(n)
h(n)
∈ Θ(1)
c) f(n) ∈ Θ(g(n))⇒ 2f(n) ∈ Θ(2g(n))
d) min(f(n), g(n)) ∈ Θ
(
f(n)g(n)
f(n)+g(n)
)
Problem 4 [2+4=6 marks]
Dr. I. M. Smart has invented a new class of functions, denoted O′(f): A function f(n) is in
O′(g) if there is a constant c > 0 such that f(n) ≤ cg(n) for all n > 0. All functions map
positive integers to positive integers.
a) Prove that f(n) ∈ O′(g(n)) implies that f(n) ∈ O(g(n)).
b) Prove that f(n) ∈ O(g(n)) implies that f(n) ∈ O′(g(n)).
Problem 5 [4+4+4+6(+4)=18(+4) marks]
Analyze the following piece of pseudocode and give a tight (Θ) bound on the running time
as a function of n. Show your work. A formal proof is not required, but you should justify
your answer (in all cases, n is assumed to be a positive integer).
a) x = 0
for i = 1 to n * n * n do
for j = 1 to i * i do
x = x * 2
b) x = 1
y = 0
for i = 1 to n do
x = x * 5
for j = 1 to x do
y = y + 1
2
c) x := -42
y := 1
while y < 5n do
z := n * n * n
while z > y do
x := 2 - x
z := z - y
y := y + 5
d) Consider the following (rather strange) code-fragment:
mystery (int n) {
// pre: n >= 2
compute L := floor( log (n) )
if L is even
print all subsets of {1,...,L}
else
print all subsets of {1,...,2L}
}
For example, for n = 17, we have L = blog(17)c = 4, so the code prints all 16 subsets
of {1, 2, 3, 4}.
Let f(n) be the run-time of this code. You may assume that computing log(n) takes
Θ(1) time, and printing the subsets of {1, . . . , k} takes Θ(2k) time.
i) Find a constant d1 and prove that f(n) ∈ O(nd1). Your d1 should be as small as
possible, but you need not prove that it is minimal.
ii) Find a constant d2 and prove that f(n) ∈ Ω(nd2). Your d2 should be as big as
possible, but you need not prove that it is maximal.
iii) Bonus: Argue that there cannot exist a constant d such that f(n) ∈ Θ(n2).
Problem 6 [4 or 4(+2), graded out of 4 marks]
An almost-heap is a binary tree that satisfies all heap-properties except that at one item the
order-property may be violated. Thus, it consists of an array A and one index i such that
A[j] < A[parent(j)] for all j 6= i. In the example below, the violated order-property occurs
between 31 and 40.
3
42
31
22
20 13
40
37 39
36
28
7
27
Solve one of the following problems:
Note: If you give two solutions, we will only grade the first solution presented.
1) [4 marks] Show how to turn an almost-heap into a heap in time O(log2 n).
2) [4(+2) marks] Let h be the height of the almost-heap and ` be the level that contains
node i. Show how to turn an almost-heap into a heap in time O((` + 1)(h− ` + 1)).
Use the following notation: the root of T is node root(T ), and the rightmost node
in the last layer is last(T ). The key stored in a node i is denoted by key(i); the parent, left
and right child of a node i is denoted parent(i), left(i) and right(i) respectively.
4
Problem 7 [3+10=13 marks]
a) Show that an arbitrary item can be removed from a heap in O(log n) time, if the item’s
index into the heap is known. Specifically, give an algorithm heapRemove(h, i) that
removes the element at index i from heap h. Justify your algorithm’s running time.
b) Consider the following C++ class:
class Team {
int wins;
int losses;
string name;
// You may add fields/methods/constructors/destructor as necessary
};
We wish to build a data structure that allows for efficient retrieval of the team with the
most wins and also for efficient retrieval of the team with the fewest losses. Essentally
we want a priority queue that supports two different priority measures. Provide an
implemenation of the following class:
class TeamPQ {
// add fields/methods/constructors/destructor as necessary
public:
void insert(const Team &t); // O(log n) time
const Team &findMaxWins() const; // O(1) time
const Team &findMinLosses() const; // O(1) time
void removeMaxWins(); // O(log n) time
void removeMinLosses(); // O(log n) time
};
Implement this class in C++ and submit electronically (the remainder of these instruc-
tions pertain to the programming portion of this assignment).
Provide a main function that accepts the following commands from stdin (you may
assume that all inputs are valid):
• i wins losses name - inserts a team with the given wins, losses, and name into
the priority queue. You may assume that name contains no whitespace.
• pw - prints the name of the team with the most wins, without removing it from
the priority queue. Prints nothing if the priority queue is empty.
5
• pl - prints the name of the team with the fewest losses, without removing it from
the priority queue. Prints nothing if the priority queue is empty.
• rw - removes the team with the most wins from the priority queue and prints
nothing. Does nothing if the priority queue is empty.
• rl - removes the team with the fewest losses from the priority queue and prints
nothing. Does nothing if the priority queue is empty.
All output is printed to stdout. The program terminates when eof is encountered.
For example, the following input:
i 15 5 leafs
i 13 3 canucks
i 12 7 canadiens
i 10 10 jets
i 0 14 oilers
pw
pl
rw
pw
rl
pl
i 20 1 leafs
pw
pl
should produce the following output:
leafs
canucks
canucks
canadiens
leafs
leafs
Place your entire program in the file teampq.cpp
6