CSC 320

Connex

Overview

The goal of this course is to study the fundamental power and limitations of computation. We will use abstract models to gain an understanding of what can and cannot be achieved using computational devices. We will study the Turing machine, a model that captures everything that can be computed in principle, and formally show the existence of problems that cannot be solved by this model. We also examine restricted versions of Turing machines, such as finite automata, context-free grammars, and time- and space- bounded machines, which are often useful in practice and have structure which will allow use to give deep characterizations enabling us to understand their power. We will define what it means to show that one problem is harder to solve than another, and use this idea both to prove that some problems are hard to solve and also to develop generic techniques for solving large classes of problems. In particular, we will look at the Satisfiability problem, which will provide us with a general method for solving many kinds of optimization problems, and which is also a key component of the problem at the heart of modern computer science – P vs NP.

Textbook

TBA

Assessment

Task Weight
Assignments 5%
Project 10%
Midterm 35%
Final 50%