Welcome to cse102-notes’s documentation!

Contents:

• Introduction
  • Example
• Algorithms
  • Problem
  • Computational Procedure
    • RAM Model
  • Runtime
    • “Efficient”
  • Asymptotic Notation
    • Big-O
    • Big-\(\Omega\)
    • Big-\(\Theta\)
    • Examples
• Recurrence
  • Solving
    • Recursion Tree
    • Induction/Substitution
    • Master Theorem
• Divide-and-Conquer Algorithms
  • Mergesort
    • Proving Mergesort
  • Designing
  • Integer Multiplication
    • Elementary Multiplication
    • Divide-and-Conquer
    • Gotta Go Fast
    • Gotta Go Faster
  • Closest Pair
    • D/C Algorithm
    • Runtime
• Data Structures
  • Priority Queues
    • Operations
    • Implementations
  • Amortized Runtimes
    • Automatically-expanding Arrays
    • Incrementing Binary Counter
  • Disjoint-Set Data Structures
• Graphs
  • Algorithms
    • S-T Connectivity Problem
    • BFS
    • DFS
  • Representing Graphs
  • More Problems
    • Cyclic Test
    • Topological Order
  • Minimum Spanning Tree
    • Kruskal’s Algorithm
    • Prim’s Algorithm
    • Proofs
      • Kruskal’s
      • Prim’s
      • Cut Property
  • Single-Source Shortest Paths
    • Dijkstra’s Algorithm
      • Proof
    • Related Problems
      • Shortest-Paths in a DAG
      • Shortest-Paths With Negative Weights
      • All-Pairs Shortest-Paths
• Greedy Algorithms
  • Interval Scheduling Problem
  • Optimality
    • Exchange Argument
    • Inductive Argument
    • ISP
    • Scheduling to Minimize Lateness
    • Huffman Coding
• Dynamic Programming
  • Weighted Interval Solving Problem
  • Design
  • Edit Distance
    • Problem
    • Solution
    • Runtime
  • Bellman-Ford Algorithm
    • Idea
    • Solution
    • Runtime
• Network Flow
  • Flow Networks
  • S-T Flow
  • Maximum-Flow Problem
  • Ford-Fulkerson Method
    • Termination and Runtime
    • Optimality
      • Lemma
      • Theorem
    • Runtime Revisited
  • Applications
    • Bipartite Matching
    • Image Segmentation
      • Solving
• Beyond 102
  • Interactable Problems and Optimal Runtimes

Transcripts

Click to download.

Week 1

1/4/2021: Introduction

1/6/2021: Algorithms/RAM Model

1/8/2021: Asymptotic Notation

Week 2

1/11/2021: Examples and Recurrence

1/13/2021: Induction and Master Theorem

1/15/2021: Divide/Conquer and Mergesort

Week 3

1/20/2021: D/C Integer Multiplication

1/22/2021: D/C Closest Points

Week 4

1/25/2021: Priority Queues

1/27/2021: Amortized Runtimes (no transcript available)

1/29/2021: Graphs (no transcript available)

Week 5

2/1/2021: BFS/DFS (no transcript available)

2/3/2021: Cyclic Test/Topological Sort (no transcript available)

2/5/2021: Minimum Spanning Trees (no transcript available)

Week 6

2/8/2021: Proving Kruskal’s and Prim’s (no transcript available)

2/10/2021: Midterm

2/12/2021: Proving Cut Property, SSSP (no transcript available)

Week 7

2/17/2021: Dijkstra’s Algorithm (no transcript available)

2/19/2021: Greedy Algorithms (no transcript available)

Week 8

2/22/2021: Minimal Lateness/Huffman Coding (no transcript available)

2/24/2021: Dynamic Programming (no transcript available)

2/26/2021: Edit Distance (no transcript available)

Week 9

3/1/2021: Bellman-Ford Algorithm (no transcript available)

3/3/2021: Network Flow (no transcript available)

3/5/2021: Ford-Fulkerson Algorithm (no transcript available)

Week 10

3/8/2021: Applications of FF: Bipartite Matching

3/10/2021: Image Segmentation

Indices and tables

• Index

• Module Index

• Search Page