Syllabus

Overview

We will study intermediate and advanced data structures, computer algorithms, and the analysis of both using techniques from discrete mathematics. We will also study the implementation of these data structures and algorithms using the principles of generic programming and data abstraction.

Data structures and algorithms form a major component of any software system. When building such a system, a skilled computer scientist must make intelligent decisions about alternative techniques, choosing from existing data structures and algorithms or designing his/her own when necessary. While we will concentrate on the theoretical design and analysis of data structures and algorithms, we will reinforce the theory with working examples, laboratories, programming projects, and use of the C++ standard library.

 Main text (required):

Data Structures and Algorithm Analysis in C++, 2nd Edition, by Mark Allen Weiss
Weiss has a more recent and slightly lower level text that is being used in CS II. Be sure you get the right version and edition.

C++ reference (suggested):

The C++ Programming Language, 3rd Edition, by Bjarne Stroustrup
If you do not already own a good C++ reference, Stroustrup's book is recommended. Be sure to get the third edition. This covers all new features of C++ including the standard library.

Here are the basic course requirements, which are explained in more detail below.

Laboratories:           10%
4 Programming projects: 10% each
2 Exams:                15% each
Final exam:             20%

Typical lower bound cutoffs for A, B, C and D grades are 90%, 80%, 70% and 60%, respectively. Your instructor may use higher or lower cutoffs when assigning grades if warranted.

See the class hour schedule for the time and place of your lecture section. You are responsible for all material and announcements made in lecture.  Exams and material may vary between lectures, so you must attend your assigned lecture.

See the class hour schedule for the time and place of your lab section. Labs will be weekly and attendance is required. Those who show up late for lab or those who leave early will not receive credit. Labs cannot be made up. The exams will contain material covered in labs.  Due to the size of the sections and the limited number of computers, you must attend your assigned lab section.  The TA will take attendance and you will not receive credit unless you attend your assigned section.

Four programming projects will be assigned during the semester. Programs will be written in C++ using the standard library and must follow certain guidelines. Students may only collaborate to share design and debugging ideas or to spot compiler errors. Code may not be shared. Project submissions will be compared electronically using a variety of software tools to detect code similarity. Each student caught cheating on a project will receive a grade of zero for that project and will be reported to the Dean of Students office. Late submissions will not be accepted. Any project submitted after 11:59:59 PM on the due date will be given a grade of zero.

During the semester, there will be two exams covering both the lecture and lab material.
With advanced notice, the exam schedule may be altered through the semester.  There will be a
comprehensive final exam given during finals week.

It is very important that each student use his or her best judgment to ensure academic integrity in this class. We've outlined guidelines above concerning collaboration which everyone is expected to follow. Copying sections of another person's code for a project and copying answers from another person during an exam are considered cheating. Refer to the the Rensselaer Handbook for other various forms of academic dishonesty. Academic dishonesty will be dealt with harshly.

The course web site is http://www.cs.rpi.edu/courses/spring00/dsa/ . It will include links to different C++ programming resources, copies of lecture notes, lab assignments, and other material, and class announcements. You should check it fairly often for updates. All course materials will be distributed through the web site.

 This is subject to change, and should be used merely as a guide.

Week            Topics
----            ------
 1              Overview; Data abstraction; STL framework; generic programming
                Algorithm analysis
 2              Sorting algorithms and analysis
 3              Sorting algorithms continued
 4              Review of C++ class mechanics; container requirements
                Implementation & analysis of vector, list, deque
    (Project 1 due 2/4)
 5              Trees; Binary search trees
 6  EXAM 1
 7              Balanced trees
 8              Skip lists; hashing
    (Project 2 due 3/3)
 9              Hashing continued
    (Spring break 3/13-17)
10              Binary heaps; heapsort
11  EXAM 2      Leftist heaps
    (Project 3 due 3/31)
12              Graphs
13              Graphs
14              And more graphs
15              Special topics and review
    (Project 4 due 4/27)
    FINAL EXAM TBA finals week

---

Last updated: January 10, 1999 by Eric Breimer

Go Back Home