CS 61B: Data Structures - Shewchuk

CS 61B
Data Structures

Prof. Jonathan Shewchuk
[email protected]
(But ask most questions on the CS 61B Piazza discussion group and send most private requests to [email protected] so the TAs can respond too.)

Spring 2014
Mondays 1–2 pm and Wednesdays noon–2 pm
Wheeler Hall Auditorium

Here are some practice problems for the Final Exam.

Here are the solutions.

Please congratulate Jianqiao Yang, Chengming Liao, and Junyan Kang, who as the team ChaoWeiLanMao 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 13 at 8:00 am in 100 Haas Pavilion. Students in the Disabled Students' Program who requested extra time will receive alternative locations by email.

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. Please keep your notes under your seat so people passing in front of you don't trip over them.

The TAs will hold a review session for the Final Exam this Saturday, May 10 at 2–5 pm in 2050 Valley Life Sciences Building.

Textbooks

Required: Kathy Sierra and Bert Bates, Head First Java, O'Reilly, 2005. ISBN # 0-596-00920-8. (Either the first or second edition will do.)
Optional: 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, fifth, or sixth 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.
Access the CS 61B Piazza discussion group.
Online version of the course reader, plus extra documentation on Java and Gmake.
The Java 2 standard libraries API: frames, no frames (maintained by Oracle).
The Java language specification (maintained by Oracle).
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.

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. Webcasts and podcasts of past lectures are offered by Berkeley's Educational Technology Services through their Webcast Berkeley page. Click on the icons in the schedule below to view past lectures. Lectures are not broadcast live, but they should be available within a day or two after they happen.

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

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

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

9: February 10	Stack & heap	Sierra & Bates, pp. 77, 235–239, 258–265, 663	.
10: February 12	Inheritance	S & B, Chapter 7; pp. 28–33, 250–257	Homework 3
11: February 12	Testing; equals()	S & B, pp. 95–109, 662	.
February 14	.	.	Lab 4

February 17	President's Day	.	.
12: February 19	Abstract classes	S & B, Chapter 8	.
13: February 19	Java packages	S & B, pp. 154–160, 587–591, 667–668	.
February 21	.	.	Lab 5
February 22	.	.	Project 1

14: February 24	MIDTERM I	covers Lectures 1–12	.
15: February 26	Exceptions	S & B, pp. 315–338	Homework 4
16: February 26	More Java	S & B, pp. 189, 283	.
February 28	.	.	Lab 6

17: March 3	Game Trees	.	.
18: March 5	Encapsulation	S & B, pp. 80–84	Homework 5
19: March 5	Encapsulated lists	S & B, p. 664	.
March 7	.	.	Lab 7

20: March 10	Asymptotic analysis	Goodrich & Tamassia, Chapter 4	.
21: March 12	Dictionaries & hash tables	G & T, Sections 9.1, 9.2, 9.5–9.5.1	.
22: March 12	Hash codes; stacks & queues	G & T, Chapter 5	.
March 14	.	.	Lab 8

23: March 17	Algorithm analysis	G & T, Chapter 4	.
24: March 19	Trees and traversals	G & T, Chapter 7	Homework 6
25: March 19	Priority queues	G & T, Sections 8.1–8.3	.
March 21	.	.	Lab 9

March 24–28	Spring Recess

26: March 31	Binary search trees	G & T, Section 10.1	.
27: April 2	Balanced search trees	G & T, Section 10.4	Project 2
28: April 2	Graphs	G & T, Sections 13.1–13.3	.
April 4	.	.	Lab 10

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

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

35: April 21	Radix sort	G & T, Section 11.3.2	.
36: April 23	Splay trees	G & T, Section 10.3	Homework 9
37: April 23	Amortized analysis	.	.
April 25	.	.	Lab 13

38: April 28	Randomized analysis	.	.
39: April 30	Garbage collection	G & T, Sections 14.1.2–14.1.3	Project 3
40: April 30	Augmenting data structures	.	.
May 2	.	.	Lab 14

41: May 5	Sorting video	.	.
42: May 7	Review	.	Homework 10
May 9	.	.	Lab 15

The FINAL EXAM will take place on Tuesday, May 13, from 8 am to 11 am in 100 Haas Pavilion. (CS 61B is in Exam Group 5.)

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, February 24, 1–2 pm, Wheeler Auditorium).
12.5% for Midterm II (Monday, April 14, 1–2 pm, Wheeler Auditorium).
25% for the Final Exam (Tuesday, May 13, 8–11 am, 100 Haas Pavilion).

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

[email protected]