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
- 1.
- Induction and Deduction
- 2.
- Common functions with examples
- 3.
- Algorithm Theory focuses on infinitely large datasets: asymptotics
- 4.
- Big-O
- 5.
- Recursion and loop
- 6.
- Mathematical Induction and Loop Invariants
- 7.
- Computing Model
4.1.2 Recursion
- 1.
- TODO video on Induction and recursion
4.2 Projects and Exercises
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 and , respectively. Determine such that A| is better than B for
Problem 4.2 (Goodrich et al R-4.7 rephrased) Order the following functions by asymptotic growth rate:
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: A single sheep clearly has the same colour as itself.
Induction Step: Consider a flock of sheep. Take one sheep out. The remaining sheep have the same colour by induction. Now, replace and take a different sheep out. Again, the remaining 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 be a polynomial, i.e.
- 1.
- Describe an -time algorithm to compute .
- 2.
- Improve the algorithm to time by improving the calculation of .
- 3.
- Now consider rewriting as
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 -time algorithm is always faster than Bob’S -time algorithm. To settle the issue they run a set of experiments. To Al’s dismay, they find that if , the -algorithm runs faster, and only when is the -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
Problem 4.7 (Goodrich et al R-4.28 rephrased) Given an -element array . Algorithm A chooses elements from at random and executes an -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 -element array . Algorithm D calls Algorithm E on each element . Algorithm E runs in time when called on . 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 time on average.
- 1.
- Proof techniques C-4.