CS30053 Foundations of computing

Autumn 2004, L-T-P: 3-0-0, Credits: 3

Class timings

Slot: C
Regular: M 9:30-10:25, W 8:30-9:25, Th 9:30-10:25
Reserve: W 7:30-8:25
Room No: 120, CSE building


This course is a conglomeration of the two core courses CS 21001 and CS 21004 for CSE majors. The official syllabus for this course can be found here or here. I have broken it up and expanded the parts in the following form.

1. Set theory and logic  

Logic and propositions, sets, set operations, functions, relations, equivalence relations, partial orders.

2. Analysis of algorithms  

Time complexity, intractable problems, the big-O notation, mathematical induction, recursive algorithms, correctness of algorithms.

3. Combinatorics  

Pigeon-hole principle, permutations and combinations, principal of inclusion-exclusion, generating functions, linear recurrences and their solutions, divide-and-conquer relations.

4. Graphs and trees  

Paths and cycles, shortest path, Eulerian and Hamiltonian paths and cycles, planar graphs, trees, tree traversal, spanning trees, minimum spanning trees.

5. Automata theory  

Languages and grammars, finite state machines, Turing machines, undecidable problems.

6. Algebraic structures  

Groups and subgroups, cosets and quotient groups, group homomorphism, rings, integral domains, fields, ideals, ring homomorphisms, polynomial rings.


  1. K H Rosen, Discrete mathematics and its applications, 5th edition, Tata McGraw-Hill Publishing Company, 2002, Rs 365.
    Also visit this site. Take care not to buy the 4th (or earlier) edition.

  2. J P Tremblay and R Manohar, Discrete mathematical structures with applications to Computer Science, Tata McGraw-Hill Publishing Company, 1999, Rs 250.
  3. C L Liu, Elements of discrete mathematics, 2nd edition, Tata McGraw-Hill Publishing Company, 2000, Rs 175.
  4. N L Biggs, Discrete mathematics, 2nd edition, Oxford Indian edition, 2003, Rs 245.
  5. M O Albertson and J P Hutchinson, Discrete mathematics with algorithms, John Wiley & Sons (Asia) Pte Ltd, 2001, around Rs 300.

Neither of these books fully covers the entire official syllabus. I plan to follow Rosen's book because its overlap with the syllabus seems maximal. The book does not cover algebraic structures, but I doubt if time will permit us to study groups, rings and fields. The first five topics already make a decent syllabus. In case I cover algebra, I will supply supplementary hand-outs.

Tentative test schedule

Practice exercises