EECS 380: Data structures and Algorithms

Winter 2001

Announcements

Basic information

Lecture 1 (Tues/Thur. 10:30-12:00, 1504 GGBL) Prof. Mark Brehob: 2237 EECS, brehob@umich.edu
Lecture 5 (Tues/Thur. 1:30-3:00, 1013 Dow) Prof. Igor Markov: 2211 EECS, imarkov@eecs.umich.edu

Teaching assistants: (office hours will be held on the 3rd floor of the Media Union computer lab.)

Exam times/dates

Midterm: Thursday Feb 22nd in class (see questions and answers)
Final: As per university schedule.
Prof. Markov's section: Wed, Apr 25 @ 1:30 - 3:30
Prof. Brehob's section: Wed, Apr 25 @ 4:00 - 6:00

Office hours

On-line, use the Class Newsgroup. Computer labs: locations and current usage

Course Material

The required text for this class is Algorithms in C++, 3rd edition by Robert Sedgewick. We will also use handouts and web references on a regular basis. Also, see the recommended additonal material for useful information..

Class handouts will be available on-line. Sample discussion questions are also available.

There is information on the midterm, which include exam texts and solutions.

Practice final is now online.

Other handouts on Convex hull and growth of functions. are available on the media union's site. (You will be asked for your library password...)

The Class Newsgroup umich.eecs.class.380 will also be a useful source of information. For best results, be sure to use the engin newserver, news-server.engin.umich.edu.

Projects

Homework assignments

Course overview

This course is intended to give you an understanding of data structures and algorithms in addition to further exposing you to C++ and programming in general. We intend to teach the ``traditional'' topics for this course. But in addition the students will be exposed to non-traditional (but very useful in practice) data structures and tools.

Prerequisites

Students must have taken EECS 203 and EECS 280 or have an equivalent background. You should understand basic programming concepts including pointers, arrays, linked lists, and data abstractions. You should understand basic discrete mathematics including recursion relations, big-Oh notation, and have a basic understanding of sets and graphs.

You will be doing your work in C++ on a Unix system. If you are not familiar with that environment, we advise that you learn quickly. A TA can help you during office hours.

Class Projects and Homework

Three projects will be assigned during the term, each of which will require substantial time commitments. Further there will be about 6 homework assignments.

Homeworks will be turned in the EECS 380 box in room 2420 EECS. Due dates and times will be listed on the homework assignments themselves. Once the assignments have been picked up for grading, no assignments will be accepted unless a verifiable emergency occurred. The pick-up might occur right at the due time or hours later. In general we recommend that you get the assignments in 24 hours ahead of the due date in order to avoid potential problems (car wouldn't start, printer went down, no computers available, etc.)

Projects will be turned in via an autograder. This procedure will be described on the project assignment itself. Extensions will only be granted for medical or personal emergencies. Be prepared to substantiate any extension request with written proof, for example a note from your doctor. Extensions will not be grated for reasons such as: the printer went down, you erased all your files, you lost your code, etc. You can avoid all these problems by starting the projects early and keeping backup files.

Project and Homework Grading

The projects and homework will be graded primarily for correctness and style. All grading issues should first be discussed with your TA. If you cannot resolve a problem with the TA, bring the project to the instructor.

Doing your own projects and homework

All projects and homeworks are to be done on your own. Violation will result in a zero on the project/homework and initiation of formal procedures for LSA or Engineering honor councils. We will be using a correlation program to check for cheating. At the same time, we encourage students to help each other learn the course material. As in most courses there is a boundary separating these two situations. In general you can discuss concepts of the course or on the specifics of C++ syntax. But you may not collaborate in any way when constructing a solution. If you have any questions about what constitutes unacceptable collaboration, please talk to your instructor.

Exams

You are to take both the midterm and the final at the scheduled times. We require at least 2 weeks notice and written documentation of the conflict.

Grading

Final grades will be based on the total points earned on the projects and exams. Factors such as class participation may be used to adjust your final grade, especially if it falls on a borderline. The tentative point breakdown is as follows:

Computers

Your programs will be graded on a SUN workstation using g++. Your programs, and makefiles, need to work on those machines.

Lecture schedule

# Lectures       Topic                             Chapters
 ---------------------------------------------------------------------
    1        |    Introduction                    | 1
 ---------------------------------------------------------------------
             |    Fixed arrays: static vs dynamic | 
             |                  memory allocation |
    3        |    Expandable arrays               | 3
             |    Linked lists                    |
             |    Strings                         |
 ---------------------------------------------------------------------
             |    Linear (unstructured) search    | 
    3        |    Binary search and               | 12.4
             |      other ops with sorted ranges  | 2
             |    Random vs. sequential access    |
             |    Bit-vectors                     |
             |    Algorithm analyses              | 
 ---------------------------------------------------------------------
    2        |    Stacks                          | 4.2-4.4
             |    Queues                          | 4.6
 ---------------------------------------------------------------------
             |    Specification by interface      |
    2        |    Abstract data types             | 4.1, 4.8-4.10
             |    Generic programming             |
             |    Introduction to STL             | 
             |           reference: http://www.sgi.com/Technology/STL/
 ---------------------------------------------------------------------
    4-5      |    Sorting and permutations        |
             |    Traversal of permutations       |
             |    Linear-time sorted range test   |
             |    Elementary sorting methods      | 6
             |    Quicksort (+median pivoting)    | 7
             |    Merge sort                      | 8
             |    Radix sort and bin sorting      | 10
             |    Pointer sorting, stability,     |
             |      sorting permutations          |
 ---------------------------------------------------------------------
    1        |    Midterm                         | 1-4,6-8,10 + STL
 ---------------------------------------------------------------------
    4        |    Recursion and Trees             | 5
             |     divide-and-conquer             |
             |     dynamic programming            |
             |     traversals  properties of trees|
             |    Heaps and priority queues       | 9
             |    Binary search trees             | 12.5-12.6
 ---------------------------------------------------------------------
    2        |    Hashing                         | 14
 ---------------------------------------------------------------------
    6+       |    Graphs                          | handouts
             |    Advanced topics                 | 12,13,16
 ---------------------------------------------------------------------