Projects

1
Arrays Linked Lists and Recursion
3 4 Circularly Linked Lists and List Reversal 129
3 4 1 Circularly Linked Lists 129 
3 4 2 Reversing a Linked List 133

2
List and Iterator ADTs
6 4 Case Study: Bubble-Sort on a Sequence 259
6 4 1 The Bubble-Sort Algorithm 259
6 4 2 A Sequence-Based Analysis of Bubble-Sort 260

3+
Heaps and Priority Queues
8 3 Heap
8 3 6 Bottom-Up Heap Construction⋆ 353

4+
Heaps and Priority Queues
8 4 Adaptable Priority Queues 357
8 4 1 A List-Based Implementation 358
8 4 2 Location-Aware Entries 360

5
Hash Tables Maps and Skip Lists
9 1 Maps 368
9 1 1 The Map ADT 369
9 1 2 A C++ Map Interface 371

6+
Hash Tables Maps and Skip Lists
9 1 3 The STL map Class 372
9 1 4 A Simple List-Based Map Implementation 374

7+
Hash Tables Maps and Skip Lists
9 4 Skip Lists 402
9 4 1 Search and Update Operations in a Skip List 404

8+
Sorting Sets and Selection
11 1 Merge-Sort 500
11 1 1 Divide-and-Conquer 500

9
Sorting Sets and Selection
11 1 2 Merging Arrays and Lists 505
11 1 3 The Running Time of Merge-Sort 508
11 1 4 C++ Implementations of Merge-Sort 509

10
Sorting Sets and Selection
11 2 Quick-Sort 513

11
Sorting Sets and Selection
11 2 1 Randomized Quick-Sort 521
11 2 2 C++ Implementations and Optimizations 523

12+
Sorting Sets and Selection
11 3 Studying Sorting through an Algorithmic Lens 526
11 3 1 A Lower Bound for Sorting 526
11 3 2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 528
Bucket-Sort

13
Sorting Sets and Selection
11 3 Studying Sorting through an Algorithmic Lens
11 3 2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 528
Radix-Sort
11 3 3 Comparing Sorting Algorithms 531

14
Sorting Sets and Selection
11 4 Sets and Union/Find Structures 533
11 4 1 The Set ADT 533
11 4 2 Mergable Sets and the Template Method Pattern 534

15+
Sorting Sets and Selection
11 4 Sets and Union/Find Structures
11 4 3 Partitions with Union-Find Operations 538

16
Sorting Sets and Selection
11 5 Selection 542
11 5 1 Prune-and-Search 542
11 5 2 Randomized Quick-Select 543
11 5 3 Analyzing Randomized Quick-Select 544

17+
Strings and Dynamic Programming
12 1 1 The STL String Class 555

18+
Strings and Dynamic Programming
12 2 Dynamic Programming 557
12 2 1 Matrix Chain-Product 557

19+
Strings and Dynamic Programming
12 2 Dynamic Programming
12 2 2 DNA and Text Sequence Alignment 560

20+
Strings and Dynamic Programming
12 3 Pattern Matching Algorithms 564
12 3 1 Brute Force 564
12 3 2 The Boyer-Moore Algorithm 566

21+
Strings and Dynamic Programming
12 3 Pattern Matching Algorithm
12 3 3 The Knuth-Morris-Pratt Algorithm 570

22+
Strings and Dynamic Programming
12 4 Text Compression and the Greedy Method 575
12 4 1 The Huffman-Coding Algorithm 576
12 4 2 The Greedy Method 577

23
Strings and Dynamic Programming
12 5 Tries 578
12 5 1 Standard Tries 578

24
Strings and Dynamic Programming
12 5 Tries
12 5 2 Compressed Tries 582

25+
Strings and Dynamic Programming
12 5 Tries
12 5 3 Suffix Tries 584
12 5 4 Search Engines 586

26
Memory Management and B-Trees 665
14 1 Memory Management 666
14 1 1 Memory Allocation in C++ 669
14 1 2 Garbage Collection 671

27
Memory Management and B-Trees
14 2 External Memory and Caching 673
14 2 1 The Memory Hierarchy 673
14 2 2 Caching Strategies 674

28+
Memory Management and B-Trees
14 3 External Searching and B-Trees 679
14 3 1 (a,b) Trees 680
14 3 2 B-Trees 682

29
Memory Management and B-Trees
14 4 External-Memory Sorting 683
14 4 1 Multi-Way Merging 684

---