Objectives
Outcomes
Unit – I
Scope of the course, Application areas in CS, A feel of some advanced problems in Combinatorial Optimization/ Graph Theory, Sum/Product rules, Power set - algorithm, Bijections/Mapping/Examples Permutations and combinations, examples, Combinatorial ideas, Pascal Triangle Counting principles via examples, Insertion sort, Stirling numbers
Unit – II
Average case analysis and combinatorial ideas Double counting - Fubini's method, PHP principle, various illustrations Stirling numbers of II kind, Combinatorial identities, Binomial theorem Multinomial theorem, P(n,t1, - - - ,tp) notation, Euler PHI-function, Properties, Steps in Sieve of Eratosthenes
Unit – III
Inclusion/Exclusion Principle, Exercises, Derangements, IMO type problems, Ramsey Theory, Partition problems, Ferrar Diagrams Recurrences - Examples in CS, Substitution methods, Recurrence trees, D&C Solving Fibonacci series - GF idea, Difference equations, examples. Homogeneous case Inhomogeneous case
Unit – IV
Basics of GFs, Review problems, Examples, GF manipulations Coupled difference equations, Graph theory fundamentals, Representations, Examples in CS - MST review, Party problem Distance in graphs, Floyd-Warshall algorithm, Operations in graphs, Meanings of products
Unit – V
Regular graphs, related results, Coloring, Cliques and independent sets, Trees, definitions, related problems, properties, Network Flows, Definitions, Related discussions and Max-Flow Min-Cut Theorem, Introduction to optimization problems in CS, LP formulation, Branch-andBound
