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 | |||||||||||||||||
| |||||||||||||||||
Semester | Autumn |
Syllabus[edit | edit source]
Syllabus mentioned in ERP[edit | edit source]
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.
Concepts taught in class[edit | edit source]
Student Opinion[edit | edit source]
How to Crack the Paper[edit | edit source]
Classroom resources[edit | edit source]
Additional Resources[edit | edit source]
Time Table[edit | edit source]
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 |