Syllabus from January 2005

2 Credits

Syllabus

Recurrence relations, Three Recurrent Problems, More Recurrences, Divide and Conquer, Generating Functions, Exponential Generating Functions, Applications, Combinatorial Identities, Linear Equations, Partitions, Recurrence Relations, Solving recurrencies, Linear Homogeneous Recurrences, Linear Non-homogenous Recurrences, Method of Telescoping sums, Method of Iteration, Method of Substitution, Graphs, Regular Graphs, Subgraphs, Connected Graphs, Paths, Circuits And Cycles, Components, Connectivity, Bipartite Graphs, Trees, Eulerian Graphs, Fleury’s Algorithm, Hamiltonian Graphs, Travelling Salesperson Problem, Graphs Coloring and Planar graphs, Vertex Colourings, Definition And Examples, Bounds For Chromatic numbers, Planar Graphs, Map Colouring Problem, Edge Colouring, Automata, grammars and languages, Sequential Circuits and Finite-State Machine, Finite-State automata, Languages and Grammars, No-deterministic Finite-State Automata, Relationships Between Languages and Automata.