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 2009Mondays, Wednesdays, and Fridays, 5:00–6:00 pm155 Dwinelle Hall |
|---|
Mike Clancy would like all CS 61B students toplease take this survey. One point on your final exam depends on it.Solutions to the final exam are here.
Please congratulate Daniel Flanigan and Dylan Scott, also known as Deep Blue, for destroying all opposition and winning the Network Tournament!
Review questions for the Final Examare available. 
Here are thesample solutions to selected questions.
The Final Exam took place onWednesday, May 20 from 5 to 8 pm in Wheeler Auditorium. If you are in the Disabled Students' Program, your exam started at the same time in 380 Soda Hall. The review session was Monday, May 18 from 8:30 to 10:30 pm in 10 Evans Hall. 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.
Textbooks
- Kathy Sierra andBert Bates,Head First Java, O'Reilly, 2005. ISBN # 0-596-00920-8. (Either the first or second edition will do.)
- Michael T. Goodrich andRoberto Tamassia, Data Structures and Algorithms in Java, John Wiley & Sons, 2006. ISBN # 0-471-73884-0. (The first, third, or fourth 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 fourth 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.
- Online version of the course reader, plus extra documentation on Java and Gmake.
- The Java 2 standard libraries API: frames, no frames (maintained by Sun).
- The Java language specification (maintained by Sun).
- 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.
- Access the ucb.class.cs61b newsgroup. From off campus, use the portalhttp://inst.eecs.berkeley.edu/webnews using your class account.
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.
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 last time I taught the course 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 21 | Course overview | Sierra & Bates, pp. 1-9, 18-19, 84 | . |
| 2: January 23 | Using objects | S & B, Chapter 2; pp. 54-58, 154-160, 661, 669 | Lab 1 |
| 3: January 26 | Defining classes | S & B, pp. 71-74, 76, 85, 240-249, 273-281, 308-309 | . |
| 4: January 28 | Types; conditionals | S & B, pp. 10-14, 49-53, 75, 78-79, 86, 117, 286-287, 292, 660 | Homework 1 |
| 5: January 30 | Iteration & arrays I | S & B, pp. 59-62, 83, 114-116, 293-300, 670 | Lab 2 |
| 6: February 2 | Iteration & arrays II | S & B, pp. 282-285 | . |
| 7: February 4 | Linked lists I | Goodrich & Tamassia, Section 3.2 | Homework 2 |
| 8: February 6 | Linked lists II | G & T, Section 3.3 | Lab 3 |
| 9: February 9 | Stack frames | Sierra & Bates, pp. 77, 235-239, 258-265, 663 | . |
| 10: February 11 | Testing | S & B, pp. 95-109, 662 | Homework 3 |
| 11: February 13 | Inheritance | S & B, Chapter 7; pp. 28-33, 250-257 | Lab 4 |
| February 16 | President's Day | . | . |
| 12: February 18 | Abstract classes | S & B, Chapter 8 | Project 1 |
| 13: February 20 | Java packages | S & B, pp. 154-160, 587-591, 667-668 | Lab 5 |
| 14: February 23 | MIDTERM I | covers Lectures 1-12 | . |
| 15: February 25 | Exceptions | S & B, pp. 315-338 | Homework 4 |
| 16: February 27 | More Java | S & B, pp. 189, 283 | Lab 6 |
| 17: March 2 | Game Trees | . | . |
| 18: March 4 | Encapsulation | S & B, pp. 80-84 | Homework 5 |
| 19: March 6 | Encapsulated lists | S & B, p. 664 | Lab 7 |
| 20: March 9 | Asymptotic analysis | Goodrich & Tamassia, Chapter 4 | . |
| 21: March 11 | Algorithm analysis | G & T, Chapter 4 | . |
| 22: March 13 | Stacks & queues; dictionaries | G & T, Sections 9.1-9.3 | Lab 8 |
| 23: March 16 | Hash tables & hash codes | G & T, Chapter 5 | . |
| 24: March 18 | Trees and traversals | G & T, Chapter 7 | . |
| 25: March 20 | Priority queues | G & T, Sections 8.1-8.3 | Lab 9 |
| March 22 | . | . | Homework 6 |
| March 23-27 | Spring Recess | ||
| 26: March 30 | Binary search trees | G & T, Section 10.1 | . |
| 27: April 1 | Balanced search trees | G & T, Section 10.4 | Project 2 |
| 28: April 3 | Graphs | G & T, Sections 13.1-13.3 | Lab 10 |
| 29: April 6 | Weighted graphs | G & T, Sections 13.5, 13.7-13.7.1 | . |
| 30: April 8 | Four sorting algorithms | G & T, Sections 8.2.3, 8.3.5, & 11.1 | Homework 7 |
| 31: April 10 | Quicksort | G & T, Section 11.2 | Lab 11 |
| 32: April 13 | MIDTERM II | covers Lectures 1-29 | . |
| 33: April 15 | Disjoint Sets | G & T, Section 11.6 | Homework 8 |
| 34: April 17 | Sorting & selection | G & T, Section 11.3 & 11.7 | Lab 12 |
| 35: April 20 | Radix sort | G & T, Section 11.4 | . |
| 36: April 22 | Sorting video | . | Homework 9 |
| 37: April 24 | Splay trees | G & T, Section 10.3 | Lab 13 |
| 38: April 27 | Amortized analysis | . | . |
| 39: April 29 | Randomized analysis | . | Project 3 |
| 40: May 1 | Expression parsing | . | Lab 14 |
| 41: May 4 | Garbage collection | G & T, Sections 14.1.2-14.1.3 | . |
| 42: May 6 | Augmenting data structures | . | Homework 10 |
| 43: May 8 | Review | . | Lab 15 |
**The FINALEXAM**took place on Wednesday, May 20, from 5 to 8 pm in Wheeler Auditorium. (CS 61B is in Exam Group 18.)
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 thelabs.
- 10% for thehomeworks.
- 35% for threeprojects.
- 12.5% forMidterm I(Monday, February 23, 5–6 pm, 155 Dwinelle Hall).
- 12.5% forMidterm II(Monday, April 13, 5–6 pm, 155 Dwinelle Hall).
- 25% for theFinal Exam(Wednesday, May 20, 5–8 pm, Wheeler Auditorium).
“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?”