CS30053 Foundations of computing, Autumn 2004

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

Syllabus

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.

Textbooks

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.
J P Tremblay and R Manohar, Discrete mathematical structures with applications to Computer Science, Tata McGraw-Hill Publishing Company, 1999, Rs 250.
C L Liu, Elements of discrete mathematics, 2nd edition, Tata McGraw-Hill Publishing Company, 2000, Rs 175.
N L Biggs, Discrete mathematics, 2nd edition, Oxford Indian edition, 2003, Rs 245.
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

Class test I: August 26, 2004, 6:30pm onwards, weightage: 10%.
Questions: ps.gz, pdf.
Solutions: ps.gz, pdf.
Mid-sem test: 21.09.2004 FN (9:00-11:00), S301 (B). Weightage: 30%.
Questions: ps.gz, pdf.
Solutions: ps.gz, pdf.
Class test II: Cancelled.
End-sem test: 27.11.2004 FN (8:00-11:00), CSE 120. Weightage: 60%.
Questions: ps.gz, pdf.
Solutions: ps.gz, pdf.

Practice exercises

Set 1 (on logic and set theory): ps.gz, pdf.
Set 2 (on algorithms and complexity): ps.gz, pdf.
Set 3 (on elementary counting techniques): ps.gz, pdf.
Set 4 (on advanced counting techniques): ps.gz, pdf.
Set 5 (on modeling computations): ps.gz, pdf.

Home

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.