CS212

COMBINATORICS AND GRAPH THEORY

Objectives

  • To introduce basic combinatorics and graph theory

 

Outcomes

  • Ability to apply combinatorial ideas in other mathematical arguments in other subjects e.g., analysis of algorithms, queueing theory, etc.
  • Ability to comprehend graph theory fundamentals and tackle problems in dynamic programming, network flows, etc.

 

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

TEXT BOOKS

  1. J. H. Van Lint and R. M. Wilson, “A course in Combinatorics”, 2 nd edition, Cambridge Univ. Press, 2001
  2. G. Chartrand and P. Zhang, “Introduction to Graph Theory”, McGraw-Hill, 20