Version: 0.6.7 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 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 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 RAM Assembly Recap Machine Code vs. Assembly Code Instruction Set Anatomy of a Program Cheat Sheet: Pseudo Code → Assembly Assignment Sequence Conditional Loop Worked Example Macros Try It Yourself Indices and Tables# Index Module Index Search Page
