CS205M: Theoretical Foundations of Computer Science

Instructor

Khushraj Nanik Madnani

Teaching Assistants

• Ritu Kumari (Ph.D. candidate)
• Archana K. R. (Ph.D. candidate)
• Kethireddy Mahendranath Reddy (M.Tech. I)
• Vishwa Pranav Reddy Bobbala (M.Tech. I)

About the Course

The course is evenly split between:

• Discrete Mathematics (50%)
  • Sets, Functions, Relations, Partial Orders
  • Recurrences, Summations
  • Counting, Generating Functions, Asymptotics
  • Elementary Logic and Proof Techniques
  • Introduction to Graphs
  • Group Theory (if time permits)
  • Reference Book:
    Discrete Mathematics and Its Applications (Indian adaptation by Kamala Krithivasan) – Kenneth. H. Rosen
    No need to buy books, if you don't prefer. I will be giving some notes which should cover the essentials.
• Formal Languages and Automata Theory (50%):
• Reference Book: TBD
• Alphabets, Languages
• Regular Languages: Finite Automata, Regex
• Context-Free Languages: PDAs, CFGs
• Recursively Enumerable Languages: Turing Machines
• Introduction to Computability and Complexity (if time permits)

Lecture Slides

• Lectures 1 and 2 : Course Introduction, Grading Schemes, etc. and Introduction to Sets
• Lecture 3 : Introduction to Relations and Functions
• Lectures 4 and 5 : Comparing Cardinality of infinite sets, Countability, Introduction to Propositional Logic.
• Lecture 6 : Propositional Logic Continued.
• Lectures 7 and 8 : Introduction to Predicate Logic.

A’ = A – 0.15*A, B’ = B – 0.15*B, ...,  E’ = E – 0.15*E
X = 0.15*(A + B + C + D + E)/5
A_new = A’ + X, B_new = B’ + X, ...,  E_new = E'+ X