Basic information:

• Instructor: David Liben-Nowell ("David"; not "Dave"), dlibenno
• Lecture: 1a (MW 8:30a–9:40a, F 8:30–9:30a), CMC 206.
• Office Hours: Tuesday 10–11a; Wednesday 1–2:30p; Friday 9:40–10:40a.
  Always feel free to email for an appointment if the scheduled times aren't good for you.
  
  
• Prefector: George Kachergis (kachergg). Prefecting sessions: 7pm on Sundays and 6pm on Tuesdays, CMC 319. Feel free to drop by!
• Grader: Daniel Lew (lewda).
  
  
• Catalogue description: Data structures form the foundation of computer science: they make algorithms more efficient and facilitate problem-solving on both small scales and large scales. In this course, we will explore these basic building blocks of computer science and develop computer programs based on these data structures. We will study stacks, queues, trees, linked lists, graphs and hash tables, as well as algorithms for recursion, searching, and sorting. Mathematical methods for analyzing the performance of algorithms will also be addressed. We will apply these concepts in a term-long software design project. Prerequisite: Computer Science 117 or consent of the instructor.

Announcements:

• The final exam is Monday, 13 March 2006, 7:00–9:30p, in our normal classroom.
• Review session for the final: 11:00a–12:00p on Sunday, 12 March 2006, in our regular classroom. Bring questions; we'll quit early if you don't ask anything.
• The optional PS8 was distributed in class on Monday, 27 Feburary 2006. It needs to be submitted by 5:00p on Friday, 10 March 2006, if you want credit for it.
  
  
• There is an anonymous feedback form available for any comments that you have about the course. If you have any suggestions or comments on the class (style, content, workload, etc.), please feel free to use this form to let me know.
  
  
• Old announcements.

Estimated Approximate Rough Tentative Schedule (subject to change):

• Week #1: introduction to data structures, Java review, inheritance and interfaces. Chapters 1 and 3 and Appendix A, as necessary.
• Week #2: efficiency of algorithms, linked lists. Chapters 2 and 4.
• Week #3: more linked lists, stacks. Chapters 4 and 5.
• Week #4: queues, recursion. Chapters 6 and 7.
• Week #5: midterm exam, recursion, sets and maps, trees. Chapters 2 and 9.
• Week #6: midterm break, trees, binary search trees. Chapter 8.
• Week #7: balanced binary search trees. Chapter 11.
• Week #8: heaps and priority queues, hashing. Chapters 8 and 9.
• Week #9: sorting and graphs. Chapters 10 and 12.
• Week #10: graphs and presentations. Chapter 12.

Classes, Assignments, and Labs:

• 04 January 2006 (W): CS127, dictionaries. For Friday: PS0 (survey), read §1.2–1.3, §3.1–3.4, and some information on pair programming, and Appendix A if needed.
• 06 January 2006 (F): array-based dictionaries, ADTs, efficiency begun. For Monday: read §2.8 and §3.4. If you feel like it, read §2.7 on loop invariants.

• 09 January 2006 (M): inheritance, abstract classes, interfaces, and how to compare algorithms. For Wednesday: reread §2.8.
• 11 January 2006 (W): algorithmic efficiency, and a sketch of generics. For Friday: read §4.4.
• 13 January 2006 (F): more efficiency, digressions on sorting, and linked lists begun. For Monday: read §4.5–4.6. Don't forget PS1!

• 16 January 2006 (M): PS1 debriefing, linked-list implementation. For Wednesday: read the rest of Chapter 4. Complete peer evaluation for PS1 by tonight (Monday) at 11:59p.
• 18 January 2006 (W): linked lists, sentinels, iterators (LinkedList127.java, LinkedListTester.java). PS2 assigned. For Friday: read §5.1–5.4 (skim 5.4); complete PS2 design.
• 20 January 2006 (F): recursive view of linked lists, stacks. PS2 design document due tonight; PS2 due Monday. For Monday: read §6.1, §6.3.

• 23 January 2006 (M): queues; recursion begun. For Wednesday: read Chapter 7. Don't forget PS2!
• 25 January 2006 (W): more recursion. For Friday: reread Chapter 7, and read Wikipedia's "tail recursion" entry.
• 27 January 2006 (F): recursion: memoization, backtracking (8 Queens applet). For Monday: read §9.1–9.2; finish PS3; PS2 peer eval.

• 30 January 2006 (M): 8 queens analyzed, review. For Wednesday: study! Don't forget PS3.
• 1 February 2006 (W): Midterm exam. Reading for Friday: §8.1–8.4.
• 3 February 2006 (F): trees, binary search trees. For Wednesday: review §8.1–8.4.

• 6 February 2006 (M): midterm break!
• 8 February 2006 (W): binary search trees, tree traversal. For Friday: review §8.1–8.4, read §11.1, §11.3. Don't forget PS4!
• 10 February 2006 (F): more BSTs, a digression on computability, augmented BSTs. For Monday: review §11.1, §11.3.

• 13 February 2006 (M): (Amy.) AVL trees (applet for AVL trees). For Wednesday: read §11.2 (on AVL trees), and §11.1, §11.3 (for real this time).
• 15 February 2006 (W): red/black trees (applet for red/black trees). Reading for Friday: §8.5.
• 17 February 2006 (F): red/black trees, concluded. Finish PS5 for Sunday.

• 20 February 2006 (M): priority queues. For Wednesday: read §9.3 and §9.4; fill out PS5 peer evals; work on PS6.i.
• 22 February 2006 (W): hashing—chaining (hashing applet). For Friday: reread §9.3–9.4; work on PS6.
• 24 February 2006 (F): hashing—open addressing (hashing applet). For Monday and Wednesday: read Chapter 10 (skip §10.6, §10.11).

• 27 February 2006 (M): insertion/selection/bubble/heap/merge sort (sorting applet). For Wednesday: finish Chapter 10, read Wikipedia on counting sort and radix sort.
• 1 March 2006 (W): quick sort (sorting applet, plus another applet for other sorts). For Friday: read §12.1–12.3.
• 3 March 2006 (F): counting/radix sort (counting sort, radix sort), introduction to graphs. For Monday: read §12.4.

• 6 March 2006 (M): representation of graphs, BFS/DFS.
• 8 March 2006 (W): presentations (treaps applet).
• 10 March 2006 (F): presentations (skip lists #1, skip lists #2, skip list data).

• 13 March 2006 (M), 7:00–9:30p: final exam!