CS 61B: Data Structures (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 2005Mondays, Wednesdays, and Fridays, 3:00-4:00 pm4 Le Conte Hall (next to the Campanile) |
|---|
Final exam solutions are available(except Problem 2). So are Midterm I solutions andMidterm II solutions.
Please congratulate Steven Sam and Adam Singer of The Mighty Levinsfor trashing all opposition and attaining resounding victory in the**Network Tournament**!
The final exam takes place at 5 pm on Tuesday, May 17, in 220 Hearst Gymnasium. Students in the Disabled Students' Program who have request extra time should report to 508 Soda Hall at the same time. The review session for the final exam takes place from 4 pm to 7 pm on Sunday, May 15, in 10 Evans Hall.
Textbooks
- Kathy Sierra andBert Bates,Head First Java, O'Reilly, 2003. ISBN # 0-596-00465-6.
- 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 of Goodrich and Tamassia, read thecourse overview.
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.
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. Webcasts of past lectures are offered by Berkeley's Educational Technology Services through theirWebcast Berkeley page. Click on the icons
in the schedule below to view past lectures. 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 PostScript
or PDF
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 19 | Course overview |
Sierra & Bates, pp. 1-7, 16-17, 82 | . |
| 2: January 21 | Using objects  |
S & B, Chapter 2; pp. 52-56, 150-156, 589, 596 | . |
| 3: January 24 | Defining classes  |
S & B, pp. 69-72, 74, 83, 236-245, 269-277, 289-290 | . |
| 4: January 26 | Types; conditionals  |
S & B, pp. 8-12, 47-51, 73, 76-77, 84, 114, 282-284, 588 | Lab 1 |
| 5: January 28 | Iteration & arrays I |
S & B, pp. 57-60, 81, 112-113, 285-287, 597 | Homework 1 |
| 6: January 31 | Iteration & arrays II |
S & B, pp. 278-281 | . |
| 7: February 2 | Linked lists I |
. | Lab 2 |
| 8: February 4 | Linked lists II |
. | Homework 2 |
| 9: February 7 | Stack frames |
S & B, pp. 75, 231-235, 254-261, 591 | . |
| 10: February 9 | Testing |
S & B, pp. 93-107, 590, 593 | Lab 3 |
| 11: February 11 | Inheritance |
S & B, Chapter 7; pp. 26-31, 246-253 | Homework 3 |
| 12: February 14 | Abstract classes |
S & B, Chapter 8 | . |
| 13: February 16 | Java packages |
S & B, pp. 150-156, 515-519, 594-595 | Lab 4 |
| 14: February 18 | Exceptions |
S & B, pp. 297-320 | Project 1 |
| February 21 | President's Day | . | . |
| 15: February 23 | MIDTERM I | covers Lectures 1-12 | Lab 5 |
| 16: February 25 | More Java |
. | Homework 4 |
| 17: February 28 | Game Trees |
. | . |
| 18: March 2 | Encapsulation |
S & B, pp. 78-80 | Lab 6 |
| 19: March 4 | Encapsulated lists |
S & B, p. 592 | Homework 5 |
| 20: March 7 | Asymptotic analysis |
Goodrich & Tamassia, Chapter 3 | . |
| 21: March 9 | Algorithm analysis |
G & T, Chapter 3 | Lab 7 |
| 22: March 11 | Hash tables |
G & T, Sections 8.1-8.3 | . |
| 23: March 14 | Stacks and queues |
G & T, Chapter 4 | . |
| 24: March 16 | Trees and traversals |
G & T, Chapter 6 | Lab 8 |
| 25: March 18 | Priority queues |
G & T, Sections 7.1-7.3 | Homework 6 |
| March 21-25 | Spring Recess | ||
| 26: March 28 | Binary search trees |
G & T, Section 9.1 | . |
| 27: March 30 | Balanced search trees |
G & T, Section 9.4 | Lab 9 |
| 28: April 1 | Graphs |
G & T, Sections 12.1-12.3 | Project 2 |
| 29: April 4 | Weighted graphs |
G & T, Sections 12.5, 12.7-12.7.1 | . |
| 30: April 6 | Sorting I |
G & T, Sections 7.2.3, 7.3.5, & 10.1 | Lab 10 |
| 31: April 8 | Sorting II |
G & T, Section 10.2 | Homework 7 |
| 32: April 11 | MIDTERM II | covers Lectures 1-29 | . |
| 33: April 13 | Disjoint Sets |
G & T, Section 10.6 | Lab 11 |
| 34: April 15 | Sorting III |
G & T, Section 10.3 & 10.7 | Homework 8 |
| 35: April 18 | Sorting IV (video) | . | . |
| 36: April 20 | Sorting V |
G & T, Section 10.4 | Lab 12 |
| 37: April 22 | Splay trees |
G & T, Section 9.3 | Homework 9 |
| 38: April 25 | Amortized analysis |
. | . |
| 39: April 27 | Randomized analysis |
. | Lab 13 |
| 40: April 29 | Expression parsing |
. | Project 3 |
| 41: May 2 | Garbage collection |
. | . |
| 42: May 4 | Augmenting data structures |
. | Lab 14 |
| 43: May 6 | Review |
. | . |
| May 9 | . | . | Homework 10 |
The FINAL EXAMtakes place on Tuesday, May 17, from 5 to 8 pm in 220 Hearst Gymnasium. (CS 61B is in Exam Group 12.)
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
- 5% for thelabs.
- 10% for thehomeworks.
- 35% for threeprojects.
- 12.5% forMidterm I(Wednesday, February 23, 3-4 pm, 100 Lewis Hall).
- 12.5% forMidterm II(Monday, April 11, 3-4 pm, 100 Lewis Hall).
- 25% for theFinal Exam(Tuesday, May 17, 5-8 pm, 220 Hearst Gymnasium).
``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?''
