Course Title
CS 61B - Data Structures
Abbreviated Course Title
DATA STRS
Instructors in Charge
Mike Clancy Senior Lecturer
Paul Hilfinger, Professor
Catalog Data
4 units; 3 hours lecture, 1 hour discussion section, 2 hours
programming laboratory, average 6 additional hours self-scheduled
programming laboratory. Offered fall, spring, and summer terms.
Prerequisites
CS 61A.
Catalog Description
Fundamental dynamic data structures, including linear lists, queues,
trees, and other linked structures; arrays, strings, heaps, and hash tables.
Elementary principles of software engineering.
Abstract data types. Algorithms for sorting and searching.
Introduction to the Java programming language.
Expanded Description
In CS 61B, students are expected to gain facility with Java programming,
become familiar with
fundamental data structures and algorithms, and learn techniques for
constructing programs of moderate size using Java.
Roughly a third of the semester will be devoted to an introduction to Java.
Constructs and topics to be covered include the following:
- The compile/execute cycle.
- Primitive data types (integer, floating point, character,
boolean); arrays; classes.
- Interactive control structures.
- Functions; recursion; overloading.
- Inheritance; interfaces; exceptions; threads.
In the rest of the semester, and in conjunction with practice of basic
Java programming techniques, students will implement and experiment
with fundamental algorithms and data structures:
- Construction, modification, and traversal of linked list
structures of various forms -- singly-linked, doubly-linked, and
circular, with and without sentinels.
- Construction, modification, and traversal of binary trees (in
particular, binary search trees and expression trees).
- Sorting of sequences by selection, insertion, quicksort, merge
sort; binary search through a binary search tree of a sorted sequence.
- Binary heaps.
- Hashing.
- Elementary graph structures and algorithms.
The aim is for students to be able to recognize when these data
structures and algorithms are applicable to a problem, and to be able
to evaluate their relative advantages and disadvantages.
Design in terms of abstract data types and isolation of their
implementation in modules will be emphasized. We intend that, having
taken CS 61B, student will:
- understand the distinction between a specification or interface
and an implementation;
- understand pre- and post-conditions in specifications;
- be able to use a specificiation expressed as a set of procedure
headers with comments; and
- be able to provide suitable comments for modules, data types, and
functions.
Data types used for illustration will include queues, stacks,
dictionaries, sets, and GUI toolsets.
CS 61B is the first place in our curriculum that students design and
develop a program of significant size (around 1000 lines) from scratch.
Course assignments include at least one such program.
CS 61A is an important prerequisite
for 61B. We expect to build heavily on data-oriented and
object-oriented design approaches introduced in those courses, as well
as on algorithms for recursive list and tree manipulation.
June 2003
clancy@cs.berkeley.edu