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 2005 Mondays, Wednesdays, and Fridays, 3:00-4:00 pm 4 Le Conte Hall (next to the Campanile)

Final exam solutions are available (except Problem 2). So are Midterm I solutions and Midterm II solutions.

Please congratulate Steven Sam and Adam Singer of The Mighty Levins for trashing all opposition and attaining resounding victory in the Network Tournament!

The final exam takes place at 5 pm on Tuesday, May 17, in 220 Hearst Gymnasium. Students in the Disabled Students' Program who have request extra time should report to 508 Soda Hall at the same time. The review session for the final exam takes place from 4 pm to 7 pm on Sunday, May 15, in 10 Evans Hall.

Textbooks

• Kathy Sierra and Bert Bates, Head First Java, O'Reilly, 2003. ISBN # 0-596-00465-6.
• Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, Third Edition, John Wiley & Sons, 2004. ISBN # 0-471-46983-1.
• For information on using older editions of Goodrich and Tamassia, read the course overview.

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.

Work

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

Lectures

Labs, homeworks, and projects that are currently available can be accessed by clicking on them. Webcasts of past lectures are offered by Berkeley's Educational Technology Services through their Webcast Berkeley page. Click on the icons in the schedule below to view past lectures. You will need a Web browser with a RealPlayer plug-in. Lectures are not broadcast live, but they should be available within a day or two after they happen.

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 19	Course overview	Sierra & Bates, pp. 1-7, 16-17, 82	.
2: January 21	Using objects	S & B, Chapter 2; pp. 52-56, 150-156, 589, 596	.
3: January 24	Defining classes	S & B, pp. 69-72, 74, 83, 236-245, 269-277, 289-290	.
4: January 26	Types; conditionals	S & B, pp. 8-12, 47-51, 73, 76-77, 84, 114, 282-284, 588	Lab 1
5: January 28	Iteration & arrays I	S & B, pp. 57-60, 81, 112-113, 285-287, 597	Homework 1
6: January 31	Iteration & arrays II	S & B, pp. 278-281	.
7: February 2	Linked lists I	.	Lab 2
8: February 4	Linked lists II	.	Homework 2
9: February 7	Stack frames	S & B, pp. 75, 231-235, 254-261, 591	.
10: February 9	Testing	S & B, pp. 93-107, 590, 593	Lab 3
11: February 11	Inheritance	S & B, Chapter 7; pp. 26-31, 246-253	Homework 3
12: February 14	Abstract classes	S & B, Chapter 8	.
13: February 16	Java packages	S & B, pp. 150-156, 515-519, 594-595	Lab 4
14: February 18	Exceptions	S & B, pp. 297-320	Project 1
February 21	President's Day	.	.
15: February 23	MIDTERM I	covers Lectures 1-12	Lab 5
16: February 25	More Java	.	Homework 4
17: February 28	Game Trees	.	.
18: March 2	Encapsulation	S & B, pp. 78-80	Lab 6
19: March 4	Encapsulated lists	S & B, p. 592	Homework 5
20: March 7	Asymptotic analysis	Goodrich & Tamassia, Chapter 3	.
21: March 9	Algorithm analysis	G & T, Chapter 3	Lab 7
22: March 11	Hash tables	G & T, Sections 8.1-8.3	.
23: March 14	Stacks and queues	G & T, Chapter 4	.
24: March 16	Trees and traversals	G & T, Chapter 6	Lab 8
25: March 18	Priority queues	G & T, Sections 7.1-7.3	Homework 6
March 21-25	Spring Recess
26: March 28	Binary search trees	G & T, Section 9.1	.
27: March 30	Balanced search trees	G & T, Section 9.4	Lab 9
28: April 1	Graphs	G & T, Sections 12.1-12.3	Project 2
29: April 4	Weighted graphs	G & T, Sections 12.5, 12.7-12.7.1	.
30: April 6	Sorting I	G & T, Sections 7.2.3, 7.3.5, & 10.1	Lab 10
31: April 8	Sorting II	G & T, Section 10.2	Homework 7
32: April 11	MIDTERM II	covers Lectures 1-29	.
33: April 13	Disjoint Sets	G & T, Section 10.6	Lab 11
34: April 15	Sorting III	G & T, Section 10.3 & 10.7	Homework 8
35: April 18	Sorting IV (video)	.	.
36: April 20	Sorting V	G & T, Section 10.4	Lab 12
37: April 22	Splay trees	G & T, Section 9.3	Homework 9
38: April 25	Amortized analysis	.	.
39: April 27	Randomized analysis	.	Lab 13
40: April 29	Expression parsing	.	Project 3
41: May 2	Garbage collection	.	.
42: May 4	Augmenting data structures	.	Lab 14
43: May 6	Review	.	.
May 9	.	.	Homework 10

The FINAL EXAM takes place on Tuesday, May 17, from 5 to 8 pm in 220 Hearst Gymnasium. (CS 61B is in Exam Group 12.)

Course Description (from the catalogue)

Prerequisites: CS 61A or Engineering 77N. (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 (Wednesday, February 23, 3-4 pm, 100 Lewis Hall).
• 12.5% for Midterm II (Monday, April 11, 3-4 pm, 100 Lewis Hall).
• 25% for the Final Exam (Tuesday, May 17, 5-8 pm, 220 Hearst Gymnasium).

``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?''