CS30053 Foundations of computing
Autumn 2004, L-T-P: 3-0-0, Credits: 3
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.
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.
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