The most fundamental types of algorithms and algorithmic methods of general use in computer science will be studied. We will concentrate on learning the most important concepts used in constructing these algorithms and on analyzing their efficiency. We'll start with the sorting review and develop our analysis techniques using these simple algorithms. Then we'll proceed to the algorithms and data structures for order statistics (first static, then dynamic); priority queues (leftist heaps); dictionaries (hashing and tree-based); and disjoint sets. In the last third of the course we'll apply these data structures to graph problems like minimum weight spanning trees and shortest path; as well as study other algorithms such as all-shortest-paths/transitive-closure; matrix operations; (and time permitting) integer arithmetic; pattern matching, etc. In the last class we will preview the notion of NP-completeness - topic covered in greater depth in cs332.
Though this course is sometimes considered a "theory" course (in particular, since it has no programming assignments, and even includes some proofs), it is in reality one of the most practical and useful courses offered in the CS department. It is hard to imagine a software developer who would not have an opportunity to apply the material and skills covered in this course in his/her job projects. Some of the algorithms will be heavily utilized even before you graduate - in other courses (e.g. graph algorithms are used in networks, e.g. cs455). I had more than one student tell me even midway through the course that they are already applying what they have learned in their part-time jobs. I even know of a case when a developer was fired from his job for not knowing/using something we cover in the very first part of the course.
Prereq: CAS CS 112, CS 113. Coreq: CAS CS 232 or CAS MA 242, CAS CS 235 or 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.
Tuesday, Thursday: 2-3:30pm in mcs-B31
email: itkis+330 cs . bus.bedu
Office Phone: 353-5285
Office Hours: Thursday 10:30am -1:30pm
(or by appointment)
email: dbera cs.bu.edu
Office: PSY221 (64 Cummington Street, opposite the CS dept building)
Office Phone: 358-2354
Office Hours: Mon - 2-3:30pm; Wed - 3:30-5pm
Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, 2nd edition, 2001. The book also has an errata page.
There are a few other useful/recommended texts listed in a bibliography compiled by prof. Homer.
Data Structures and Network Algorithms, by Robert Endre Tarjan, 1983.
Algorithms, by S. Dasgupta, C. Papadimitriou, U. Vazirani. 2008.
Algorithm Design, by J. Kleinberg and E. Tardos, 2006