CSC240H Standard Course Description

CSC240H Standard Course Description

Enriched Introduction to the Theory of Computation

Owner

Faith Fich

fich@cs.toronto.edu

Course Description

The rigorous application of logic and proof techniques to Computer Science. Propositional and predicate logic; mathematical induction and other basic proof techniques; correctness proofs for iterative and recursive algorithms; properties of languages.

Background

Contains material currently in both CSC165H and CSC236H, condensed to fit into one half course. This course goes at a faster pace and will have more challenging assignments. It is geared towards students with strong mathematical backgrounds. This course is not intended for students who have taken CSC165H; they should normally proceed to CSC 236H. However, students who wish to switch up to this enriched course will be allowed to.

Prerequisistes

Two OACs from Calculus, Algebra & Geometry, Finite Mathematics with high grades
- NO REASON KNOWN
CGPA 3.00
- enriched course

Corequisistes

CSC148H/150H
- programming skills, including recursion

Exclusions

236H
- "regular" version of this course
CSC238H
- "old" version of this course
MAT309H
- NO REASON KNOWN

Follow-On Courses

CSC263H/265H
- knowledge of algorithm correctness
CSC465H
- knowledge of logic and skills to reason about algorithms

Learning Objectives

Be familiar with propositional and predicate logic
- know the basic definitions and terminology
- be comfortable expressing ideas using logical notation
Understand standard proof techniques, especially induction
- be able to use basic proof techniques (by contradiction, by cases, generalization)
- be able to use induction (weak, strong, structural)
Understand how to state and prove the correctness of algorithms
- be able to write preconditions and postconditions
- be able to write and prove loop invariants
- be able to prove properties of recursive code
Understand basic properties of languages
- know the formal definition of a language and related concepts (strings, alphabets, etc.)
- understand the concept of regular languages and prove things about them
  - know regular expressions (regexps)
  - know finite-state automata (FSAs)
  - know the equivalence of regexps and FSAs
  - be aware of the limitations of regular languages
- understand the concept of context-free languages and prove things about them
  - know context-free grammars (CFGs)
  - be aware of the limitations of context-free languages

Topics (not necessarily in this order)

Propositional and Predicate logic (6 hr.)
- definitions of big-Oh, big-Omega, big-Theta (as examples)
- review of basic proof techniques
- formal syntax and semantics of propositional logic
- formal syntax and semantics of predicate logic
- normal forms
- further applications to computer science
Induction (4 hr.)
- review of induction and strong induction
- least counterexample
- recursive definitions
- structural induction
Program correctness (7 hr.)
- Preconditions and postconditions
- Correctness proofs of iterative programs
  - proving partial correctness using loop invariants
  - proving termination
- Correctness proofs of recursive programs
  - using induction to prove partial correctness and termination together
Languages, grammars, and automata (9 hr.)
- Basic definitions (alphabet, string, language)
- Finite state automata (FSA) (2 hr.)
  - deterministic and nondeterministic FSA
  - FSA as language accepters
  - equivalence of deterministic and nondeterministic FSA
- Regular expressions (2 hr.)
  - syntax
  - semantics
  - applications to pattern matching
- Properties of regular languages (2 hr.)
  - equivalence of regular expressions and FSA
  - examples of nonregular languages
- Context-free grammars (2 hr.)
  - syntax
  - semantics, parse trees
  - ambiguity, non context-free languages

Suggested Texts

```
REQUIRED

No text chosen yet
```

Sample Evaluation

type	weight	description
assignments	40%	4-5 assignments
midterm tests	15-20%	1-2 tests
final exam	40-45%