Goals for Test 2
Day: 11th of December
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 - Linear Algorithms for the Selection Problem
- Understanding the randomized version of QuickSelect
- Understanding the deterministic version (median of medians)
Example exercises: applying the deterministic version to an array; question 1 from homework #3; Some CLRS Book exercises: 9.2-1, 9.2-4, 9.3-1, 9.3-2, 9.3-3, 9.3-5, 9.3-7, 9.3-8, 9.3-9.
Group 2 - Sorting in Linear Time
- Understanding how Counting Sort works and its complexity
- Understanding how Radix Sort works and its complexity
- Understanding how Bucket Sort works and its average-case complexity
Example exercises: showing how a certain algorithm works; questions 2 and 3 from homework #3; Some CLRS Book exercises: 8.2-1, 8.2-2, 8.2-3, 8.3-1, 8.3-3, 8.3-4, 8.4-1, 8.4-2.
Group 3 - String Matching
- Understanding what the string matching problem is about
- Understanding how naive string matching works and its complexity
- Understanding how a deterministic finite automaton (DFA) works, and how it could match a pattern
- Understanding the Knuth-Morris-Pratt algorithm and its complexity
- Understanding the Rabin-Karp algorithm and its expected complexity
- Understanding the concepts of tries and compressed prefix tres
- Understanding the concept of suffix trees, suffix arrays and LCP arrays, their complexity and the kind of problems they can solve
Example exercises: questions 4, 5 and 6 from homework #3; showing how a certain string matching algorithm works for a specific example instance; Some CLRS Book exercises: 32.1-1, 32.1-4, 32.2-1, 32.2-2, 32.2-3, 32.3-1, 32.3-2, 32.3-3, 32.3-1, 32.3-5, 32.4-1, 32.4-3, 32.4-7.
Group 4 - Greedy Algorithms
- Understanding the concepts of greedy algorithms, optimal substructure and greedy choice property.
- Understanding the greedy ideas of the coin change, fractional knapsack, interval scheduling and minimum spanning trees (using Prim's algorithm).
- Understanding the concept of an heap, its complexity and how its operations work.
- Proving that a certain greedy choice is always correct (or giving counter-examples that show it is incorrect)
Example exercises: applying a greedy algorithm to a specific instance; producing an instance for which a certain greedy algorithm does not output an optimal answer; question 1 from homework #4; Some CLRS Book exercises: 16.1-2, 16.1-3, 16.1-4, 16.2-1, 16.2-3,.
Group 5 - Dynamic Programming
- Understanding the concepts of dynamic programming, optimal substructure, overlapping subproblems, bottom-up and top-down (memoization) strategies
- Understanding the dynamic programming ideas of fibonacci sequence, number pyramid, LIS, 0-1 knapsack and variants, edit distance and LCS.
Example exercises: writing the recurrence describing a dynamic programming solution, applying DP to a certain instance, question 2 from homework #4; Some CLRS Book exercises: 15.1-5, 15.4-1, 15.4-2, 15.4-4, 15.4-5.
Group 6 - NP-completeness
- Understanding the concepts of classes P, NP, NP, coNP, NP-complete and NP-hard.
- Understanding the differences and similarities between an optimization/search problem and the correspondent decision problem.
- Understanding the concept of problem reduction and knowing how to make (simple) reductions between problems
- Knowing the CIRCUIT-SAT, SAT, 3SAT, IndSet, VertexCover and Clique problems.
Example exercises: proving a problem is NP-complete, question 3 from from homework #4.
)