Note : Course details updated in Jul 2015..
Course title also changed from "Mathematical Concepts of Computer Science"(MCCS) to "Logic and Combinatorics for Computer Science"(LCCS).
Course Objectives:
The course is intended to provide the foundations to mathematical rigor that are used in most areas of Computer Science and limitations of Computation. The topics include Logic, Basic Combinatorics and elements of Computability.
Syllabus
Language of Math – Sets, relations, functions (quick review) - 1
Logic : Propositional Logic, Predicate and First order Logic, Examples, Soundness
and Completeness. Second Order Logic. Incompleteness theorems.
Further extensions of logic (MSO, Temporal etc). Subsets of first order logic. Example Applications. (7 + 2)
Proofs: Mathematical Arguments and Argument Forms, Inference Rules, Notion of a
Proof and validity of an argument, Various Proof techniques and examples,
Identifying fallacies. (7+3)
Infinite Sets: Countable and uncountable sets, Cantor’s diagonalization. (3+1)
Undecidability : Turing Machines, Church-Turing Thesis. Notion of Computation and decidability, Undecidability of the Halting Problem. Consequences to the Program Verification Problem. (6 + 2)
Combinatorics – Basics: Pigeonhole Principle and applications (e.g., Ramsey Theorem) (2+1)
Counting methods: Principle of Inclusion Exclusion, Proving Combinatorial Identities, Combinatorial Arguments, Permutations, Derangements. (4 + 1)
Recurrence: Linear recurrences, method of roots. Generating Functions. Examples (2 + 1)
Structured Sets: Posets and Lattices, Fixed Point Theorems (Knaster-Tarski and Polya), Monoids, Semigroups, Groupoids and Groups, Examples, Subgroups, Cosets, Lagrange’s theorem. Introduction to Polya’s theory of counting. (8 + 3)
Text Books
- Discrete Mathematics and its Applications – Kenneth H. Rosen 7th Edition -Tata McGraw Hill Publishers - 2007
- Introduction to Automata Theory, Languages and Computation - Hopcroft, Motwani, and Ullman - Pearson Publishers
- A Mathematical Introduction to Logic - Herbert B Enderton, Pearson Publishers.
References
- Combinatorics: Topics, Techniques, Algorithms by Peter J. Cameron, Cambridge University Press, 1994 (reprinted 1996).
- Concrete Mathematics – Ronald Graham, Donald Knuth, and Oren Patashnik, 2nd Edition - Pearson Education Publishers - 1996.
Learning Outcomes:
Be able to Comprehend and Evaluate mathematical arguments revolving around computations and programs. Be conversant with the Mathematical Rigor that is necessary for computer science and be able to come up with rigorous arguments.
Be able to Identify and apply underlying combinatorial structures and analyze them.
Know the limitations of computations and be able to identify infeasibilities and limitations of computational problems.
