CS30053 : FOUNDATIONS OF COMPUTING (3 0 0 3)

Detailed Syllabus:

Logic, sets, relations and functions, induction, iteration and recursion, graphs. Algebraic structures, combinatorics. Grammars and languages, automata, Turing machines, undecidability. Algorithms and their correctness, complexity, intractability.

Text Books:

Kenneth H. Rosen, Discrete Mathematics and its Applications, Tata McGraw-Hill.

Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, Pearson Education, Asia.

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.

Foundations of Computer Science, C Edition, Alfred V. Aho and Jeffrey D. Ullman

Discrete Mathematics in Computer Science, Donald F. Stanat and David F. McAllister

Other materials shall be distributed

Evaluation Procedure

Assignments: 10 marks

Quiz: 1 Quiz : 10 marks

Mid Sem Exam: 30 marks

End Sem Exam : 50 marks

Presentations for the class:

Overview

Logic

Proofs

Inductive Reasoning

Pigeon Hole Principle

Growth of Functions: The Order of a Function

Recurrences: Deriving and Solving Them

Divide and Conquer Algorithms and the Master Theorem

Mathematical Relations

Partially Ordered Sets

Analysis of Algorithms

Analysis of Recursive Algorithms