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.) Autumn 2006 Mondays, Wednesdays, and Fridays, 4:00-5:00 pm 145 Dwinelle Hall

The lower division instructional staff would like you to fill out this survey to help them improve CS 61B. As an enticement, everyone who completes the survey by Sunday night will receive the equivalent of one bonus lab point. It might put you over the edge if you're close to the line.

The Final Exam will take place on Saturday, December 16, from 8 to 11 am at 2050 Valley Life Sciences Building. If you are in the Disabled Students' Program, your exam will start at the same time in 508 Soda Hall. The review session will be Thursday, December 14, from 3 to 6 pm in 102 Wurster Hall. The final exam will be open book, open notes, closed electronics, as usual.

You can find practice questions here (also in PostScript and PDF). The answers are available here (also in PostScript and PDF).

Your TA Michael Le has kindly provided this Final Exam review sheet. Your TA Leonard Wei has provided this Midterm II review sheet and and solutions for your consideration. The Midterm I review sheet and solutions are also still available.

The Network Tournament took place on Monday, December 11 from 6-9 pm in 306 Soda Hall.

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

Labs, homeworks, and projects that are currently available can be accessed by clicking on them. Webcasts and podcasts 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. For the streaming webcasts, 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: August 28	Course overview	Sierra & Bates, pp. 1-9, 18-19, 84	.
2: August 30	Using objects	S & B, Chapter 2; pp. 54-58, 154-160, 661, 669	.
3: September 1	Defining classes	S & B, pp. 71-74, 76, 85, 240-249, 273-281, 308-309	.
September 4	Labor Day	.	.
4: September 6	Types; conditionals	S & B, pp. 10-14, 49-53, 75, 78-79, 86, 117, 286-287, 292, 660	Lab 1
5: September 8	Iteration & arrays I	S & B, pp. 59-62, 83, 114-116, 293-300, 670	Homework 1
6: September 11	Iteration & arrays II	S & B, pp. 282-285	.
7: September 13	Linked lists I	Goodrich & Tamassia, Section 3.2	Lab 2
8: September 15	Linked lists II	G & T, Section 3.3	Homework 2
9: September 18	Stack frames	Sierra & Bates, pp. 77, 235-239, 258-265, 663	.
10: September 20	Testing	S & B, pp. 95-109, 662	Lab 3
11: September 22	Inheritance	S & B, Chapter 7; pp. 28-33, 250-257	Homework 3
12: September 25	Abstract classes	S & B, Chapter 8	.
13: September 27	Java packages	S & B, pp. 154-160, 587-591, 667-668	Lab 4
14: September 29	Exceptions	S & B, pp. 315-338	Project 1
15: October 2	MIDTERM I	covers Lectures 1-12	.
16: October 4	More Java	S & B, pp. 189, 283	Lab 5
17: October 6	Game Trees	.	Homework 4
18: October 9	Encapsulation	S & B, pp. 80-84	.
19: October 11	Encapsulated lists	S & B, p. 664	Lab 6
20: October 13	Asymptotic analysis	Goodrich & Tamassia, Chapter 4	Homework 5
21: October 16	Algorithm analysis	G & T, Chapter 4	.
22: October 18	Dictionaries & hash tables	G & T, Sections 9.1-9.3	Lab 7
23: October 20	Hashing; stacks & queues	G & T, Chapter 5	.
24: October 23	Trees and traversals	G & T, Chapter 7	.
25: October 25	Priority queues	G & T, Sections 8.1-8.3	Lab 8
26: October 27	Binary search trees	G & T, Section 10.1	Homework 6
27: October 30	Balanced search trees	G & T, Section 10.4	.
28: November 1	Graphs	G & T, Sections 13.1-13.3	Lab 9
29: November 3	Weighted graphs	G & T, Sections 13.5, 13.7-13.7.1	Project 2
30: November 6	Four sorting algorithms	G & T, Sections 8.2.3, 8.3.5, & 11.1	.
31: November 8	Quicksort	G & T, Section 11.2	Lab 10
November 10	Veterans Day	.	Homework 7
32: November 13	MIDTERM II	covers Lectures 1-29	.
33: November 15	Disjoint Sets	G & T, Section 11.6	Lab 11
34: November 17	Sorting & selection	G & T, Section 11.3 & 11.7	Homework 8
35: November 20	Sorting video	.	.
36: November 22	Radix sort	G & T, Section 11.4	.
November 24	Thanksgiving	.	.
37: November 27	Splay trees	G & T, Section 10.3	Homework 9
38: November 29	Amortized analysis	.	Lab 12
39: December 1	Randomized analysis	.	Project 3
40: December 4	Expression parsing	.	.
41: December 6	Garbage collection	G & T, Sections 14.1.2-14.1.3	Lab 13
42: December 8	Augmenting data structures	.	Homework 10

The FINAL EXAM takes place on Saturday, December 16, from 8 to 11 am at 2050 Valley Life Sciences Building. (CS 61B is in Exam Group 13.)

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 (Monday, October 2, 4-5 pm, 145 Dwinelle Hall).
• 12.5% for Midterm II (Monday, November 13, 4-5 pm, 145 Dwinelle Hall).
• 25% for the Final Exam (Saturday, December 16, 8-11 am, 2050 Valley Life Sciences Building).

“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?”