Goals for Test 1
Day: 6th of November
Time: 10:00
Duration: 2h30m
Location: FC6 013 (DCC Building, ground floor)
Here is a short list of goals for the first test. You should be familiar with the examples given in classes, with the lecture slides and with the homework exercises given.
During the test you will be given the following auxiliary material: auxiliary material PDF
(no need to "memorize": the main goal is to understand!)
Group 1 - Correctness and Loop Invariants
- Understanding the concept of a loop invariant
- Being able to prove that a simple algorithm using loops is correct using invariants
Example exercises: all questions from from Exercises #01.
Group 2 - Asymptotic Analysis
Notation
- Understanding what O, o, Ω, ω and Θ means
- Classifying pairs of functions into their correspondent notation
- Reasoning about sentences involving this notation
- Proving something using the formal definitions
- Determining the asymptotic cost of a simple algorithm
Example exercises: all questions from Exercises #02; questions 2 and 3 from homework #1.
Recurrences
- Understanding the basics of the divide-and-conquer paradigm
- Writing the recurrence describing an algorithm
- Understanding methods for solving recurrences: unrolling, substitution, recursion tree and master theorem
- Solving recurrences
Example exercises: all questions from Exercises #03; questions 4 and 5 from from homework #1.
Group 3 - Amortized Analysis
- Understanding the concept of amortized analysis
- Understanding methods for doing amortized analysis: aggregation, accounting and potential methods
- Determining the amortized cost of an operation for a simple data structure
Example exercises: all questions from from Exercises #04; questions 6 and 7 from from homework #1.
Group 4 - Probabilistic Analysis and Randomized Algorithms
- Understanding basic probability concepts (including linearity of expectation)
- Understanding the notion of expected running time
- Understanding the quicksort algorithm (both naive and randomized versions)
- Understanding the concept of Las Vegas and Monte Carlo randomized algorithms, and how one can improve the probability of success using amplification
- Doing a probabilistic analysis of simple randomized algorithms
Example exercises: questions 1 and 2 from homework #2. Simple exercises with dice we did on the class. Showing expected runtime of a randomized version of quicksort. Showing expected probability of success for randomized min-cut.
Group 5 - Lower Bounds
- Understanding the concept of lower bounds
- Understanding the decision tree model
- Understanding the information theory argument and the concept of adversarial strategies
- Proving lower bounds for simple problems
Example exercises: question 3 from homework #2. Showing why comparison-based sorting is Ω(n log n) or why determining the maximum element of a set is Ω(n).
)