CMSI 282 Home Page

CMSI 282 - Data Structures and Algorithms II - spring, 2007 Home Page and Course Syllabus

Brief contents

We will build upon the material of CMSI 281 to investigate algorithm paradigms, with an emphasis on combinatorial search. Among other things, we will look at divide-and-conquer algorithms, greedy methods, dynamic programming, randomized algorithms, some modern heuristics (e.g., genetic programs, simulated annealing), problems on strings (such as string matching and determining longest common subsequences), advanced sorts and order statistics, how to generate combinatorial objects, graph algorithms, and some computational geometry, with a little cake-cutting thrown in for good measure.

A major theme of the course is the notion of algorithm paradigms which transcend specific problems to serve as more general program models.

There will be a midterm (in class, Tuesday, March 20) and a final exam (11 am, Thursday, May 3). You should also expect (roughly) bi-weekly assignments that include problems to be worked out, proofs, and, of course, lots of programming.

There are required textbooks, but- quite intentionally- they have not been ordered for the LMU Bookstore. In a nutshell, several excellent books could easily serve this purpose (e.g., Cormen, Leiserson, Rivest, and Stein; Dasgupta, Papdimitriou, and Vazirani; Kleinberg and Tardos; Levitin; Aho, Hopcroft, and Ullman, which is somewhat dated, but still outstanding; and Skiena); as well as several useful "auxiliary" books (Gonick and Wheelis; Robertson and Webb). These are all described in the much longer annotated list of references.

Revised: December 23, 2007