Course Description

This course is designed to provide students with an understanding of the principles and techniques used in the design and analysis of computer algorithms. The course is primarily theoretical and does not require programming, but it does require understanding of the notion of a mathematical proof and some knowledge of elementary discrete mathematics. We will discuss and analyze a variety of data structures and algorithms chosen for their importance and their illustration of fundamental concepts. We shall emphasize analyzing the worst-case running time of an algorithm as a function of input size. We will focus on the themes of efficient algorithms and intractable problems. Toward the end of the term, we will also examine heuristic techniques often used in practice, even though in many cases their worst-case complexities are either not known or very high.

The course goal is to provide a solid background in algorithms for computer science students, in preparation either for a job in industry or for more advanced courses at the graduate level. I strongly encourage mathematicians and people from other concentrations to take the course as well.

Because this may be the first course for many of you to study the modern theory of algorithms, and we will be covering a great deal, I expect the course to be challenging, both in terms of the workload and the difficulty of the material. You should be prepared to do a lot of work outside of class. The payoff will be that you will learn a lot of both useful and interesting things.


CAS CS 112 or CS 113; CAS MA 293 and MA 294

While we may review some of the topics covered in the above courses (such as some sorting algorithms, depth- and breadth- first searches, basic data structures: lists, stacks, queues, etc.), we will be doing it in a way which assumes that you had reviewed them on your own. Namely, we will be focusing on issues glossed over in your first introductions to these topics. So, please make sure to read the assigned chapters reviewing these topics, even before these are covered in class.


TR 11:00am-12:30 in room MCS 148


CAS CS330 A2 690566 Monday 1:00pm-2:00pm in KCB 201
CAS CS330 A3 690553 Wednesday 2:00pm-3:00pm in CAS 208


Quiz: Tuesday, Feb. 25

Midterm: Thursday, March 27

Final: May 8th, 9:00-11:00 am in Room MCS 148.

Performance self-monitoring:

The grade statistics for hw's and tests will be published on the web.

The danger zone is one tandard deviation below average or worse.

If you find yourself in this danger zone more than a couple times - you have a good chance to fail the class. If you are in the danger zone a few times, then (1) talk to the instructor (and/or TF) without delay; (2) make sure that your performance improves.


Professor Shang-Hua Teng

Office: MCS-276
Office Hours: Tuesday 12:30-2:00pm, Thursday 1:30-3:00pm (or by appointment)
Office Phone: 358-2596

Teaching Fellow

Maosen Fang

Office: MCS-147
Office Hours: Monday 2:00-3:00pm, Wednesday 5:00-7:00pm (or by appointment)
Office Phone: 358-2376

Required Texts

Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, 2nd edition, 2001. (here is another link to the book)

There are a few other useful/recommended texts listed in a bibliography compiled by Professor Homer.

In addition, here is a link of an on-line "Dictionary" of Algorithms and Data Structures