(Cover illustration: Anatjari Tjampitjinpa, ``Snake Dreaming,'' 1988.) 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 2002 Beginning January 23 Mondays, Wednesdays, and Fridays, 2:00-3:00 pm 1 Pimental Hall

Review questions for the final exam are available (text, PostScript).

Solutions to two of the final exams in the reader are now available via the Exams link. Give your classmate Michelle Kam a pat on the back for typing them in for you.

Network tournament winners: The winning team is Champs Part II! Please congratulate Minqiu Cao, Mike Tai, and Hector Angulo on their hard-won Network Title on May 8. Despite going to the sudden death round in their last three contests - twice even losing the first round of their two-out-of-three matches - the Champs proved their ability to come back from behind again and again, and prevail over all comers. Our stalwart heroes win gift certificates to Amoeba Records and your unstinting admiration.

Ian Joyner's critique of C++ is available as PostScript or HTML.

Textbooks

• David Arnow and Gerald Weiss, Introduction to Programming Using Java: An Object-Oriented Approach, Java 2 Update, Addison-Wesley, 2000. ISBN # 0-201-75159-3 or ISBN # 0-201-61272-0.
• Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, Second Edition, John Wiley & Sons, 2001. ISBN # 0-471-38367-8. (The first edition can be used too, but all the sections are numbered differently.)

Information

• Course overview: prerequisites, laboratory and discussion sections, grading, cheating policies.
• Admission to the class.
• 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.
• 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.
• Information on using Java at home, and information on connecting from home.
• User's Guide to EECS Instructional Computing.
• Access the ucb.class.cs61b newsgroup.

Work

• Homeworks and Projects.
• Labs.
• Exams.

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, which offers both live CS 61B webcasts and past lectures. Click on this icon to view a live lecture (only works when a lecture is in progress), or on the same icons below to view past classes. You will need a Web browser with a RealPlayer plug-in.

Some lecture notes can be obtained by clicking on the lecture titles (for ASCII) or the PostScript 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 23	Course overview	Arnow & Weiss, Chapter 1	.
2: January 25	Using objects	A & W, Chapters 2 & 3	Lab 1
3: January 28	Defining classes	A & W, Chapter 4	.
4: January 30	Types; conditionals	A & W, Chapters 5 & 6	Homework 1
5: February 1	Iteration & arrays I	A & W, Sections 8.1-8.5, 10.8-10.12	Lab 2
6: February 4	Iteration & arrays II	A & W, Chapter 9	.
7: February 6	Linked lists I	.	Homework 2
8: February 8	Linked lists II	.	Lab 3
9: February 11	Activation records	A & W, Chapter 11	.
10: February 13	Testing	A & W, Chapter 7	Homework 3
11: February 15	Inheritance	A & W, Chapter 13	Lab 4
February 18	President's Day	.	.
12: February 20	Abstract classes	A & W, Chapter 13	.
13: February 22	Java packages	.	Lab 5
February 23	.	(Project 1 due Saturday at 5 pm)	Project 1
14: February 25	MIDTERM I	covers Lectures 1-12	.
15: February 27	Exceptions	A & W, Chapter 14	Homework 4
16: March 1	More Java	.	Lab 6
17: March 4	Game Trees	.	.
18: March 6	Encapsulation	.	Homework 5
19: March 8	Encapsulated lists	.	Lab 7
20: March 11	Asymptotic analysis	Goodrich & Tamassia, Chapter 3	.
21: March 13	Algorithm analysis	G & T, Chapter 3	.
22: March 15	Hash tables	G & T, Sections 8.1-8.3	Lab 8
23: March 18	Stacks and queues	G & T, Chapter 4	.
24: March 20	Trees and traversals	G & T, Chapter 6	Homework 6
25: March 22	Priority queues	G & T, Sections 7.1-7.3	Lab 9
March 25-29	Spring Recess	.	.
26: April 1	Binary search trees	G & T, Section 9.1	.
27: April 3	Balanced search trees	G & T, Sections 9.3 & 9.4	Project 2
28: April 5	Graphs	G & T, Sections 12.1-12.3	Lab 10
29: April 8	Weighted graphs	G & T, Sections 12.5, 12.7-12.7.1	.
30: April 10	Sorting I	G & T, Sections 7.2.3, 7.3.4, & 10.1	Homework 7
31: April 12	Sorting II	G & T, Section 10.3	Lab 11
32: April 15	MIDTERM II	covers Lectures 1-29	.
33: April 17	Disjoint Sets	Handout (outside 625 Soda)	Homework 8
34: April 19	Sorting III (video)	.	Lab 12
35: April 22	Sorting IV	G & T, Section 10.4 & 10.7	.
36: April 24	Sorting V	G & T, Section 10.5	Homework 9
37: April 26	Expression parsing	.	Lab 13
38: April 29	Splay trees	Handout	.
39: May 1	Amortized Analysis	.	.
40: May 3	Randomized Analysis	.	Lab 14
May 4	.	(Project 3 due Saturday at 2 pm)	Project 3
41: May 6	C pointers	.	.
42: May 8	Garbage collection	.	Homework 10
43: May 10	Review	.	Lab 15

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

Course Description

Prerequisites: A grade of B- or better in CS 61A or Engineering 77N. (The B- requirement is rarely enforced.)

Grading

• 5% for the labs.
• 10% for the homeworks.
• 35% for three projects.
• 12.5% for Midterm I (Monday, February 25, 2-3 pm, in class).
• 12.5% for Midterm II (Monday, April 15, 2-3 pm, in class).
• 25% for the Final Exam (Friday, May 24, 5-8 pm).