Algorithms and Data Structures 2020

Week 3. Complexity Analysis

Algorithms and Data Structures

4 Week 3. Complexity Analysis

Reading 3 Goodrich, Tamassia, & Goldwasser: Chapter 4

4.1 Key Concepts

   4.1.1 Complexity
   4.1.2 Recursion

4.1.1 Complexity

Induction and Deduction
Common functions with examples
Algorithm Theory focuses on infinitely large datasets: asymptotics
Recursion and loop
Mathematical Induction and Loop Invariants
Computing Model

4.1.2 Recursion

TODO video on Induction and recursion

4.2 Projects and Exercises

   4.2.1 Wednesday Group Work
   4.2.2 Compulsory Assignment
   4.2.3 Practice Problems

This week, I ask you not to start with the compulsory projects. The Wednesday Group Work section contains two warm-up problems, and then a discussion exercise which I want to discuss in the plenary debrief, after your group discussion.

You should be able to complete those three problems in the group session, and you may have time to proceed with the compulsory projects.

4.2.1 Wednesday Group Work

Problem 4.1 (Goodrich et al R-4.1 rephrased) The number of operations executed by algortihms A and B is 8n log n and 2n3, respectively. Determine n0 such that A| is better than B for n n0

Problem 4.2 (Goodrich et al R-4.7 rephrased) Order the following functions by asymptotic growth rate:

4n log n + 2n, 265, 2log n, 4n + 100 log n, 4n, 1.1n,n2 + 10n,n3,n log n,n32.

Problem 4.3 (Goodrich et al C-4.43 rephrased) Claim: In any flock of sheep, all sheep have the same colour

An alleged proof goes as follows.

Base Case: n = 1 A single sheep clearly has the same colour as itself.

Induction Step: Consider a flock of n > 1 sheep. Take one sheep a out. The remaining n 1 sheep have the same colour by induction. Now, replace a and take a different sheep b out. Again, the remaining n 1 sheep have the same colour by induction. Hence, all the sheep in the flock have the same colour.

In reality, we know that a flock with black and white sheep has been observed, so what is wrong with the argument?

4.2.2 Compulsory Assignment

Problem 4.4 (Goodrich et al C-4.49 rephrased) Let p(x) be a polynomial, i.e.

p(x) = i=0na ixi.

Describe an O(n2)-time algorithm to compute p(x).
Improve the algorithm to (n log n) time by improving the calculation of xi.
Now consider rewriting as
p(x) = a0 + x(a1 + x(a2 + x(a3 + + x(an1 + xan)))).

How many arithmetic operations do you need to calculate this (in Big-O notation).

Problem 4.5 (Goodrich et al R-4.31 rephrased) Al and Bob are arguing about their algorithms. Al claims his O(n log n)-time algorithm is always faster than Bob’S O(n2)-time algorithm. To settle the issue they run a set of experiments. To Al’s dismay, they find that if n < 100, the O(n2)-algorithm runs faster, and only when n 100 is the O(n log n)-time one better. Explain how this is possible.

4.2.3 Practice Problems

Problem 4.6 (Goodrich et al C-4.35 rephrased) Show that

i=1ni2 = O(n3).

Problem 4.7 (Goodrich et al R-4.28 rephrased) Given an n-element array X. Algorithm A chooses log n elements from X at random and executes an O(n)-time calculation for each. What is the worst-cae running time of B.

Problem 4.8 (Goodrich et al R-4.30 rephrased) Given an n-element array X. Algorithm D calls Algorithm E on each element Xi. Algorithm E runs in O(i) time when called on Xi. What is the worst-case run time of D?

Problem 4.9 (Goodrich et al P-4.55 rephrased) Make an experimental analysis to test the hypothesis that Java’s Array.sort() method runs in O(n logn) time on average.

Proof techniques C-4.x