## EECS 380: Data structures and Algorithms## Winter 2001 |

- 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

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

s of`char*`

.

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

- 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

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

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.

- 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 #1
- Partial solution for homework #1
- Homework #2
- Some hints for hw2
- Homework #3
- Homework #4
- Homework #5

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.

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.

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

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