CS210 : FOUNDATIONS OF COMPUTER SCIENCE (3 1 0 4)
Detailed Syllabus:
Computer Science: Mechanization of Abstraction, Propositional logic,
logic expressions, truth tables, tautologies, contradictions, Predicate
logic, proofs and logical inference. Godels conjecture.
Pigeon-hole principle, elementary counting principles. Data models:
representing structures: Lists, stacks, queues, trees.
Set data model, operations on set and languages. List and vector implementations
of sets. Relations and functions. Binary relations.
Algorithms, Design of programs, correctness of programs, iteration, induction
and recursions. Elementary analysis of algorithms: recurrence and Master's Theorem.
Text Books:
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
Scribe : Please take class notes. You shall be asked to submit a scribe on a particular class, chosen by me. The document is to be prepared in latex : 10 marks
Assignments: 20 marks
Quiz: 1 Quiz : 20 marks
End Term Examination : 50 marks
Presentations for the class:
Overview
Logic
Proofs
Inductive Reasoning
Analysis of Algorithms in the RAM model(PDF,
PPT)
Growth of Functions
Recurrences: Deriving and Solving Them
Divide and Conquer Algorithms and the Master Theorem
MergeSort: Implementation and Analysis of Recursive Programs
Sets and Languages
Relations
Binary Relations as Trees, Expression Trees
Partial Ordering
Functions
Countability
Principles of Counting: Counting-I
Theory of Ramsey: Ramsey's Number
Counting-II: Pigeon Hole Principle
Derangements
The Principle of Inclusion and Exclusion
Examination Questions:
Mid Term Examination
End Term Examination