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.

Prerequisites

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.

Lectures

TR 3:30-5PM in room GCB 209

Sections

CAS CS330 A2 878748 Wednesday 4:00pm-5:00pm in MCS B23
CAS CS330 A3 878735 Wednesday 5:00-6:00pm in MCS B23
CAS CS330 A4 865436 Thursday 2:00-3:00pm in MCS B33

Tests

Quiz 1: Thursday, Oct. 16 (in class)

Midterm: Thursday, Nov. 6 (in class)

Quiz 2: Tuesday, Nov. 25 (in class)

Final: TBA

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.

Instructor

Professor Shang-Hua Teng

Email: steng@cs.bu.edu
Office: MCS-276
Office Hours: Tuesday 12:30-2:00pm, Thursday 12:30-2:00pm (or by appointment)
Office Phone: 358-2596

Teaching Fellow

Tao Wang wtwang@cs.bu.edu

Email: tba@cs.bu.edu
Office: PSY 226
Office Hours: Wed. 3--4 pm, Thursday 10-12am (or by appointment)
Office Phone: 617 258 2355

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