Combinatorics and Algorithms Design

A university-level course pairing combinatorial mathematics with algorithm design. The first half covers counting principles, permutations and combinations, generating functions, integer partitions and Ferrers diagrams, linear homogeneous recurrence relations and the Fibonacci sequence, Catalan and Stirling numbers, derangements, the inclusion-exclusion and pigeonhole principles, and optional material on permutation groups, Burnside's lemma and Pólya's theorem. The second half introduces algorithm complexity and asymptotic analysis, then incremental algorithms and loop invariants (insertion sort, the Dutch national flag problem), divide and conquer (merge sort, order statistics, substitution, recursion tree and master methods), randomized algorithms (hiring problem, randomized select), and dynamic programming (maximum subarray, knapsack, matrix chain multiplication). Weekly homework, demo sessions and a final exam are included. Suited to students of computer science and mathematics with basic mathematical maturity.