Office of the Registrar
Campus Address
Hanover, NH
03755-3529
Phone: (603) 646-xxxx
Fax: (603) 646-xxxx
Email: reg@Dartmouth.EDU

New Course Supplement 2016


COSC 49.03 Lower Bounds in Computer Science

In this course we shall study things that computers cannot do. In a typical Algorithms course we learn several ingenious techniques to solve problems efficiently. In contrast, in this course we shall learn how to prove that certain problems cannot be solved too efficiently. For example, you probably know that a set of n integers can be sorted using O(n log n) comparisons. We shall now learn how to prove that O(n log n) is the best we can hope to do: in other words, (n log n) is a lower bound on the number of comparisons required to sort.

During the course we shall survey lower bound results from a wide range of areas in Computer Science. Broadly, we shall study decision trees, Boolean circuits, and communication protocols. We shall consider simple looking problems from each of these areas but, as we shall learn, even innocent looking lower bound results can be quite a challenge to prove.

Proving lower bounds requires a puzzle-solving bent of mind rather than extensive knowledge of Algorithms; this course will involve quite different ways of thinking than CS 31. A love of mathematical reasoning always helps, but we will not be using any advanced mathematics itself.

Distributive and/or World Culture

Dist:QDS

The Timetable of Class Meetings contains the most up-to-date information about a course. It includes not only the meeting time and instructor, but also its official distributive and/or world culture designation. This information supersedes any information you may see elsewhere, to include what may appear in this ORC/Catalog or on a department/program website. Note that course attributes may change term to term therefore those in effect are those (only) during the term in which you enroll in the course.