Optional Readings

Introduction

• Lafore: chapter 1

Recursion and Backtracking

• Lafore: chapter 6

Sorting and Algorithm Analysis

• Lafore: chapter 2 (only the sections on logarithms and big-O notation); chapter 3; chapter 7
• Lafore presents an approach to quicksort that differs slightly from the version presented in lecture. The version in the lecture notes is based on one used by Cormen et al. in their book, Introduction to Algorithms (MIT Press).

Linked Lists

• Lafore: chapter 5, pages 179-197

Lists, Stacks, and Queues

• Lafore: chapter 4, pages 115-142; chapter 5, pages 202-211, plus the reading from the prior topic
• The Java Tutorial has material on interfaces, including a definition page and a section on creating and using interfaces.
• The Java Tutorial provides overviews of nested classes, inner classes, and generics.

Binary Trees and Huffman Encoding; Binary Search Trees

• Lafore: chapter 8, pages 365-421

Balanced Search Trees

• Lafore: chapter 10, pages 492-506

Heaps and Priority Queues

• Lafore: chapter 12

Hash Tables

• Lafore: chapter 11, pages 519-571

Graphs

• Lafore: chapter 13, pages 615-660; chapter 14, pages 669-707, 710-713 (note: the MST algorithm that Lafore presents is Prim’s algorithm)
• A good overview of minimum spanning trees is available here.