CS 61B Data Structures
Prof. Jonathan Shewchuk |
The lower division instructional staff would like you to fill out this survey to help them improve CS 61B. As an enticement, everyone who completes the survey by Sunday night will receive the equivalent of one bonus lab point. It might put you over the edge if you're close to the line.
The Final Exam will take place on Saturday, December 16, from 8 to 11 am at 2050 Valley Life Sciences Building. If you are in the Disabled Students' Program, your exam will start at the same time in 508 Soda Hall. The review session will be Thursday, December 14, from 3 to 6 pm in 102 Wurster Hall. The final exam will be open book, open notes, closed electronics, as usual.
You can find practice questions here (also in PostScript and PDF). The answers are available here (also in PostScript and PDF).
Your TA Michael Le has kindly provided this Final Exam review sheet. Your TA Leonard Wei has provided this Midterm II review sheet and and solutions for your consideration. The Midterm I review sheet and solutions are also still available.
The Network Tournament took place on Monday, December 11 from 6-9 pm in 306 Soda Hall.
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. For the streaming webcasts, you will need a Web browser with a RealPlayer plug-in. 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: August 28 | 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 | . |
September 4 | Labor Day | . | . |
4: September 6 | Types; conditionals | S & B, pp. 10-14, 49-53, 75, 78-79, 86, 117, 286-287, 292, 660 | Lab 1 |
5: September 8 | Iteration & arrays I | S & B, pp. 59-62, 83, 114-116, 293-300, 670 | Homework 1 |
6: September 11 | Iteration & arrays II | S & B, pp. 282-285 | . |
7: September 13 | Linked lists I | Goodrich & Tamassia, Section 3.2 | Lab 2 |
8: September 15 | Linked lists II | G & T, Section 3.3 | Homework 2 |
9: September 18 | Stack frames | Sierra & Bates, pp. 77, 235-239, 258-265, 663 | . |
10: September 20 | Testing | S & B, pp. 95-109, 662 | Lab 3 |
11: September 22 | Inheritance | S & B, Chapter 7; pp. 28-33, 250-257 | Homework 3 |
12: September 25 | Abstract classes | S & B, Chapter 8 | . |
13: September 27 | Java packages | S & B, pp. 154-160, 587-591, 667-668 | Lab 4 |
14: September 29 | Exceptions | S & B, pp. 315-338 | Project 1 |
15: October 2 | MIDTERM I | covers Lectures 1-12 | . |
16: October 4 | More Java | S & B, pp. 189, 283 | Lab 5 |
17: October 6 | Game Trees | . | Homework 4 |
18: October 9 | Encapsulation | S & B, pp. 80-84 | . |
19: October 11 | Encapsulated lists | S & B, p. 664 | Lab 6 |
20: October 13 | Asymptotic analysis | Goodrich & Tamassia, Chapter 4 | Homework 5 |
21: October 16 | Algorithm analysis | G & T, Chapter 4 | . |
22: October 18 | Dictionaries & hash tables | G & T, Sections 9.1-9.3 | Lab 7 |
23: October 20 | Hashing; stacks & queues | G & T, Chapter 5 | . |
24: October 23 | Trees and traversals | G & T, Chapter 7 | . |
25: October 25 | Priority queues | G & T, Sections 8.1-8.3 | Lab 8 |
26: October 27 | Binary search trees | G & T, Section 10.1 | Homework 6 |
27: October 30 | Balanced search trees | G & T, Section 10.4 | . |
28: November 1 | Graphs | G & T, Sections 13.1-13.3 | Lab 9 |
29: November 3 | Weighted graphs | G & T, Sections 13.5, 13.7-13.7.1 | Project 2 |
30: November 6 | Four sorting algorithms | G & T, Sections 8.2.3, 8.3.5, & 11.1 | . |
31: November 8 | Quicksort | G & T, Section 11.2 | Lab 10 |
November 10 | Veterans Day | . | Homework 7 |
32: November 13 | MIDTERM II | covers Lectures 1-29 | . |
33: November 15 | Disjoint Sets | G & T, Section 11.6 | Lab 11 |
34: November 17 | Sorting & selection | G & T, Section 11.3 & 11.7 | Homework 8 |
35: November 20 | Sorting video | . | . |
36: November 22 | Radix sort | G & T, Section 11.4 | . |
November 24 | Thanksgiving | . | . |
37: November 27 | Splay trees | G & T, Section 10.3 | Homework 9 |
38: November 29 | Amortized analysis | . | Lab 12 |
39: December 1 | Randomized analysis | . | Project 3 |
40: December 4 | Expression parsing | . | . |
41: December 6 | Garbage collection | G & T, Sections 14.1.2-14.1.3 | Lab 13 |
42: December 8 | Augmenting data structures | . | Homework 10 |
The FINAL EXAM takes place on Saturday, December 16, from 8 to 11 am at 2050 Valley Life Sciences Building. (CS 61B is in Exam Group 13.)
Prerequisites: CS 61A or Engineering 77N. (The catalogue says “with a grade of B- or better,” but I've never seen this rule enforced.)
|