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