Syllabus
FAQ, etc.   Office Hours
Calendar   Campuswire
Message Board   Gradescope
Gradebook
  Course Notes
  All Resources

This Week

Minimum Spanning Trees

Midterm 02 on Thursday, Mar 04

Lecture 17 — Asymptotic Time Complexity, pt. II

  • Recommended Reading: Section 1.5 in Course Notes
  • Prof. Wang
  • slides not yet posted...
  • Zoom lecture 11:00 AM PST on Thursday, Mar 4
  • Prof. Eldridge
  • slides not yet posted...

Lecture 16 — Minimum Spanning Trees and Prim's Algorithm

  1. Minimum Spanning Trees
  2. Prim's Algorithm
  3. Analysis of Time Complexity
  4. (Optional) Proof of Correctness

Midterm 02 Sample Questions

past weeks

Week 8

Weighted Shortest Paths

Lecture 15 — Dijkstra's Algorithm

  1. Dijkstra's Algorithm
  2. Analysis

Lecture 14 — Bellman-Ford

  1. Shortest Paths in Weighted Graphs
  2. The Bellman-Ford Algorithm
  3. Early Stopping and Negative Cycles

Homework 8

Was due Wednesday, Mar 03 at 23:59 PM

Discussion 8

Week 7

Depth-First Search

Lecture 13 — Depth-First Search

  1. Depth-First Search
  2. Nesting Properties of DFS
  3. Topological Sort

Lecture 12 — BFS for Shortest Paths

  1. Shortest Paths
  2. Finding Shortest Paths with BFS
  3. BFS Search Trees

Homework 7

Was due Wednesday, Feb 24 at 23:59 PM

Discussion 7

Week 6

Graphs and Breadth-First Search

Lecture 11 — Breadth First Search

  1. Breadth-First Search
  2. Time Complexity of BFS

Lecture 10 — Graph Theory

  1. Graph Theory
  2. Paths
  3. Connected Components
  4. Adjacency Matrices
  5. Adjacency Lists
  6. Dictionary of Sets

Homework 6

Was due Wednesday, Feb 17 at 23:59 PM

Discussion 6

Week 5

Hashing

Midterm 01 on Thursday, Feb 04

Lecture 9 — Hashing

  1. Hashing and Hash Functions
  2. Hash Tables
  3. Faster Algorithms with Hashing

Homework 5

Was due Wednesday, Feb 10 at 23:59 PM

Week 4

Faster Selection and Queries

Lecture 8 — Binary Search Trees

  1. Dynamic Sets, Many Queries
  2. Binary Search Trees
  3. Querying and Insertion in BSTs
  4. Balanced and Unbalanced BSTs
  5. Augmenting BSTs

Lecture 7 — Quickselect

  1. Order Statistics
  2. Quickselect
  3. Partition
  4. Analysis of Quickselect
  5. Quicksort

Homework 4

Was due Tuesday, Feb 02 at 23:59 PM

Discussion 4

Midterm 01 Sample Questions

Week 3

Recursion and Sorting

Lecture 6 — Sorting

  1. Selection Sort and Loop Invariants
  2. Mergesort
  3. The Merge Operation
  4. Analyzing Mergesort
  5. Using Sorted Structure

Lecture 5 — Recurrences and Binary Search

  1. Querying a Database
  2. Binary Search
  3. Thinking Inductively
  4. Recurrence Relations
  5. Recurrence for Binary Search

Homework 3

Was due Tuesday, Jan 26 at 23:59 PM

Discussion 3

Week 2

Time Complexity

Lecture 4 — Expected Time and Lower Bounds

  1. Average Case and Expected Time
  2. Average Case for the Movie Problem
  3. Theoretical Lower Bounds
  4. Matrix Multiplication

Lecture 3 — Asymptotic Time Complexity, pt. II

  1. Properties of Asymptotic Notation
  2. Notation Practicalities
  3. The Movie Problem
  4. Best and Worst Case Complexity
  5. About the Notation

Homework 2

Was due Tuesday, Jan 19 at 23:59 PM

Discussion 2

Week 1

Introduction

Welcome to DSC 40B!

Here's how to get started:

  • read the syllabus
  • join our campuswire and gradescope with the email invitations you received earlier this week
  • watch the intro lecture (posted below)

See you in lecture.

Lecture 2 — Asymptotic Time Complexity, pt. I

  1. News
  2. Nested Loops
  3. Linear and Quadratic
  4. Big Theta Notation
  5. Big O and Big Omega
  6. Limit Definitions

Lecture 1 — Introduction

  1. The Syllabus
  2. Introduction
  3. Example: Brute Force Clustering
  4. Measuring Efficiency of Algorithms
  5. Time Complexity Analysis

Homework 1

Was due Tuesday, Jan 12 at 23:59 PM

Discussion 1

future weeks

Week 10

Conclusion

Final on Saturday, Mar 13