##

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