ENROLL

David Liben-Nowell

An introduction to the theory of computation. What problems can and cannot be solved efficiently by computers? What problems cannot be solved by computers, period? Topics include formal models of computation, including finite-state automata, pushdown automata, and Turing machines; formal languages, including regular expressions and context-free grammars; computability and uncomputability; and computational complexity, particularly NP-completeness.

Prerequisite: Computer Science 111 and either Computer Science 202 or Mathematics 236

David Liben-Nowell

A second course on designing and analyzing efficient algorithms to solve computational problems. We will survey some algorithmic design techniques that apply broadly throughout computer science, including discussion of wide-ranging applications. A sampling of potential topics: approximation algorithms (can we efficiently compute near-optimal solutions even when finding exact solutions is computationally intractable?); randomized algorithms (does flipping coins help in designing faster/simpler algorithms?); online algorithms (how do we analyze an algorithm that needs to make decisions before the entire input arrives?); advanced data structures; complexity theory. As time and interest permit, we will mix recently published algorithmic papers with classical results.

Prerequisite: Computer Science 252 or instructor permission

David Liben-Nowell

Beginning with the prototypes developed in the Senior Seminar, project teams will complete their project and present it to the department. Required of all senior majors.

Prerequisite: Computer Science 399

David Liben-Nowell

Beginning with the prototypes developed in the Senior Seminar, project teams will complete their project and present it to the department. Required of all senior majors.

Prerequisite: Computer Science 399