EECS 311 - Data Structures & Data Management

Fall 2008

Required Text: Weiss, Data Structures and Algorithm Analysis in C++, 3rd Edition, Addison-Wesley, 2006. [order]

Lectures: Monday, Wednesday, and Friday, 11:00am-11:50am in Tech LG76.

Instructor: Jason D. Hartline.

Office Hours: Wednesday 12:00pm-1:00pm, and by appointment; Ford 3-329.

Teaching Assistants. Benjamin Prosnitz, `bprosnitz [at] gmail.com`

Office Hours: Thursday, 11:00am-12:00am, Tech CG50.

Announcements:

- 9/26/08: Go see Copenhagen, playing through Sunday 9/28/08 in Tech.
- 10/7/08: For tips on basic proof techniques consult Chapter 1 of the text or the course notes for EECS 310: Discrete Math. In particular, see the EECS 310 lecture notes on proofs and induction.
- 10/17/08: Read handout on splay trees [Part I] [Part II].
- 10/20/08: Midterm will be on 10/27/08 in class. You may bring one handwritten sheet of notes.
- 10/20/08: Do not attempt Homework 4, Problem 4.
- 10/24/08: The Midterm Review session will be Sunday at 6pm in Tech L361.
- 10/28/08: Programming Assignment 1 posted, see below.
- 11/18/08: Programming Assignment 2 posted, see below.
- 11/18/08: Students may want to attend Prof. Immorlica's lecture on "Marriage, Honesty, and Stability", Nov. 19, 4pm, Ford ITW.
- 12/3/08:
- Homework 8 will not be accepted late. It is due Friday in class.
- Friday's lecture will be a review for the final. Bring your questions to class.
- We had one fewer programming assignment than originally planned. For anyone who did badly on a program and wishes to improve their grade, you may implement the union-find based maze generating algorithm discussed in section 8.7 of the text.

- Lecture outlines for selected topics have been posted: priority queues, binomial queues, union/find (lecture 1 and lecture 2), sorting, andquicksort.

Overview. Data structures play a fundamental role in the computer system design and programming. Efficient data structures are important for enabling efficient algorithms, especially where there are tradeoffs to be made between initializing, accessing, and manipulating data. For instance Google Inc.'s remarkable success relies on their ability to easily access vast amounts of data in efficient data structures. This course focuses on the design, implementation, and analysis of abstract data types, data structures and their algorithms. Topics include: data and procedural abstraction, linked lists, stacks, queues, binary trees, searching, and sorting.

Prerequisites. EECS 211 (Fundamentals of Computer Programming II) or EECS 231 (Advanced Programming for Computer Engineers). Previous or concurrent enrollment in EECS 310 (Mathematical Foundations of Computer Science) is highly recommended.

Grading.

- Problem Sets (30%) Weekly problem sets will test students understanding of core course concepts. Problem sets must be done individually. Problems sets will be graded on a 20 point scale.
- Programming Assignments (30%) There will be 4-5 programming assignments to ensure that students can translate the theoretical course concepts into practical implementations. Programming assignments must be implemented in C++. The approved compiler for the course is
`g++`. You should ensure that your programs compile and run successfully in T-LAB. - Midterm (15%) There will be one in-class closed-book closed-notes midterm examination. Students may bring one sheet of handwritten notes to the exam.
- Final (25%) There will be a comprehensive closed-book closed-notes final examination. Students may bring one sheet of handwritten notes to the exam.
- Classroom Participation (Bonus 3%) Students who contribute positively to classroom will receive up to 3% bonus on their final grade.

Homework: Homework 1, Homework 2, Homework 3, Homework 4, Homework 5, Homework 6, Homework 7, Homework 8.

Programming Assignments: Programming Assignment 1, Programming Assignment 2, Optional Programming Assignment 3.

Homework Policies. Problem sets and programming assignments shall be done individually. You may discuss them at a high level with your classmates; however, to ensure academic integrity you should not take any notes during your discussions. You may consult your text book, TA, and instructor for help with problem sets; you may not consult the Internet. Problem sets will be assigned weekly on Friday and due the following Friday at the beginning of class. Problem sets turned in after class but before the subsequent class (the following Monday) will receive a 5 point penalty. Solutions will be distributed during the subsequent class, after which late assignments will not be accepted.

Tentative Schedule:

- Week 1: Introduction to data structures, redundant binary counter, runtime analysis. (Reading: Chapters 1 and 2)
- Week 2: Abstract data types, stacks, queues, lists, dynamic resizing (Reading: Chapter 3)
- Week 3: Trees, tree traversals, representations, dictionary ADT (Reading: Chapter 4)
- Week 4: binary search trees, AVL trees, splay trees. (Reading: Splay Tree handout [Part I] [Part II])
- Week 5: Hash tables, hash functions, collision handling schemes, probability, universal hashing (Reading: Chapter 5, Hash table handout [pdf], Notes on probability [Part I] [Part II] )
- Week 6: (Midterm) Graphs, graph representations, graph traversals, breadth first search, depth first search. (Reading: Chapter 9, Sections 1 and 2)
- Week 7: Graph algorithms, topological sort, shortest paths, minimum spanning trees.(Reading Chapter 9, Sections 3 (except 3.3-3.5) and 5)
- Week 8: Priority queues, heaps. (Reading: Chapter 6; Notes on Priority Queues [pdf]; Notes on Binomial Queues [pdf])
- Week 9: Disjoint sets, union-find. (Reading: Chapter 8; Notes on Union Find [1.pdf] [2.pdf])
- Week 10: Sorting, divide and conquer, merge sort, heap sort. (Reading: Chapter 7; Notes on Sorting [pdf]; Notes on Quicksort [pdf])