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 2004Mondays, Wednesdays, and Fridays, 5:00-6:00 pm1 Pimentel Hall |
|---|
The final exam takes place Thursday, May 20, from 5-8 pm in the Wheeler Hall Auditorium. Students in the Disabled Students' Program take the exam at 5 pm in 508 Soda Hall.
Some practice problems for the final exam are available astext orPostScript.
Please congratulate Graham Melcher, Bryce Lee, and Leonard Wei--theKiller Coding Ninja Monkeys--for smashing all opposition and winning the Network tournament!
Here's some information ontiming Java programs with fine precision.
Textbooks
- David Arnow,Scott Dexter, andGerald Weiss(No, not THAT Gerald Weiss), Introduction to Programming Using Java: An Object-Oriented Approach, Second Edition, Addison-Wesley, 2004. ISBN # 0-321-20006-3.
- Michael T. Goodrich andRoberto Tamassia, Data Structures and Algorithms in Java, Third Edition, John Wiley & Sons, 2004. ISBN # 0-471-46983-1.
- For information on using older editions, read thecourse overview.
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 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 21 | Course overview |
Arnow Dexter Weiss, Chapter 1 | . |
| 2: January 23 | Using objects  |
ADW, Chapters 2 & 3 | . |
| 3: January 26 | Defining classes  |
ADW, Chapters 4 & 5 | . |
| 4: January 28 | Types; conditionals  |
ADW, Chapter 6 | Lab 1 |
| 5: January 30 | Iteration & arrays I |
ADW, Sections 9.1-9.5, 9.12-9.14 | Homework 1 |
| 6: February 2 | Iteration & arrays II |
ADW, Chapter 10 | . |
| 7: February 4 | Linked lists I |
. | Lab 2 |
| 8: February 6 | Linked lists II |
. | Homework 2 |
| 9: February 9 | Activation records |
ADW, Chapter 14 | . |
| 10: February 11 | Testing |
ADW, Chapter 8 | Lab 3 |
| 11: February 13 | Inheritance |
ADW, Sections 12.1-12.6 | Homework 3 |
| February 16 | President's Day | . | . |
| 12: February 18 | Abstract classes |
ADW, Chapter 12 | Lab 4 |
| 13: February 20 | Java packages |
. | Project 1 |
| 14: February 23 | MIDTERM I | covers Lectures 1-12 | . |
| 15: February 25 | Exceptions |
ADW, Chapter 13 | Lab 5 |
| 16: February 27 | More Java |
. | . |
| February 29 | due 5 pm | . | Homework 4 |
| 17: March 1 | Game Trees |
. | . |
| 18: March 3 | Encapsulation |
. | Lab 6 |
| 19: March 5 | Encapsulated lists |
. | Homework 5 |
| 20: March 8 | Asymptotic analysis |
Goodrich & Tamassia, Chapter 3 | . |
| 21: March 10 | Algorithm analysis |
G & T, Chapter 3 | Lab 7 |
| 22: March 12 | Hash tables |
G & T, Sections 8.1-8.3 | . |
| 23: March 15 | Stacks and queues |
G & T, Chapter 4 | . |
| 24: March 17 | Trees and traversals |
G & T, Chapter 6 | Lab 8 |
| 25: March 19 | Priority queues |
G & T, Sections 7.1-7.3 | Homework 6 |
| March 22-26 | Spring Recess | . | . |
| 26: March 29 | Binary search trees |
G & T, Section 9.1 | . |
| 27: March 31 | Balanced search trees |
G & T, Section 9.4 | Lab 9 |
| 28: April 2 | Graphs |
G & T, Sections 12.1-12.3 | Project 2 |
| 29: April 5 | Weighted graphs |
G & T, Sections 12.5, 12.7-12.7.1 | . |
| 30: April 7 | Sorting I |
G & T, Sections 7.2.3, 7.3.5, & 10.1 | Lab 10 |
| 31: April 9 | Sorting II |
G & T, Section 10.2 | Homework 7 |
| 32: April 12 | MIDTERM II | covers Lectures 1-29 | . |
| 33: April 14 | Disjoint Sets |
G & T, Section 10.6 | Lab 11 |
| 34: April 16 | Sorting III (video) | . | . |
| April 18 | due 5 pm | . | Homework 8 |
| 35: April 19 | Sorting IV |
G & T, Section 10.3 & 10.7 | . |
| 36: April 21 | Sorting V |
G & T, Section 10.4 | Lab 12 |
| April 23 | Lecture cancelled | . | Homework 9 |
| 37: April 26 | Splay trees |
G & T, Section 9.3 | . |
| 38: April 28 | Amortized analysis |
. | Lab 13 |
| 39: April 30 | Randomized analysis |
. | Project 3 |
| 40: May 3 | Expression parsing |
. | . |
| 41: May 5 | Garbage collection |
. | Lab 14 |
| 42: May 7 | Augmenting data structures |
. | Homework 10 |
| 43: May 10 | Review |
. | . |
The FINAL EXAMtakes place on Thursday, May 20, from 5 to 8 pm in Wheeler Hall Auditorium. (CS 61B is in Exam Group 17.)
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 23, 5-6 pm, in class).
- 12.5% forMidterm II(Monday, April 12, 5-6 pm, in class).
- 25% for the Final Exam (Thursday, May 20, 5-8 pm, Wheeler Hall Auditorium).
Mail inquiries tocs61b@cory.eecs