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.2.7 A C++ Hash Table Implementation 387

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

9`
Sorting Sets and Selection
11 1 Merge-Sort 500
11 1 1 Divide-and-Conquer 500

10`
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

11`
Sorting Sets and Selection
11 2 Quick-Sort 513

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

13`
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

14`
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

15`
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

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

17`
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

18`
Strings and Dynamic Programming
12 1 1 The STL String Class 555

19`
Strings and Dynamic Programming
12 2 Dynamic Programming 557
12 2 1 Matrix Chain-Product 557

20
Strings and Dynamic Programming
12 2 Dynamic Programming
12 2 2 DNA and Text Sequence Alignment 560

21
Strings and Dynamic Programming
12 3 Pattern Matching Algorithms 564
12 3 1 Brute Force 564  + implementation in C++

22`
Strings and Dynamic Programming
12 3 Pattern Matching Algorithm
12 3 2 The Boyer-Moore Algorithm 566

23`
Strings and Dynamic Programming
12 3 Pattern Matching Algorithm
12 3 3 The Knuth-Morris-Pratt Algorithm 570

24`
Strings and Dynamic Programming
12 4 Text Compression and the Greedy Method 575
12 4 1 The Huffman-Coding Algorithm 576 + implementation in C++
12 4 2 The Greedy Method 577

25`
Strings and Dynamic Programming
12 5 Tries 578
12 5 1 Standard Tries 578

26`
Strings and Dynamic Programming
12 5 Tries
12 5 2 Compressed Tries 582

27`
Strings and Dynamic Programming
12 5 Tries
12 5 3 Suffix Tries 584
12 5 4 Search Engines 586

28
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

29
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

30
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

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

---