Version: 0.5.24 Algorithms and Data Structures# About This Course Welcome! What Can You Expect from Me? What Do I Expect from You? Course Overview Syllabus Why to Study This? Learning Outcomes Competence Skills Knowledge Practicalities Lectures Lab Sessions Examination Additional Resources Textbooks Online Courses Programming Platforms Modules Foundations Contents 1. Computations 1.1. Computation 1.2. Algorithms 1.3. Data Structures 1.4. How to Describe an Algorithm? 1.5. Conclusions 2. Computer 2.1. Random Access Machines 2.2. Programming Languages 2.3. Conclusion 3. Correctness 3.1. Functional Correctness? 3.2. Formal Proofs 3.3. Testing 3.4. Conclusion 4. Efficiency 4.1. Running Example 4.2. Benchmarking Performance 4.3. Computational Complexity 4.4. Conclusion 5. Algorithm Analysis 5.1. Modeling Algorithm Efficiency 5.2. Best, Worst, and Average Cases 5.3. Conclusions 6. The Big-O Notation 6.1. Comparing Efficiencies 6.2. Asymptotic Analysis 6.3. Orders of Growth 6.4. Conclusions Sequences Contents 1. Abstract Data Types 1.1. Data Types 1.2. Abstract Data Types 1.3. Conclusion 2. Using Arrays 2.1. An ADT for Sequences 2.2. Array-based Sequences in C 3. Using Dynamic Arrays 3.1. Infinite Sequences 3.2. Runtime Analysis 3.3. Amortized Analysis 3.4. Summary 4. Searching 4.1. Jump Search 4.2. Binary Search 4.3. Interpolation Search 5. Simple Sorting 5.1. What Is Sorting? 5.2. Selection Sort 5.3. Insertion Sort 5.4. Bubble Sort 6. Stacks, Queues, and Deques 6.1. Stacks 6.2. Queues 6.3. Deques Recursion Contents 1. Procedure Calls 1.1. Why Procedure Calls? 1.2. How Does “Calling” Work? 1.3. The Call Stack 1.4. How Much Does “Calling” Cost? 2. Recursion 2.1. What is Recursion? 2.2. Recursive Data Types 2.3. Recursive Algorithms 3. Linked Lists 3.1. Linked Lists 3.2. Other Flavors of List 3.3. Iterators 3.4. Linked Lists vs. Dynamic Arrays 4. Quick Sort 4.1. Quick Sort 4.2. Efficiency 5. Merge Sort 5.1. Merge Sort 5.2. Efficiency 6. Sorting Without Comparing 6.1. The Limit of Sorting by Comparing 6.2. Counting Sort 6.3. Radix Sort 6.4. Sorting Algorithms, Overview Hashing Contents 1. What Is Hashing? 1.1. The Map ADT 1.2. What Is a “Good” Key? 1.3. Hash Tables 1.4. Hash Functions 1.5. Usages of Hashing 2. Collisions 2.1. What Are “Collisions”? 2.2. Separate Chaining 2.3. Open Addressing Trees Contents 1. Trees 1.1. What Is a Tree? 1.2. Tree Implementations 1.3. Tree Traversals 2. Binary Search Trees 2.1. Ordered Sets 2.2. Ordered Set Using a Binary Search Tree 3. Binary Heaps 3.1. The Priority Queue ADT 3.2. What Is a Binary Heap? 3.3. Binary Heap Using an Array 3.4. Heapification 3.5. Heap Sort 4. AVL Trees 4.1. Why BST Can Be Inefficient? 4.2. AVL Trees 5. B-Trees 5.1. External Storages 5.2. The Disk-access Model (DAM) 5.3. B-Trees 6. Prefix and Suffix Trees 6.1. Prefix Trees 6.2. Suffix Trees Graphs Contents 1. Graph Theory 1.1. Graphs in Real-life 1.2. Graphs Species 1.3. The Graph Jargon 1.4. Alternative Representations 1.5. Graph Problems 1.6. Graphs as Data Structures 2. Reachability & Shortest Paths 2.1. Part I: Paths and Reachability 2.2. Part II: Weighted Paths and Edge Cases 2.3. Part III: Shortest Path Algorithms 2.4. Comparison of Shortest Path Algorithms 2.5. Summary 2.6. Further Reading 2.7. What’s Next? 3. Minimum Spanning Trees 3.1. What is a Spanning Tree? 3.2. The Minimum Spanning Tree Problem 3.3. Algorithm 1: Prim’s Algorithm 3.4. Algorithm 2: Kruskal’s Algorithm 3.5. Comparing Prim’s and Kruskal’s Algorithms 3.6. Applications of Minimum Spanning Trees 3.7. Summary 3.8. Further Reading 3.9. What’s Next? Optimization Contents 1. Exhaustive Search 2. Heuristic Search 3. Dynamic Programming Computational Complexity Contents 1. String Matching 2. Regular Expressions 3. Complexity Classes Beyond RAM Contents 1. Parallel Computing 2. Quantum Computing 3. How to Design Algorithms? Lab Sessions Setup Foundations Java Refresher Random Access Machines Correctness Cost Models Efficiency Sequences Sequences Using Arrays in Java Finding Extrema Finding Duplicates Digital Counter Recursion Simple Recursions Linked Lists Using Iteration Using Recursion Benchmark Trees Binary Search Tree (BST) Minimum Binary Heap Graphs Mazes & Graphs Maze Escape Analysis Generating “Random” Mazes Using the CLI Optimization Recursion Memoization Dynamic Programming Benchmark Code Examples Edge List Pattern in Ruby Adjacency List in JavaScript Adjacency Matrix in C Recaps Math Recap Logic Sets Sequences & Tuples Functions Probabilities Calculus Exponents Logarithms Summations Products Factorial Combinatorics Permutations Combinations Indices and Tables# Index Module Index Search Page
