(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 2004 Mondays, Wednesdays, and Fridays, 5:00-6:00 pm 1 Pimentel Hall

Some practice problems for the final exam are available as text or PostScript.

Please congratulate Graham Melcher, Bryce Lee, and Leonard Wei--the Killer Coding Ninja Monkeys--for smashing all opposition and winning the Network tournament!

Here's some information on timing Java programs with fine precision.

Textbooks

• David Arnow, Scott Dexter, and Gerald Weiss (No, not THAT Gerald Weiss), Introduction to Programming Using Java: An Object-Oriented Approach, Second Edition, Addison-Wesley, 2004. ISBN # 0-321-20006-3.
• 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, read the course overview.

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 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 21	Course overview	Arnow Dexter Weiss, Chapter 1	.
2: January 23	Using objects	ADW, Chapters 2 & 3	.
3: January 26	Defining classes	ADW, Chapters 4 & 5	.
4: January 28	Types; conditionals	ADW, Chapter 6	Lab 1
5: January 30	Iteration & arrays I	ADW, Sections 9.1-9.5, 9.12-9.14	Homework 1
6: February 2	Iteration & arrays II	ADW, Chapter 10	.
7: February 4	Linked lists I	.	Lab 2
8: February 6	Linked lists II	.	Homework 2
9: February 9	Activation records	ADW, Chapter 14	.
10: February 11	Testing	ADW, Chapter 8	Lab 3
11: February 13	Inheritance	ADW, Sections 12.1-12.6	Homework 3
February 16	President's Day	.	.
12: February 18	Abstract classes	ADW, Chapter 12	Lab 4
13: February 20	Java packages	.	Project 1
14: February 23	MIDTERM I	covers Lectures 1-12	.
15: February 25	Exceptions	ADW, Chapter 13	Lab 5
16: February 27	More Java	.	.
February 29	due 5 pm	.	Homework 4
17: March 1	Game Trees	.	.
18: March 3	Encapsulation	.	Lab 6
19: March 5	Encapsulated lists	.	Homework 5
20: March 8	Asymptotic analysis	Goodrich & Tamassia, Chapter 3	.
21: March 10	Algorithm analysis	G & T, Chapter 3	Lab 7
22: March 12	Hash tables	G & T, Sections 8.1-8.3	.
23: March 15	Stacks and queues	G & T, Chapter 4	.
24: March 17	Trees and traversals	G & T, Chapter 6	Lab 8
25: March 19	Priority queues	G & T, Sections 7.1-7.3	Homework 6
March 22-26	Spring Recess	.	.
26: March 29	Binary search trees	G & T, Section 9.1	.
27: March 31	Balanced search trees	G & T, Section 9.4	Lab 9
28: April 2	Graphs	G & T, Sections 12.1-12.3	Project 2
29: April 5	Weighted graphs	G & T, Sections 12.5, 12.7-12.7.1	.
30: April 7	Sorting I	G & T, Sections 7.2.3, 7.3.5, & 10.1	Lab 10
31: April 9	Sorting II	G & T, Section 10.2	Homework 7
32: April 12	MIDTERM II	covers Lectures 1-29	.
33: April 14	Disjoint Sets	G & T, Section 10.6	Lab 11
34: April 16	Sorting III (video)	.	.
April 18	due 5 pm	.	Homework 8
35: April 19	Sorting IV	G & T, Section 10.3 & 10.7	.
36: April 21	Sorting V	G & T, Section 10.4	Lab 12
April 23	Lecture cancelled	.	Homework 9
37: April 26	Splay trees	G & T, Section 9.3	.
38: April 28	Amortized analysis	.	Lab 13
39: April 30	Randomized analysis	.	Project 3
40: May 3	Expression parsing	.	.
41: May 5	Garbage collection	.	Lab 14
42: May 7	Augmenting data structures	.	Homework 10
43: May 10	Review	.	.

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

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 23, 5-6 pm, in class).
• 12.5% for Midterm II (Monday, April 12, 5-6 pm, in class).
• 25% for the Final Exam (Thursday, May 20, 5-8 pm, Wheeler Hall Auditorium).