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.)Autumn 2010Mondays, Wednesdays, and Fridays, 5:00–6:00 pm155 Dwinelle Hall

Please congratulate Oleksiy Budilovsky, Victor Yu, andMarvin 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 placeThursday, December 16, 11:30 am–2:30 pm in theRecreational Sports Facility Field House. Students in the Disabled Students' Program who requested accommodations should have arrived at326 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

Information

Work

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 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: 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 FINALEXAMwill 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


“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