CS 61B: Data Structures

(Cover illustration: Anatjari Tjampitjinpa, ``Snake Dreaming,'' 1988.)

CS 61B
Data Structures

Prof. Jonathan Shewchuk

Spring 2000
Mondays, Wednesdays, and Fridays, 3:00-4:00 pm
1 Pimental Hall

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

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-61272-0.
Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, John Wiley & Sons, 1998. ISBN # 0-471-19308-9.

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.
CSUA help session schedules (Unix, Emacs, and more) and documentation.
Access the ucb.class.cs61b newsgroup.

Work

Lectures

The following schedule is tentative. There will definitely 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. See the Software page of the Berkeley Internet Broadcasting System Web page for information on viewing lectures over the net, either live or after the fact .

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. Do not be surprised if they say the same thing I said in class; I edit them after class to make sure of this. If I receive any more 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 that class.

	Topic	Reading	Due
1: January 19	Course overview	Arnow & Weiss, Chapter 1	.
2: January 21	Using objects	A & W, Chapters 2 & 3	Lab 1

3: January 24	Defining classes	A & W, Chapter 4	.
4: January 26	Types; conditionals	A & W, Chapters 5 & 6	Homework 1
5: January 28	Iteration & arrays I	A & W, Sections 8.1-8.5, 10.8-10.12	Lab 2

6: January 31	Iteration & arrays II	A & W, Chapter 9	.
7: February 2	Linked lists I	.	Homework 2
8: February 4	Linked lists II	.	Lab 3

9: February 7	Activation records	A & W, Chapter 11	.
10: February 9	Testing	A & W, Chapter 7	Homework 3
11: February 11	Inheritance	A & W, Chapter 13	Lab 4

12: February 14	Abstract classes	A & W, Chapter 13	.
13: February 16	Java packages	.	Project 1
14: February 18	Exceptions	A & W, Chapter 14	Lab 5

February 21	President's Day	.	.
15: February 23	MIDTERM I	covers Lectures 1-12	Homework 4
16: February 25	More Java	.	Lab 6

17: February 28	Game Trees	.	.
18: March 1	Encapsulation	.	Homework 5
19: March 3	Encapsulated lists	.	Lab 7

20: March 6	Asymptotic analysis	Goodrich & Tamassia, Chapter 2	.
21: March 8	Algorithm analysis	G & T, Chapter 2	.
22: March 10	Hash tables	G & T, Sections 7.1, 7.2, & 7.6	Lab 8

23: March 13	Stacks and queues	G & T, Chapter 3	.
24: March 15	Trees and traversals	G & T, Sections 5.1-5.4	Homework 6
25: March 17	Priority queues	G & T, Sections 6.1-6.3	Lab 9

26: March 20	Binary search trees	G & T, Section 7.3	.
27: March 22	Balanced search trees	G & T, Sections 13.1 & 13.2	Project 2
28: March 24	Graphs	G & T, Sections 9.1-9.3	Lab 10

March 27-31	Spring Recess	.	.

29: April 3	Weighted Graphs	G & T, Sections 10.2-10.2.1	.
30: April 5	Sorting I	G & T, Sections 6.2.3, 6.3.3, & 8.1	Homework 7
31: April 7	Sorting II	G & T, Section 8.3	Lab 11

32: April 10	MIDTERM II	covers Lectures 1-29	.
33: April 12	Disjoint Sets	G & T, Section 12.1	Homework 8
34: April 14	Sorting III	G & T, Section 8.5	Lab 12

35: April 17	Sorting IV (video)	G & T, Section 8.6	.
36: April 19	Splay trees	G & T, Section 13.4 (13.4.3 optional)	Homework 9
37: April 21	C pointers	.	Lab 13

38: April 24	Memory management I	.	.
39: April 26	Memory management II	.	Project 3
40: April 28	C++ classes I	.	Lab 14

41: May 1	C++ classes II	.	.
42: May 3	C++ sucks	.	Homework 10
43: May 5	Review	.	Lab 15

The FINAL EXAM takes place on Tuesday, May 16, from 5 to 8 pm in the Wheeler Hall Auditorium. (CS 61B is in Exam Group 11.)

Course Description

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: 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 (Wednesday, February 23, 3-4 pm).
12.5% for Midterm II (Monday, April 10, 3-4 pm).
25% for the Final Exam (Tuesday, May 16, 5-8 pm, 100 Haas Pavilion).

Mail inquiries to cs61b@cory.eecs