(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

Check out Steven Jones' Maze Page based on Homework 9!

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

Information

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. 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

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


Mail inquiries to cs61b@cory.eecs