CS 61B: Data Structures - Shewchuk (original) (raw)

CS 61B Data Structures Prof. Jonathan Shewchukjrs@cory.eecs(But send class-related mail to cs61b@cory.eecs so the TAs can respond too.)Spring 2012Mondays, Wednesdays, and Fridays, 2:00–3:00 pm1 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 placeTuesday, May 8 at 11:30–2:30 pm in220, 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

Information

Work

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 theWebcast Berkeley pageprovided by Berkeley's Educational Technology Services.

Some lecture notes can be obtained by clicking on the lecture titles (for ASCII) or the PostScriptor PDFlinks (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 FINALEXAM**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


“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