CS 61B: Data Structures - Shewchuk

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 2010
Mondays, Wednesdays, and Fridays, 5:00–6:00 pm
155 Dwinelle Hall

Please congratulate Oleksiy Budilovsky, Victor Yu, and Marvin Thielk, also known as Golden Bears, for destroying all opposition and winning the Network Tournament! Also, please scold them for not sending a single representative to the actual tournament. There's nothing more disappointing than when the winner isn't even around to celebrate.

The Final Exam took place Thursday, December 16, 11:30 am–2:30 pm in the Recreational Sports Facility Field House. Students in the Disabled Students' Program who requested accommodations should have arrived at 326 Soda Hall at the same time. A Review Session for the Final Exam took place Friday, December 10, 2:30–4:30 pm in 1 Hearst Annex. The exam is open book, open notes, closed electronics. Please try to leave laptops, cell phones, and MP3 players at home. If you must bring them, leave them at the front at the start of the exam.

TA Kevin Weekly is kindly providing his discussion section notes here.

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, 2010. ISBN # 0-470-38326-7. (The first, third, fourth, or fifth 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 fifth 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 web 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

The following schedule is tentative. There may 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. Sadly, there will be no webcasts this semester, but you can access the webcasts from my Autumn 2006 offering of CS 61B through the Webcast Berkeley page provided by Berkeley's Educational Technology Services.

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 27	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	Lab 1
4: September 3	Types; conditionals	S & B, pp. 10–14, 49–53, 75, 78–79, 86, 117, 286–287, 292, 660	Homework 1

September 6	Labor Day	.	.
5: September 8	Iteration & arrays I	S & B, pp. 59–62, 83, 114–116, 293–300, 670	Lab 2
6: September 10	Iteration & arrays II	S & B, pp. 282–285	Homework 2

7: September 13	Linked lists I	Goodrich & Tamassia, Section 3.2	.
8: September 15	Linked lists II	G & T, Section 3.3	Lab 3
9: September 17	Stack frames	Sierra & Bates, pp. 77, 235–239, 258–265, 663	Homework 3

10: September 20	Testing	S & B, pp. 95–109, 662	.
11: September 22	Inheritance	S & B, Chapter 7; pp. 28–33, 250–257	Lab 4
12: September 24	Abstract classes	S & B, Chapter 8	Project 1

13: September 27	Java packages	S & B, pp. 154–160, 587–591, 667–668	.
14: September 29	Exceptions	S & B, pp. 315–338	Lab 5
15: October 1	More Java	S & B, pp. 189, 283	Homework 4

16: October 4	MIDTERM I	covers Lectures 1–12	.
17: October 6	Encapsulation	.	Lab 6
18: October 8	Game Trees	S & B, pp. 80–84	Homework 5

19: October 11	Encapsulated lists	S & B, p. 664	.
20: October 13	Asymptotic analysis	Goodrich & Tamassia, Chapter 4	Lab 7
21: October 15	Algorithm analysis	G & T, Chapter 4	.

22: October 18	Dictionaries & hash tables	G & T, Sections 9.1, 9.2, 9.5–9.5.1	.
23: October 20	Hash codes, stacks, queues	G & T, Chapter 5	Lab 8
24: October 22	Trees and traversals	G & T, Chapter 7	Homework 6

25: October 25	Priority queues	G & T, Sections 8.1–8.3	.
26: October 27	Binary search trees	G & T, Section 10.1	Lab 9
27: October 29	Balanced search trees	G & T, Section 10.4	Project 2

28: November 1	Graphs	G & T, Sections 13.1–13.3	.
29: November 3	Weighted graphs	G & T, Sections 13.5.1, 13.6–13.6.1	Lab 10
30: November 5	Four sorting algorithms	G & T, Sections 8.2.2, 8.3.5, & 11.1	Homework 7

31: November 8	MIDTERM II	covers Lectures 1–29	.
32: November 10	Quicksort	G & T, Section 11.2	Lab 11
November 11	Veterans Day	no discussion sections this week	.
33: November 12	Disjoint Sets	G & T, Section 11.4	Homework 8

34: November 15	Sorting & selection	G & T, Section 11.3.1 & 11.5	.
35: November 17	Radix sort	G & T, Section 11.3.2	Lab 12
36: November 19	Sorting video	.	Homework 9

37: November 22	Splay trees	G & T, Section 10.3	.
38: November 24	Amortized analysis	.	Lab 13
November 25–26	Thanksgiving	.	.

39: November 29	Randomized analysis	.	.
40: December 1	Garbage collection	G & T, Sections 14.1.2–14.1.3	Lab 14
41: December 3	Augmenting data structures	.	Project 3

42: December 6	Review	.	.
December 8	Network Tournament (5:30, 306 Soda)	.	Lab 15
December 10	(no lecture)	.	Homework 10

The FINAL EXAM will take place on Thursday, December 16, from 11:30 am to 2:30 pm in a location the university will announce late in the semester. (CS 61B is in Exam Group 14.)

Course Description (from the catalogue)

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: CS 61A or Engineering 7. (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 4, 5–6 pm, 155 Dwinelle Hall).
12.5% for Midterm II (Monday, November 8, 5–6 pm, 155 Dwinelle Hall).
25% for the Final Exam (Thursday, December 16, 11:30 am–2:30 pm, Recreational Sports Facility Field House).

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

cs61b@cory.eecs