CS60005: Foundations Of Computing Science

CS60005
Course name	Foundations Of Computing Science
Offered by	Computer Science & Engineering
Credits	4
L-T-P	3-1-0
Previous Year Grade Distribution
1 EX A B C D P F
Semester	Autumn

Syllabus

Syllabus mentioned in ERP

Discrete Structures -- Sets, Relations and Functions; Proof Techniques, Algebraic Structures, Morphisms, Posets, Lattices and Boolean Algebras. Logic -- Propositional calculus and Predicate Calculus, Satisfiabiliy and validity, Notions of soundness and completeness Languages & Automata Theory -- Chomsky Hierarchy of Grammars and the corresponding acceptors, Turing Machines, Recursive and Recursively Enumerable Languages; Operations on Languages, closures with respect to the operations. Computability -- Church-Turing Thesis, Decision Problems, Decidability and Undecidability, Halting Problem of Turing Machines; Problem reduction (Turing and mapping reduction). Computational Complexity -- Time Complexity -- Measuring Complexity, The class P, The class NP, NP-Completeness, Reduction, co-NP, Polynomial Hierarchy. Space Complexity -- Savichs Theorem, The class PSPACE.

Text Books and References: 1. J.P. Trembley and R. Manohar -- Discrete Mathematical Structures with Applications to Computer Science, McGraw Hill Book Co., 2. Michael Sipser -- Introduction to The Theory of Computation, Thomson Course Technology. 3. John E. Hopcroft and J.D.Ullman -- Inrtroduction to Automata Theory, Languages and Computation, Narosa Pub. House, N. Delhi. 4. H.R. Lewis and C.H.Papadimitrou -- Elements of the Theory of Computation, Prentice Hall, International, Inc.

Time Table

Day	8:00-8:55 am	9:00-9:55 am	10:00-10:55 am	11:00-11:55 am	12:00-12:55 pm		2:00-2:55 pm	3:00-3:55 pm	4:00-4:55 pm	5:00-5:55 pm
Monday			CSE-107
Tuesday
Wednesday	CSE-107	CSE-107
Thursday			CSE-107
Friday