Next: Priority Queues Up: CS323 Handouts
Welcome to the Spring 2012 edition of CS323, Data Structures and Algorithms. This is a continuation of CS171, where you should have already studied elementary data structures and algorithms. Our other prerequisite is CS224, just for background in mathematical writing. Compared to CS171, this course considers somewhat harder topics, and our approach will be a bit more conceptual and analytic, but still with some programming work.
Book and Rough Syllabus: Our book is Algorithms (4th ed.) by Sedgewick and Wayne.
In CS171 you should have had an introduction to some of this material (sorting, search trees, priority queues, hashing), but we will be revisiting these old topics at a more advanced level, together with some new topics.
half of the course we will study data structures such as binary search trees, hash tables, and tries. In the second half we will study graph algorithms, starting with some basic traversals and near linear-time algorithms (such as we already saw in CS171) and continuing on to some harder topics such as max-flow, matchings, and hard optimization problems.
Meetings: We meet 11:45am-12:35pm MWF in room W303, and no regular lab. That makes 42 meetings, mostly lectures except for an in-class midterm exam (near spring break) and two review days. Our final exam is scheduled by the registrar (4:30pm Friday May 4).
Staff: Your instructor (writing this) is Michelangelo Grigni. Contact me by e-mail at mic@mathcs.emory.edu, or by phone at 7-7922. My office is room W426, just upstairs from our classroom. My office hours will be posted on the web. Also, I am often available by appointment.
Graded Work: There will be five or six graded homeworks, typically with both written and programming elements. There will be a midterm in-class exam weighted like 2 homeworks, and a cumulative final exam weighted like 3 homeworks. Each graded item will be curved so that the median mark is at least 80% (B-).
Syllabus: this is our first semester using this textbook, so there is no precise syllabus available from previous semesters. However, the core topics will be as follows: union-find (Section 1.5), priority queues (2.4), red-black trees (3.3), advanced hashing (3.4 and outside book), graphs including MST and Bellman-Ford (Chapter 4), string algorithms including KMP, tries and TST's (5), advanced topics including B-trees and max-flow (6). We'll add more content if time allows.
Online Support and Handouts: There will be occasional printed handouts like this one, and frequent online notes and source code. All resources will be available via our course web page:
On Math/CS lab machines, the same material may be found via our course ``share directory'', /home/cs323000/share/. These resources should start working around the end of next week.
Policies: It is your responsibility to know what has been covered in class, to read along in the book, to turn in your work, and to attend the exams. Having missed a class is not a sufficient excuse for late work. Don't miss an exam unless you have a medical excuse.
Unless I instruct you otherwise, you should have no outside help on homeworks. You should not share your solutions with other students, nor seek solutions from other sources. On the other hand, the following kinds of collaboration are allowed: interpreting the statement of a problem, understanding an error message, learning features of a language or software tools, reviewing the textbook and course notes. If you are in doubt about what is allowed, ask me.
Your work for this class is governed by the Emory Honor Code and the Math/CS SPCA (Statement of Policy on Computer Assignments). In particular, this means you should take care to protect the confidentiality of your homework files. Apparent honor code violations will be referred to the Emory Honor Council. We may use an automated system to help detect plagiarism.