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 2006Mondays, Wednesdays, and Fridays, 4:00-5:00 pm145 Dwinelle Hall

The lower division instructional staff would like you to fill outthis surveyto 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 andPDF). The answers are available here(also in PostScript andPDF).

Your TA Michael Le has kindly provided this**Final Exam review sheet. Your TA Leonard Wei has provided thisMidterm II review sheet** and and solutionsfor 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.

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. Webcasts and podcasts of past lectures are offered by Berkeley's Educational Technology Services through theirWebcast Berkeley page. Click on the iconsin the schedule below to view past lectures. For the streaming webcasts, you will need a Web browser with aRealPlayer 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 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 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 EXAMtakes place on Saturday, December 16, from 8 to 11 am at 2050 Valley Life Sciences Building. (CS 61B is in Exam Group 13.)

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 77N. (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?”

Mail inquiries tocs61b@cory.eecs