CS 61B: Data Structures (original) (raw)
 |
(Cover illustration: Anatjari Tjampitjinpa, ``Snake Dreaming,'' 1988.) CS 61B Data Structures |
|---|
Review questions for the final exam are available (text, PostScript).
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-61272-0.
- Michael T. Goodrich andRoberto Tamassia, Data Structures and Algorithms in Java, John Wiley & Sons, 1998. ISBN # 0-471-19308-9.
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.
- CSUA help session schedules (Unix, Emacs, and more) and documentation.
- 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. See theSoftware pageof theBerkeley Internet Broadcasting System Web page for information on viewing lectures over the net, eitherliveor after the fact 
.
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. Do not be surprised if they say the same thing I said in class; I edit them after class to make sure of this. If I receive any more 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 that class.
| Topic | Reading | Due | |
|---|---|---|---|
| 1: January 19 | Course overview |
Arnow & Weiss, Chapter 1 | . |
| 2: January 21 | Using objects  |
A & W, Chapters 2 & 3 | Lab 1 |
| 3: January 24 | Defining classes  |
A & W, Chapter 4 | . |
| 4: January 26 | Types; conditionals  |
A & W, Chapters 5 & 6 | Homework 1 |
| 5: January 28 | Iteration & arrays I |
A & W, Sections 8.1-8.5, 10.8-10.12 | Lab 2 |
| 6: January 31 | Iteration & arrays II |
A & W, Chapter 9 | . |
| 7: February 2 | Linked lists I |
. | Homework 2 |
| 8: February 4 | Linked lists II |
. | Lab 3 |
| 9: February 7 | Activation records |
A & W, Chapter 11 | . |
| 10: February 9 | Testing |
A & W, Chapter 7 | Homework 3 |
| 11: February 11 | Inheritance |
A & W, Chapter 13 | Lab 4 |
| 12: February 14 | Abstract classes |
A & W, Chapter 13 | . |
| 13: February 16 | Java packages |
. | Project 1 |
| 14: February 18 | Exceptions |
A & W, Chapter 14 | Lab 5 |
| February 21 | President's Day | . | . |
| 15: February 23 | MIDTERM I | covers Lectures 1-12 | Homework 4 |
| 16: February 25 | More Java |
. | Lab 6 |
| 17: February 28 | Game Trees |
. | . |
| 18: March 1 | Encapsulation |
. | Homework 5 |
| 19: March 3 | Encapsulated lists |
. | Lab 7 |
| 20: March 6 | Asymptotic analysis |
Goodrich & Tamassia, Chapter 2 | . |
| 21: March 8 | Algorithm analysis |
G & T, Chapter 2 | . |
| 22: March 10 | Hash tables |
G & T, Sections 7.1, 7.2, & 7.6 | Lab 8 |
| 23: March 13 | Stacks and queues |
G & T, Chapter 3 | . |
| 24: March 15 | Trees and traversals |
G & T, Sections 5.1-5.4 | Homework 6 |
| 25: March 17 | Priority queues |
G & T, Sections 6.1-6.3 | Lab 9 |
| 26: March 20 | Binary search trees |
G & T, Section 7.3 | . |
| 27: March 22 | Balanced search trees |
G & T, Sections 13.1 & 13.2 | Project 2 |
| 28: March 24 | Graphs |
G & T, Sections 9.1-9.3 | Lab 10 |
| March 27-31 | Spring Recess | . | . |
| 29: April 3 | Weighted Graphs |
G & T, Sections 10.2-10.2.1 | . |
| 30: April 5 | Sorting I |
G & T, Sections 6.2.3, 6.3.3, & 8.1 | Homework 7 |
| 31: April 7 | Sorting II |
G & T, Section 8.3 | Lab 11 |
| 32: April 10 | MIDTERM II | covers Lectures 1-29 | . |
| 33: April 12 | Disjoint Sets |
G & T, Section 12.1 | Homework 8 |
| 34: April 14 | Sorting III |
G & T, Section 8.5 | Lab 12 |
| 35: April 17 | Sorting IV (video) |
G & T, Section 8.6 | . |
| 36: April 19 | Splay trees |
G & T, Section 13.4 (13.4.3 optional) | Homework 9 |
| 37: April 21 | C pointers |
. | Lab 13 |
| 38: April 24 | Memory management I |
. | . |
| 39: April 26 | Memory management II |
. | Project 3 |
| 40: April 28 | C++ classes I |
. | Lab 14 |
| 41: May 1 | C++ classes II |
. | . |
| 42: May 3 | C++ sucks |
. | Homework 10 |
| 43: May 5 | Review |
. | Lab 15 |
The FINAL EXAMtakes place on Tuesday, May 16, from 5 to 8 pm in the Wheeler Hall Auditorium. (CS 61B is in Exam Group 11.)
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 (Wednesday, February 23, 3-4 pm).
- 12.5% forMidterm II (Monday, April 10, 3-4 pm).
- 25% for the Final Exam (Tuesday, May 16, 5-8 pm, 100 Haas Pavilion).
Mail inquiries tocs61b@cory.eecs