CS 61B: Data Structures (original) (raw)
 |
(Cover illustration: Anatjari Tjampitjinpa, ``Snake Dreaming,'' 1988.) 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 2002Beginning January 23Mondays, Wednesdays, and Fridays, 2:00-3:00 pm1 Pimental Hall |
|---|
**Check out Steven Jones'Maze Page**based on Homework 9!
Review questions for the final exam are available (text, PostScript).
Solutions to two of the final exams in the reader are now available via the Exams link. Give your classmate Michelle Kam a pat on the back for typing them in for you.
**Network tournament winners:**The winning team is **Champs Part II!**Please congratulate Minqiu Cao, Mike Tai, and Hector Angulo on their hard-won Network Title on May 8. Despite going to the sudden death round in their last three contests - twice even losing the first round of their two-out-of-three matches - the Champs proved their ability to come back from behind again and again, and prevail over all comers. Our stalwart heroes win gift certificates to Amoeba Recordsand your unstinting admiration.
Ian Joyner's critique of C++ is available asPostScriptor HTML.
Textbooks
- David Arnow andGerald Weiss, Introduction to Programming Using Java: An Object-Oriented Approach, Java 2 Update, Addison-Wesley, 2000. ISBN # 0-201-75159-3 or ISBN # 0-201-61272-0.
- Michael T. Goodrich andRoberto Tamassia, Data Structures and Algorithms in Java, Second Edition, John Wiley & Sons, 2001. ISBN # 0-471-38367-8. (The first edition can be used too, but all the sections are numbered differently.)
Information
- Course overview: prerequisites, laboratory and discussion sections, grading, cheating policies.
- Admission to the class.
- 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.
- 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.
- Information on using Java at home, and information on connecting from home.
- User's Guide to EECS Instructional Computing.
- Access the ucb.class.cs61b newsgroup.
Work
Lectures
The following schedule is tentative. There will definitely 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 of past lectures are offered by Berkeley's Educational Technology Services through theirWebcast Berkeley page, which offers both live CS 61B webcasts and past lectures. Click on this icon 
to view a live lecture (only works when a lecture is in progress), or on the same icons below to view past classes. You will need a Web browser with aRealPlayer plug-in.
Some lecture notes can be obtained by clicking on the lecture titles (for ASCII) or the PostScript 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: January 23 | Course overview | Arnow & Weiss, Chapter 1 | . |
| 2: January 25 | Using objects | A & W, Chapters 2 & 3 | Lab 1 |
| 3: January 28 | Defining classes | A & W, Chapter 4 | . |
| 4: January 30 | Types; conditionals | A & W, Chapters 5 & 6 | Homework 1 |
| 5: February 1 | Iteration & arrays I | A & W, Sections 8.1-8.5, 10.8-10.12 | Lab 2 |
| 6: February 4 | Iteration & arrays II | A & W, Chapter 9 | . |
| 7: February 6 | Linked lists I | . | Homework 2 |
| 8: February 8 | Linked lists II | . | Lab 3 |
| 9: February 11 | Activation records | A & W, Chapter 11 | . |
| 10: February 13 | Testing | A & W, Chapter 7 | Homework 3 |
| 11: February 15 | Inheritance | A & W, Chapter 13 | Lab 4 |
| February 18 | President's Day | . | . |
| 12: February 20 | Abstract classes | A & W, Chapter 13 | . |
| 13: February 22 | Java packages | . | Lab 5 |
| February 23 | . | (Project 1 due Saturday at 5 pm) | Project 1 |
| 14: February 25 | MIDTERM I | covers Lectures 1-12 | . |
| 15: February 27 | Exceptions | A & W, Chapter 14 | Homework 4 |
| 16: March 1 | More Java | . | Lab 6 |
| 17: March 4 | Game Trees | . | . |
| 18: March 6 | Encapsulation | . | Homework 5 |
| 19: March 8 | Encapsulated lists | . | Lab 7 |
| 20: March 11 | Asymptotic analysis | Goodrich & Tamassia, Chapter 3 | . |
| 21: March 13 | Algorithm analysis | G & T, Chapter 3 | . |
| 22: March 15 | Hash tables | G & T, Sections 8.1-8.3 | Lab 8 |
| 23: March 18 | Stacks and queues | G & T, Chapter 4 | . |
| 24: March 20 | Trees and traversals | G & T, Chapter 6 | Homework 6 |
| 25: March 22 | Priority queues | G & T, Sections 7.1-7.3 | Lab 9 |
| March 25-29 | Spring Recess | . | . |
| 26: April 1 | Binary search trees | G & T, Section 9.1 | . |
| 27: April 3 | Balanced search trees | G & T, Sections 9.3 & 9.4 | Project 2 |
| 28: April 5 | Graphs | G & T, Sections 12.1-12.3 | Lab 10 |
| 29: April 8 | Weighted graphs | G & T, Sections 12.5, 12.7-12.7.1 | . |
| 30: April 10 | Sorting I | G & T, Sections 7.2.3, 7.3.4, & 10.1 | Homework 7 |
| 31: April 12 | Sorting II | G & T, Section 10.3 | Lab 11 |
| 32: April 15 | MIDTERM II | covers Lectures 1-29 | . |
| 33: April 17 | Disjoint Sets | Handout (outside 625 Soda) | Homework 8 |
| 34: April 19 | Sorting III (video) | . | Lab 12 |
| 35: April 22 | Sorting IV | G & T, Section 10.4 & 10.7 | . |
| 36: April 24 | Sorting V | G & T, Section 10.5 | Homework 9 |
| 37: April 26 | Expression parsing | . | Lab 13 |
| 38: April 29 | Splay trees | Handout | . |
| 39: May 1 | Amortized Analysis | . | . |
| 40: May 3 | Randomized Analysis | . | Lab 14 |
| May 4 | . | (Project 3 due Saturday at 2 pm) | Project 3 |
| 41: May 6 | C pointers | . | . |
| 42: May 8 | Garbage collection | . | Homework 10 |
| 43: May 10 | Review |
. | Lab 15 |
The FINAL EXAMtakes place on Friday, May 24, from 5 to 8 pm in Wheeler Auditorium. (CS 61B is in Exam Group 20.)
Course Description
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: A grade of B- or better in CS 61A or Engineering 77N. (The B- requirement is rarely enforced.)
Grading
- 5% for thelabs.
- 10% for thehomeworks.
- 35% for threeprojects.
- 12.5% forMidterm I(Monday, February 25, 2-3 pm, in class).
- 12.5% forMidterm II(Monday, April 15, 2-3 pm, in class).
- 25% for the Final Exam (Friday, May 24, 5-8 pm).
Mail inquiries tocs61b@cory.eecs