BU CAS CS 330 AI – Fall 2003, Algorithms

(Class Information)

Instructor: Professor Shang-Hua Teng

Email:

Office: MCS-276

Office Hours: Tuesday 12:30-2:00pm, Thursday 12:30-2:00pm

(or by appointment)

Office Phone: 358-2596

Class Web Page:

Please read the class web page for all relevant information (including the class schedule) of this class. If you have any question, please talk with Professor Teng. The class web page will evolve during the semester, where homework assignments and lecture slides will be posted once they are available.

Lectures Time and Place:

TR 3:30-5PM in room GCB 207

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

Important information:

This class will have 6 homework assignments, two quizzes, one midterm and one final. The grade will be distributed according to the following distributions

  • 30% - written assignments
  • 10% - quiz 1
  • 20% - midterm
  • 15% - quiz 2
  • 25% - final

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.

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