CSC 301: Finite Automata and Computability

Offered Under: B.Sc. in Computer Science (CSC)
Description

A rigorous introduction to the core concepts of theoretical computer science. Through this course, students will learn to analyze and classify problems according to complexity and computability. Topics covered include fundamental concepts such as string, prefix, suffix, substring, concatenation; Cardinality; Distinction between uncountable and countable infinite; Different proof techniques: Proof by construction, proof by contradiction, pigeonhole principle; Deterministic and non-deterministic Finite state automata; Regular and non-regular languages, regular expressions; Equivalence of NFA and DFA; Pumping Lemma; Context free grammar (CFG) and Push down automata (PDA); Chomsky Normal form; Parsing; Turing machine, Universal Turing machine and the Halting problem; Goedel numbering; Computability (P vs NP).



Course Type Major
Credit Hour 3
Lecture Hour 45
Expected Outcome(s):
  • Learn core ideas in computer science theory, including how to define and investigate a formalized model of computation, and what it means to reduce one problem to another.
  • Deepen their ability to think clearly, originally and devise correct proofs.


Grading Policy:

Letter Grade Marks Grade Point
A 90 - 100 4.00
A- 85 - 89 3.70
B+ 80 - 84 3.30
B 75 - 79 3.00
B- 70 - 74 2.70
C+ 65 - 69 2.30
C 60 - 64 2.00
C- 55 - 59 1.70
D+ 50 - 54 1.30
D 45 - 49 1.00
F 00 - 44 0.00