CS 47B. Data Structures
Catalog Description: (1 unit, self-paced, graded) Iterators. Hashing, applied to strings and multi-dimensional structures. Heaps. Storage management. Design and implementation of a program containing hundreds of lines of code. Students with sufficient partial credit in CS 61B may, with the consent of the instructor, complete the credit in this course.
Prerequisites: A course in data structures, plus CS 9B or equivalent, in addition to consent of the instructor. Students will not receive credit for CS 61B taken after CS 47B, or for CS 47B taken after CS 61B.
Course objectives: Students who take CS 47B are expected to have had a course that familiarized them with the following: Arrays and linked structures, in particular with the efficiency tradeoffs between them; a variety of sorting algorithms for arrays and linked lists, including some 0(n log n) sorts; binary search trees; and stacks and queues.
Topics Covered: Course activities include programming assignments and quizzes; quizzes focus on low-level language details or programming techniques, while programming assignments are broader in scope. One of the programs is a substantial project comprising several hundred lines of code. The list of programming assignments appears below. All assignments use the Java programming language.
- Iterator exercises: Students write a breadth-first and a depth-first iterator for a general tree.
- Hashing exercises: Students analyze and devise hash functions applied to particular sets of data.
- Blocks project: This project involves solving a sliding-block puzzle. Input data are an initial configuration and a goal configuration; the solution program must find a sequence of block moves that lead from the initial configuration to the goal. The project has a number of interesting features: it's an example of backtracking search in which a hash table is used to avoid cycling; not only execution time, but also memory use must be accounted for in data structure and algorithm design.
- Heap exercises: Students work with code to manage a binary heap.
- Storage management exercises: Students modify a simulated storage manager, changing its first-fit strategy to best-fit and evaluating the result.