Basic Information


This is a variant of the original course with the same course number - titled Mathematical Concepts for Computer Science. The main change has been that the course syllabus now does *not* include basic linear algebra and probability.

Course Objectives:

The aim is to help the student to gain the ability to use some of the fundamental methods of logic and combinatorics in Computer Science. The course is intended to provide the foundations to mathematical rigor, fundamental methods of logic and combinatorics in Computer Science.

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, Cantors diagonalization. (3+1) Undecidability : Turing Machines, Church-Turing Thesis. Notion of Computation and decidability, Undecidability of the Halting Problem. Consequences to the Program Verification Proble m. (6 + 2)
  • Counting and Combinatorics :Basics: Pigeonhole Principle and applications (quick review) (2+1).
    Counting methods: Principle of Inclusion Exclusion, Proving Combinatorial Identities, Combinatorial Arguments, Permutations, Derangements. (4+1)
    Recurrence: Linear recurrences, 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, Lagranges theorem. Introduction to Polyas theory of counting. (8 + 3)

Text Books & References

  • 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.
  • 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.

Course Load

This course is assigned 12 credits with 4 lectures per week. Total number of classes : 56 Lectures + 5 evaluation meetings in the whole semester. Expected offline student load: 8 hours per week.

Pre-requisites & Learning Outcomes:

This course will assume and build upon undergraduate discrete mathematics course.
We will be working on the top five levels of Blooms Taxonomy. After completing the course, the student will be able to (in other words, this is what the exams will test):
At the end of the course, we expect the attendees to
  • 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.

Evaluation Scheme

The evaluation will be based on three categories of activities.
  • Two quizzes - 20% x 2 = 40%
  • Four "short exams" - 10% x 2 = 20%
  • End-semester examination - 40% x 1 = 40%
The dates of these activities are also frozen to avoid any kind of time conflict. In addition to these, the activities will also include periodic assignments. You can find a detailed schedule in activities page and meetings page.