Computing Theory (COT)

The design, implementation, analysis, and application of a range of computer algorithms are explored. Function order of growth and amortized analysis are used in analyzing algorithms. A review and extension of data structure topics including trees and graphs are covered. Algorithm design strategies such as divide-and- conquer, the greedy method, and dynamic programming are studied.

This course focuses on the theoretical foundations of computing, grammars, automata, and formal languages including finite-state and push-down automata, regular expressions, context free and context sensitive languages, Turing machines, and introduction to complexity theory.

This course will cover techniques for the design of algorithms and the theory of np-completeness. The main topics covered in the course include dynamic programming; divide and conquer; union-find data structures; graph algorithms; np-completeness; and advanced topics.