Version: 0.3.38

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
    • 2. Binary Search Tree
    • 3. Binary Heaps
    • 4. Self-Balancing Trees
    • 5. B-Trees
    • 6. Prefix and 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
      • 1.7. Appendix
    • 2. Reachability & Shortest Paths
    • 3. Minimum Spanning Trees
• 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
  • Dynamic 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

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