EECS 380: Data structures and Algorithms

Winter 2001

Announcements

April 22: Added an alternative solution to problem 4 on practice exam, sent by Nick Schrock. It's a complete working program with a much shorter and more elegant makeBalancedBST() function. It may run slower, but is great if you need to write a piece of code quickly on a final exam.
April 19: A new pq_demo handout is online (demonstrates a priority_queue of pointers)
April 19: Solutions for the Practice Final are online
April 18: The autograder is up. Also some tests are posted. Be sure to click on the link and save it rather than opening the file and doing a cut-and-paste.
April 17: A new handout available that explains tree desrtructors and a neat way to debug linked structures (e.g., trees).
April 17: A medium-severity "one-off" bug was fixed in Problem 4 the practice final.
April 17: Practice Final is online
April 16: Posted a handout for project 3 showing one way to do bit manupulation.
April 13: There was an error grading project 2, we took off points for no justification of your algorithm complexities when we didn't ask for them. We will be fixing those algorithms.txt scores that need fixing, don't e-mail us!
April 13: If you are wondering why your score doesn't add up for proj2, multiply your algorithms.txt file by .75 because that's what we did.
April 13: Bonus Office Hours for those in need:
- Stephane: Wed, Apr 18 from 9-12 am (ouch! who works this early?)
- Jonathan: Wed, Apr 18 from 1-4 pm
- Kevin: Friday, Apr 20 from 1-4 pm
Prof. Brehob will have his normal office hours for the entire week of April 16th.
April 13: Typo fixed on P3 handout. Huffman codes for B and C had an extra "1" in their encoding.
April 9: Project 3 due date extended to Sunday April 22nd at 6pm.
April 7: Added a handout on Containers of pointers. This handout may be useful to students having problems with hash_sets of char*.

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.)

Jonathan Chaffer jchaffer@umich.edu
Kevin Lochner klochner@umich.edu
Stephane Jaskiewicz sjaskiew@umich.edu

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.

Mark Brehob: Tuesday, 12:15-2:15. Wednesday 9am-11am, Friday 1:30-3:30 EECS 2237.
Igor Markov: Tuesday 3-4. Wednesday 1:30-3:30. EECS 2211.
Jonathan Chaffer: Monday 6-9. Media Union 3rd floor.
Kevin Lochner: Wednesday 6-9. Media Union 3rd floor.
Stephane Jaskiewicz: Tuesday 6-9. Media Union 3rd floor.

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

Project #1 (solution)
Project #2 (Due March 22, 2001): sample input, Autograder tests used.
Project #3 (Offically assigned on Friday April 6th at 5:00pm.)

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:

Projects: 33%
Homework: 12%
Midterm: 25%
Final: 30%

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
 ---------------------------------------------------------------------