EECS 281: Data Structures and Algorithms

University of Michigan - Fall 2006

Prof. Igor Guskov

In this course you will learn fundamental data structures and algorithms that power much of existing software. You will also develop practical skills important in Information Technology, and other applications of Computer Science and Engineering. The programming language used in this course is C++.

The course will start with mathematical and empirical techniques for comparing the performance of algorithms (based on material from EECS 203). It will then cover a number of important data structures and their applications (extending the material from EECS 280), and demonstrate the design of new algorithms. Several software projects form an integral part of the course where you will learn the Standard Template Library, while training in both independent S/W development and teamwork.

Official catalog description

EECS 281. Data Structures and Algorithms
Prerequisites: EECS 203 and 280.
Introduction to algorithm analysis and O-notation; Fundamental data structures including lists, stacks, queues, priority queues, hash tables, binary trees, search trees, balanced trees and graphs; searching and sorting algorithms; recursive algorithms; basic graph algorithms; introduction to greedy algorithms and divide and conquer strategy. Several programming assignments.

Instructional Staff and Locations

Lectures:

Prof. Igor Guskov
Office: CSE 3745
Email: guskov@eecs.umich.edu
Office hours: Tuesdays and Thursdays 3:00-4:00pm in room 3745 CSE
Lecture: Tuesdays and Thursdays 1:30pm-3:00pm in room 1670 CSE

Discussion sections:

Wednesdays 3:30-4:30pm: GSI in 2150 DOW
Fridays 1:30-2:30pm: GSI in 1301 EECS

Communication

The main online resource for this course is the UofM Coursetools Web site. http://ctools.umich.edu All students enrolled in this course will be given acccess to the Web site. Lecture notes, announcements, problem assignments, software handouts will be available on this site. All active users are typically listed to every active user, the site contains chat a rooms and a bullet boards. Additionally, we will send email announcements, often to notify you of new material on Coursetools. When you submit assignment electronically, you will receive feedback by email. Therefore you must check your email regularly. If your mailbox becomes full or if your mail is not delivered, you may miss important announcements about deadlines, etc. Therefore, we do not recommend forwarding your UofM mail elsewhere.

In team projects, communication with your teammates is essential. It is your responsibility to be available for group meetings, respond to email and contribute to your group's work. You will not receive a high score if most of your group's work is done by someone else.

Typically, early exams will not be available. When we announce exam times, it is your responsibility to check for potential time conflicts with other courses you are taking and report it to the teaching staff of all involved courses.

Textbook and References

Required reading:

Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss, ISBN: 0-321-44146-X, Third Edition, Addison Wesley
Lecture notes to be posted on Coursetools
Additional references provided on Coursetools
A number of valuable online resources can be found using any search engine, such as
http://www.cppreference.com/ and http://www.sgi.com/tech/stl/.

More references on C++:

Lippman and Lajoie, C++ Primer, latest ed., gentler and more verbose description of the Language.
Lippman, Essential C++, the more advanced features of C++.
A Quick Introduction
Effective C++
C++ Tutorial
C++ stdlib and iostream and the string class
C++ STL
Some C++ features not found in C

Coursework and Grading Policies

Besides attending lectures you are expected to produce evidence of your performance in this course based on:

Homework problem sets
Three software projects (one individual and two team projects)
One 1.5-hour midterm
One 2-hour final

Your numeric course grade will be computed according to the formula:
CourseGrade = 10% * HWK_average + 25% * Midterm_exam + 30% * Final_exam + 35% * Project_average
After the numeric scores are mapped to a curve, the typical average letter grade in this course ranges from B- to B. Students with 2 or more missing projects will receive a failing grade.

Re-Grading. Requests for re-grading of homework and exam problems must be received by the lecture instructor within one week after the return of the papers to the class. This applies whether or not a student was present on the day they were returned. To request a re-grade, write "Re-grade # < problem number > " in red on the top of the first page of the paper. Do not put any new writing anywhere else on the paper.

Homework Policies

Homework assignments will be posted on coursetools with a due date clearly indicated.
Homework papers should be deposited in the EECS 281 drop box in room 2420 EECS by 6:00 p.m. on the due date. This is the only way for you to turn in your homework assignment.
Absolutely no late homework will be accepted. There are no exceptions to this rule. To account for unexpected circumstances, the lowest homework score will be dropped when computing the homework average.
Solutions to the homework will be posted on coursetools.
Homework papers will be available from Ishan Chaudhuri in envelopes marked by discussion section number.
Homework problem sets are to be completed and turned in by each student individually. Xerox copies and faxes are not accepted. Students are encouraged to discuss the assignments and approaches with the professors or the lecture GSI if any difficulties arise, but copying of answers and solutions is a violation of the Engineering Honor Code (see below).

Software Projects

This is the most time-consuming part of the course, therefore please plan accordingly and start working on assignments in advance.

The programming langauage used in this course is C++. No other programming languages can be used by students, but your experience will make it much easier to learn Java or C# in the future.
The programming environment used in this course is g++ on Linux. If you are not familiar with the make system on Linux, it is in your interest to learn it as soon as possible using resources provided on Coursetools.
All project assignments must be submitted electronically using mechanisms we describe in more detail on coursetools. In some cases we may first ask for a project plan in English, and later for working programs.
All programs must be submitted in source code to the 'autograder', which will compile them, run on prepared test cases and report any deviations from expected behavior. You will have a limited number of trial submissions to make sure that your input and output are correctly formatted.
The autograder may not reveal all of its testcases, but may report failures on its testcases.
The first project will be individual, the second project will involve teams of 2-3 students composed by the professor. The third project will involve larger teams assembled by the students themselves. The better you perform in project 2, the easier it will be for you to find partners.
Electronic submissions are automatically checked for similarity against each other and against submissions to earlier assignments, including previous years. University regulations require that we report any suspected violations of the Honor Code (see Section 6) directly to the Engineering Honor Council.

Examinations

Exact dates and times of the midterm and final exams will be posted on Coursetools.
All exams are closed-book and closed-notes. No electronic devices (pagers, cell phones, etc) are permitted. Other prohibited items include textbooks, reference books, homework, project, exam solutions, etc. We may allow one or two sheets of paper with a summary of the material covered so far.
Exams will typically include multiple-choice and fill-in-the-blanks questions with no partial credit for answers that are wrong, incomplete or too general. There will also be open-ended problems with some partial credit for incorrect or incomplete answers.
Some exams may contain extra credit problems, which will not affect the curve. Such problems will typically offer no partial credit and must be attempted only after all regular problems are solved.

The Honor Code

The Honor Code outlines certain standards of ethical conduct for persons associated with the College of Engineering at the University of Michigan. The policies of the Honor Code apply to graduate and undergraduate students, faculty members, and administrators. The Honor Code is based on these tenets:

Engineers must possess personal integrity both as students and as professionals. They must be honorable people to ensure safety, health, fairness, and the proper use of available resources in their undertakings.
Students in the College of Engineering community are honorable and trustworthy persons.
The students, faculty members, and administrators of the College of Engineering trust each other to uphold the principles of the Honor Code. They are jointly responsible for precautions against violations of its policies.
It is dishonorable for students to receive credit for work that is not the result of their own efforts.