Recurrence, generating functions, inclusion-exclusion principle, divide-and-conquer, application to algorithm design.
Combinatorics, permutations, combinations, selections, pigeonhole principle, inclusion-exclusion.
Sections 5.3, 8.1, 8.2 (Recurrence systems), 8.3-8.6 (divide and conquer, inclusion-exclusion, generating functions), 5.4 (Algorithm design)
Textbook 50 pages
Recurrence systems, solutions of recurrence systems, classification of recurrence equations, uniqueness of solutions.
Lecture notes
Principle of superposition; methods of: iteration, substitution, characteristic roots, undetermined coefficients. Higher-order recurrence systems.
Generating functions, solving recurrence systems with generating functions, counting with generating functions.
Inclusion-exclusion principle, derangements.
Algorithm analysis by recurrence relations, divide-and-conquer and recursive algorithms, generating functions.
Screencast on inclusion-exclusion principle (Trevor)
Screencast 18 minutes TrevTutor
Screencast on inclusion-exclusion problems (Trevor)
Screencast 28 minutes TrevTutor
Creating recurrence relations, initial conditions (Rosen Section 8.1)
Problems
Solutions
Determining linear homogeneous recurrence relations and their degree, solving recurrence relations (Rosen Section 8.2)
Providing Big-O estimates, designing divide-and-conquer algorithms, using the master theorem (Rosen Section 8.3)
Using the inclusion-exclusion principle (Rosen Section 8.5)
More applications of the inclusion-exclusion principle (Rosen Section 8.6)
