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

Spring 2012
Mondays, Wednesdays, and Fridays, 2:00–3:00 pm
1 Pimental Hall

Please congratulate Peter Chen, Rocky Duan, and Jack Qiao, who as the team DUMBPLAYER slaughtered the opposition and drank the blood of their enemies in the Network Tournament! They win gift certificates to Amoeba Records.

The Final Exam will take place Tuesday, May 8 at 11:30–2:30 pm in 220, 230, and 234 Hearst Gymnasium. Students in the Disabled Students' Program who have requested extra time should report to 326 Soda Hall at the same time.

Please do not sit next to another person at the exam; you should have empty seats on both sides of you. The exam is open book, open notes, and closed electronics: if we catch you with electronic devices such as cell phones, laptops, or iPods on your person, you will get zero on the exam. Leave them at the front of the room. If your cell phone rings at the front of the room, you lose a point.

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 CS 61B Piazza discussion group.

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. You are responsible for knowing and keeping up with the readings listed below; there won't be reminders in class.

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: January 18	Course overview	Sierra & Bates, pp. 1–9, 18–19, 84	.
2: January 20	Using objects	S & B, Chapter 2; pp. 54–58, 154–160, 661, 669	.

3: January 23	Defining classes	S & B, pp. 71–74, 76, 85, 240–249, 273–281, 308–309	.
4: January 25	Types; conditionals	S & B, pp. 10–14, 49–53, 75, 78–79, 86, 117, 286–287, 292, 660	Lab 1
5: January 27	Iteration & arrays I	S & B, pp. 59–62, 83, 114–116, 293–300, 670	Homework 1

6: January 30	Iteration & arrays II	S & B, pp. 282–285	.
7: February 1	Linked lists I	Goodrich & Tamassia, Section 3.2	Lab 2
8: February 3	Linked lists II	G & T, Section 3.3	Homework 2

9: February 6	Stack frames	Sierra & Bates, pp. 77, 235–239, 258–265, 663	.
10: February 8	Testing	S & B, pp. 95–109, 662	Lab 3
11: February 10	Inheritance	S & B, Chapter 7; pp. 28–33, 250–257	Homework 3

12: February 13	Abstract classes	S & B, Chapter 8	.
13: February 15	Java packages	S & B, pp. 154–160, 587–591, 667–668	Lab 4
14: February 17	Exceptions	S & B, pp. 315–338	Project 1

February 20	President's Day	.	.
15: February 22	MIDTERM I	covers Lectures 1–12	Lab 5
16: February 24	More Java	S & B, pp. 189, 283	Homework 4

17: February 27	Game Trees	.	.
18: February 29	Encapsulation	S & B, pp. 80–84	Lab 6
19: March 2	Encapsulated lists	S & B, p. 664	Homework 5

20: March 5	Asymptotic analysis	Goodrich & Tamassia, Chapter 4	.
21: March 7	Algorithm analysis	G & T, Chapter 4	Lab 7
22: March 9	Dictionaries & hash tables	G & T, Sections 9.1, 9.2, 9.5–9.5.1	.

23: March 12	Hash codes; Stacks & queues	G & T, Chapter 5	.
24: March 14	Trees and traversals	G & T, Chapter 7	Lab 8
25: March 16	Priority queues	G & T, Sections 8.1–8.3	Homework 6

26: March 19	Binary search trees	G & T, Section 10.1	.
27: March 21	Balanced search trees	G & T, Section 10.4	Lab 9
28: March 23	Graphs	G & T, Sections 13.1–13.3	Project 2

March 26–30	Spring Recess

29: April 2	Weighted graphs	G & T, Sections 13.5.1, 13.6–13.6.1	.
30: April 4	Four sorting algorithms	G & T, Sections 8.2.2, 8.3.5, & 11.1	Lab 10
31: April 6	Quicksort	G & T, Section 11.2	Homework 7

32: April 9	MIDTERM II	covers Lectures 1–29	.
33: April 11	Disjoint Sets	G & T, Section 11.4	Lab 11
34: April 13	Sorting & selection	G & T, Section 11.3.1 & 11.5	Homework 8

35: April 16	Radix sort	G & T, Section 11.3.2	.
36: April 18	Splay trees	G & T, Section 10.3	Lab 12
37: April 20	Amortized analysis	.	Homework 9

38: April 23	Randomized analysis	.	.
39: April 25	Garbage collection	G & T, Sections 14.1.2–14.1.3	Lab 13
40: April 27	Augmenting data structures	.	Project 3

41: April 30	Sorting video	.	.
42: May 2	Review	.	Lab 14
May 4	.	.	Homework 10

The FINAL EXAM took place on Tuesday, May 8, from 11:30 am to 2:30 pm in 220, 230, and 234 Hearst Gymnasium. (CS 61B is in Exam Group 6.)

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 (Wednesday, February 22, 2–3 pm, 1 Pimental Hall).
12.5% for Midterm II (Monday, April 9, 2–3 pm, 1 Pimental Hall).
25% for the Final Exam (Tuesday, May 8, 11:30 am–2:30 pm, 220, 230, and 234 Hearst Gymnasium).

“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 Katy Perry first?”

cs61b@cory.eecs