CS 61B: Data Structures - Shewchuk

CS 61B
Data Structures

Prof. Jonathan Shewchuk
jrs@cory.eecs
(But send class-related mail to cs61b@cory.eecs so the TAs can respond too.)

Spring 2009
Mondays, Wednesdays, and Fridays, 5:00–6:00 pm
155 Dwinelle Hall

Mike Clancy would like all CS 61B students to please take this survey. One point on your final exam depends on it. Solutions to the final exam are here.

Please congratulate Daniel Flanigan and Dylan Scott, also known as Deep Blue, for destroying all opposition and winning the Network Tournament!

Review questions for the Final Exam are available. Here are the sample solutions to selected questions.

The Final Exam took place on Wednesday, May 20 from 5 to 8 pm in Wheeler Auditorium. If you are in the Disabled Students' Program, your exam started at the same time in 380 Soda Hall. The review session was Monday, May 18 from 8:30 to 10:30 pm in 10 Evans Hall. The exam is open book, open notes, closed electronics. Please try to leave laptops, cell phones, and MP3 players at home. If you must bring them, leave them at the front at the start of the exam.

Textbooks

Kathy Sierra and Bert Bates, Head First Java, O'Reilly, 2005. ISBN # 0-596-00920-8. (Either the first or second edition will do.)
Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, John Wiley & Sons, 2006. ISBN # 0-471-73884-0. (The first, third, or fourth editions will do, but the second edition is missing several important data structures.)
Warning: The reading assignments given below apply to the second edition of Sierra & Bates, and the fourth edition of Goodrich & Tamassia. If you have older editions, you'll have to figure out the corresponding readings yourself.

Information

Course overview: prerequisites, laboratory and discussion sections, grading, cheating policies.
Schedule of labs and sections (and their TAs).
Getting help: schedule of instructor and TA office hours and more.
Online version of the course reader, plus extra documentation on Java and Gmake.
The Java 2 standard libraries API: frames, no frames (maintained by Sun).
The Java language specification (maintained by Sun).
A brief man page for jdb, Sun's Java debugger.
Get tutoring from Upsilon Pi Epsilon, International Honor Society for the Computer Sciences.
Information on connecting from home.
User's Guide to EECS Instructional Computing.
Access the ucb.class.cs61b newsgroup. From off campus, use the portal http://inst.eecs.berkeley.edu/webnews using your class account.

Work

Homeworks and Projects.
Labs.
Exams. Includes sample solutions to midterms in the reader.

Lectures

The following schedule is tentative. There may be changes as the semester progresses, so check here periodically.

Labs, homeworks, and projects that are currently available can be accessed by clicking on them. Sadly, there will be no webcasts this semester, but you can access the webcasts from last time I taught the course through the Webcast Berkeley page provided by Berkeley's Educational Technology Services.

Some lecture notes can be obtained by clicking on the lecture titles (for ASCII) or the PostScript or PDF links (which save paper). Please understand that they are lecture notes, and that they were written so that I would have something to say in class. I write them for me, not you, and I make them available as a courtesy to you. I edit them after class to make sure they say the same thing I said in class. If I receive complaints that my lectures and lecture notes do not differ, I will stop making lecture notes available. For related reasons, I will not make the lecture notes for a class available until after the class has taken place.

	Topic	Reading	Due
1: January 21	Course overview	Sierra & Bates, pp. 1-9, 18-19, 84	.
2: January 23	Using objects	S & B, Chapter 2; pp. 54-58, 154-160, 661, 669	Lab 1

3: January 26	Defining classes	S & B, pp. 71-74, 76, 85, 240-249, 273-281, 308-309	.
4: January 28	Types; conditionals	S & B, pp. 10-14, 49-53, 75, 78-79, 86, 117, 286-287, 292, 660	Homework 1
5: January 30	Iteration & arrays I	S & B, pp. 59-62, 83, 114-116, 293-300, 670	Lab 2

6: February 2	Iteration & arrays II	S & B, pp. 282-285	.
7: February 4	Linked lists I	Goodrich & Tamassia, Section 3.2	Homework 2
8: February 6	Linked lists II	G & T, Section 3.3	Lab 3

9: February 9	Stack frames	Sierra & Bates, pp. 77, 235-239, 258-265, 663	.
10: February 11	Testing	S & B, pp. 95-109, 662	Homework 3
11: February 13	Inheritance	S & B, Chapter 7; pp. 28-33, 250-257	Lab 4

February 16	President's Day	.	.
12: February 18	Abstract classes	S & B, Chapter 8	Project 1
13: February 20	Java packages	S & B, pp. 154-160, 587-591, 667-668	Lab 5

14: February 23	MIDTERM I	covers Lectures 1-12	.
15: February 25	Exceptions	S & B, pp. 315-338	Homework 4
16: February 27	More Java	S & B, pp. 189, 283	Lab 6

17: March 2	Game Trees	.	.
18: March 4	Encapsulation	S & B, pp. 80-84	Homework 5
19: March 6	Encapsulated lists	S & B, p. 664	Lab 7

20: March 9	Asymptotic analysis	Goodrich & Tamassia, Chapter 4	.
21: March 11	Algorithm analysis	G & T, Chapter 4	.
22: March 13	Stacks & queues; dictionaries	G & T, Sections 9.1-9.3	Lab 8

23: March 16	Hash tables & hash codes	G & T, Chapter 5	.
24: March 18	Trees and traversals	G & T, Chapter 7	.
25: March 20	Priority queues	G & T, Sections 8.1-8.3	Lab 9
March 22	.	.	Homework 6

March 23-27	Spring Recess

26: March 30	Binary search trees	G & T, Section 10.1	.
27: April 1	Balanced search trees	G & T, Section 10.4	Project 2
28: April 3	Graphs	G & T, Sections 13.1-13.3	Lab 10

29: April 6	Weighted graphs	G & T, Sections 13.5, 13.7-13.7.1	.
30: April 8	Four sorting algorithms	G & T, Sections 8.2.3, 8.3.5, & 11.1	Homework 7
31: April 10	Quicksort	G & T, Section 11.2	Lab 11

32: April 13	MIDTERM II	covers Lectures 1-29	.
33: April 15	Disjoint Sets	G & T, Section 11.6	Homework 8
34: April 17	Sorting & selection	G & T, Section 11.3 & 11.7	Lab 12

35: April 20	Radix sort	G & T, Section 11.4	.
36: April 22	Sorting video	.	Homework 9
37: April 24	Splay trees	G & T, Section 10.3	Lab 13

38: April 27	Amortized analysis	.	.
39: April 29	Randomized analysis	.	Project 3
40: May 1	Expression parsing	.	Lab 14

41: May 4	Garbage collection	G & T, Sections 14.1.2-14.1.3	.
42: May 6	Augmenting data structures	.	Homework 10
43: May 8	Review	.	Lab 15

The FINAL EXAM took place on Wednesday, May 20, from 5 to 8 pm in Wheeler Auditorium. (CS 61B is in Exam Group 18.)

Course Description (from the catalogue)

Fundamental dynamic data structures, including linear lists, queues, trees, and other linked structures; arrays, strings, and hash tables. Storage management. Elementary principles of software engineering. Abstract data types. Algorithms for sorting and searching. Introduction to the Java programming language.

Prerequisites: CS 61A or Engineering 7. (The catalogue says “with a grade of B– or better,” but I've never seen this rule enforced.)

Grading

5% for the labs.
10% for the homeworks.
35% for three projects.
12.5% for Midterm I (Monday, February 23, 5–6 pm, 155 Dwinelle Hall).
12.5% for Midterm II (Monday, April 13, 5–6 pm, 155 Dwinelle Hall).
25% for the Final Exam (Wednesday, May 20, 5–8 pm, Wheeler Auditorium).

“Let's see if I remember this. Do I splay the pineapple pizza through the Ted Nugent tea cozies? Or should I zig-zig the Versace laptops through Christina Aguilera first?”

cs61b@cory.eecs