CS61B Data Structures

@ UCB, Spring 2018
@ Instructor: Josh Hug
@ Course Website
@ Java Visualizer

Overview

The CS 61 series is an introduction to computer science, with particular emphasis on software and machines from a programmer's point of view. CS 61A covered high-level approaches to problem-solving, providing you with a variety of ways to organize solutions to programming problems as compositions of functions, collections of objects, or sets of rules. In CS 61B, we move to a somewhat more detailed (and to some extent, more basic) level of programming.

In 61A, the correctness of a program was our primary goal. In CS61B, we're concerned also with engineering. An engineer, it is said, is someone who can do for a dime what any fool can do for a dollar. Much of 61B will be concerned with the tradeoffs in time and memory for a variety of methods for structuring data. We'll also be concerned with the engineering knowledge and skills needed to build and maintain moderately large programs.

HW and Labs

There are 14 weeks of lab in the course, as well as 5 required homeworks. In addition there is 1 makeup lab as well as 2 makeup homeworks that you can optionally complete at any time before the final exam to replace a lower score.

During Phase I of the course (Weeks 1 through 4), labs will provide you with help getting your computer set up and how to use essential Java programming tools. During Phase II of the course (Weeks 5 through 7), labs will provide you with structure for the open ended design project (project 2). In Phase III of the course, labs will give you a chance to implement important data structures and algorithms. All labs will take approximately two hours to complete, though some may run slightly longer. HWs will vary from 3 to 10 hours of work. You will turn in everything electronically using GitHub, and your results will be available on Gradescope. All homeworks and labs are individual efforts (without partners). Two of the homeworks and one of the labs will be released during RRR week. If you complete all of your work during the semester, you don't need to do these (as they will be dropped). For the three labs with no official work to turn in (labs 6, 7, and 12, subject to change), everybody gets full credit automatically, even if they do not attend lab that week.

No extensions or grace hours will be granted for labs or homework. Only your 12 (of 15) best lab scores and 5 (of 7) best homework scores count towards your final score.

Homework will be graded on a rigorous suite of correctness tests while labs will receive full credit for "reasonable effort,” as evaluated by a small number of relatively simple correctness tests. Passing all tests on Gradescope for homework or labs will ensure full credit as there are no hidden tests. Each lab will be worth 8 points (for a total of 96 points), and each homework will be worth 32 points (for a total of 160 points).

Programming Projects

In addition to the HWs and labs, there will be 4 programming projects. In these projects you will build an entire system. For project 0, you will be able to work with a partner. For project 2 you will be required to work with a partner, unless you specifically request otherwise (details TBA).

Project 0 and 1 will be relatively easier than projects 2 and 3, taking less time and with greater levels of scaffolding. Project 2 will be a very difficult project (on par with what you might expect from Hilfinger's harder projects). Project 3 will be challenging, but not as time consuming as project 2.

Each project has a specific theme:

• Project 0: Introduction to Java
• Project 1: Basic Design, Testing, and Code Review
• Project 2: Large Scale Design and Testing
• Project 3: Working with an Existing Code Base

For all projects, we will ultimately release all tests that determine your grade. In other words, passing all tests on Gradescope will allow you to earn full points for the autograded portion of the project.
Projects 0, 1, 2, and 3 will be worth 50, 80, 200, and 150 points respectively. For projects 2 and 3, there are opportunities for "gold points" described in each project specification.

References

• Gitbook CS 61B - Josh Hug
• Head First Java - 2nd edition (pdf)
• A Java Reference - Assorted JAva Reference Material (pdf)
• Open Data Structures (in Java)
• GeeksforGeeks - Data Structures
• Data Structures Into Java

All the references have been archived and can be found here.