CS 234: Data Types and Structures

Lectures

This page contains the order of topics contained in lectures, listed as a sequence of modules. Please note that modules may vary considerably in length and difficulty; please see the schedule for details on timing.

For each module are listings of related readings in the textbook. Please see the resources page for additional relevant material.

Module 1: Introduction

Topics: Introduction, multiple viewpoints, basic definitions, course goals.

Textbook readings: 1.1 Introduction

Module 2: ADTs, pseudocode, and algorithm analysis

Topics: Recipes for choosing and designing ADTs, types of ADTs and data, pseudocode, different types of analysis, asymptotic notation.

Textbook readings: 4.1 Complexity Analysis

Module 3: Data structures, ADTs with no order of any kind, Python review

Topics: Memory, arrays and linked lists, ADT Multiset, Python review, ADT Set, special case of orderable data, sorting.

Textbook readings: 2.1 The Array Structure, 1.3 Bags, 6.1 Introduction (Linked Structures), 6.2 The Single Linked List, 2.2 The Python List, 6.4 More Ways to Build a Linked List, 6.3 The Bag ADT Revisited, 5.1 Searching, 5.2 Sorting, 5.3 Working with Sorted Lists, 12.1 Merge Sort, (Optional: 12.5 Sorting Linked Lists)

Module 4: ADTs with order imposed by operations

Topics: ADT Stack, ADT Queue, ADT List, ADT Ranking, ADT Superlist, ADT Grid.

Textbook readings: 7.1 The Stack ADT, 7.2 Implementing the Stack, (Optional 7.3 Stack Applications), (Optional 7.4 Application: Solving a Maze), 8.1 The Queue ADT, 8.2 Implementing the Queue, 9.1 The Doubly Linked List, 9.2 The Circular Linked List, 2.3 Two-Dimensional Arrays, 2.4 The Matrix Abstract Data Type, 3.3 Multi-Dimensional Arrays

Module 5: ADTs with items related by structure

Topics: Tree terminology, ADT Unordered Tree, ADT Binary Tree, ADT Ordered Tree.

Textbook readings: 13.1 The Tree Structure, 13.2 The Binary Tree, (Optional: 13.3 Expression Trees)

Module 6: ADT Dictionary

Topics: Binary search, tree implementations, external searching, B-trees.

Textbook readings: 3.2 Maps, 14.1 The Binary Search Tree, 14.3 AVL Trees, 14.4 The 2-3 Tree

Module 7: Digital data and average case analysis

Midterm Exam Tuesday, June 20, 4:30 PM – 6:20 PM

Topics: Decision tree lower bounds, hashing, digital sorting, interpolation search, Move to Front, Transpose.

Textbook readings: 12.3 How Fast Can We Sort?, 11.1 Introduction (Hash Tables), 11.4 Hash Functions, 11.2 Hashing, 11.3 Separate Chaining, (Optional: 11.5 The HashMap Abstract Data Type), 12.4 Radix Sort

Module 8: ADT Priority Queue

Topics: Array and linked implementations, heaps, heapsort.

Textbook readings: 8.3 Priority Queues, 13.4 Heaps, 13.5 Heapsort

Module 9: ADT Graph

Topics: Graph terminology, data structures, traversals.

Textbook readings: 6.5 The Sparse Matrix Revisited, 9.3 Multi-Linked Lists

Module 10: Wrap-up and advanced topics

Topics: Use of ADTs, ADTs for special situations.

Textbook readings: None