Computer Science 61B — Data Structures (4 Units)

Course Overview

Summary

The purpose of CS61B is to teach you basic algorithms, data structures, and fundamentals of software engineering. Additionally, some of the class is focused on learning Java (object oriented design, inheritance, etc).

Prerequisites

  • CS61A, CS88, or E7

Topics Covered

  • Java
    • Object-Oriented Programming
    • Interfaces
    • Iterators
    • Testing
    • Higher Order Functions
    • Abstract Classes
    • Exception Handling
    • Packages
    • Abstract Data Types, Java Libraries
  • Data Structures
    • Arrays
    • Linked Lists (singly-linked, doubly-linked, circular)
    • Trees (binary search, 2-3-4, splay)
    • Hash Tables (including implementations with linear probing/chaining)
    • Stacks/Queues (Priority Queues)
    • Heaps
    • Graphs
    • Sets (disjoint sets)
    • Tries
  • Algorithms
    • Search (Depth First, Breadth First)
    • Sorting (bubble, radix, bucket, merge, quick, selection, insertion)
    • Dijkstra's, A*
    • Prim's/Kruskal's
    • Dynamic Programming
    • Compression
    • NP Completeness, Reductions
    • Big O/Theta/Omega running time
    • Asymptotic, amortized, and randomized analysis of algorithms
  • Fundamentals of software engineering

Workload

Course Work

  • Coding assignment most weeks
  • Lab exercises every week
  • Three or four projects (both individual and group projects)
  • Two midterms
  • One final

Time Commitment

There are 3 hours of lecture and 3 hours of discussion/lab per week. In the lab based version of this class (CS61BL), typically offered during the summer, more time will be spent in the lab in exchange for less time in lecture (in the past this has been 12 hours of lab and 2 hours of lecture per week).

Outside of class, expect to spend around 5 hours per week on this course, with more time when projects are assigned. The majority of the time spent on this class is on the projects.

Moreover, it is well known that the workload of this class can vary by professor: - Hilfinger: projects and homeworks are very time consuming, potentially 1000+ lines of code - Shewchuk: Projects are of varying scale (some are shorter and directed, whereas others are longer and more open-ended) - Hug: Projects remain Hilfinger-level; Midterms are worth more.

Choosing the Course

When to take

This is a very important class to take early because most research and job opportunities in computer science will require knowledge of data structures and algorithms.

What's next?

The next class to take in the lower division sequence is CS61C. However, after taking CS61B it is also possible to take CS170 and CS188 (provided you have already taken CS70).

Usefulness for Research or Internships

This class is essential for research or internship opportunities in computer science. Most coding interview questions stem from material learned in CS61B.

Additional Comments/Tips

If you have already taken high school Java (AP Computer Science AB or equivalent), you may be able to opt out of CS61B. Depending on what you have previously taken when opting out, you may have to take CS47B as a supplement course. However, this class in Berkeley is likely to cover more advanced topics that you may not have covered in high school, and missing these may be a bad decision that will hinder future endeavors. CS61B will also more likely go more in-depth with the material, which will help your understanding of the material.

The course starts out laid back as the first few weeks are teaching the semantics of Java. However, after learning Java, the class becomes noticeably more difficult on a conceptual level. Make sure you do not get behind in the material. As noted before, projects take the majority of time in this class. On some of the largest projects, be ready to spend around 50 hours over the course of weeks. Because of the large time commitment of projects, make sure you start early and manage time well. Midterm exams and final exams for this class are also challenging so make sure you prepare well by going over past exams.

Last edited: Summer 2020