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
Recommended Reading: None in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Tuesday, Mar 2
part A: Trees and minimum spanning trees
part B: Properties of MST, and Prim's algorithm
part C: Implementation of Prim's algorithm
Prof. Eldridge
Lecture Slides
Minimum Spanning Trees
Prim's Algorithm
Analysis of Time Complexity
(Optional) Proof of Correctness
Midterm 02 Sample Questions
Blank Worksheet
Solutions
Zoom Recording
past weeks
Week 8
Weighted Shortest Paths
Lecture 15 — Dijkstra's Algorithm
Recommended Reading: None in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Thursday, Feb 25
part A: Dijkstra algorithm for shortest path in positively weighted graphs
part B: Correctness of Dijkstra algorithm
part C: Efficient implementation of Dijkstra algorithm
Prof. Eldridge
Lecture Slides
Dijkstra's Algorithm
Analysis
Lecture 14 — Bellman-Ford
Recommended Reading: None in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Tuesday, Feb 23
part A: Weighted graphs, shortest paths and properties
part B: Does BFS algorithm work for weighted graphs?
part C: Key operation for shortest paths: update(edge)
part D: Bellman-Ford algorithm
part E: Early stopping and negative-cycle detection in Bellman-Ford algorithm
Prof. Eldridge
Lecture Slides
Shortest Paths in Weighted Graphs
The Bellman-Ford Algorithm
Early Stopping and Negative Cycles
Homework 8
Questions
LaTeX Template
and
how to use it
Solutions
Was due Wednesday, Mar 03 at 23:59 PM
Discussion 8
Zoom (Wang)
4:00 PM PST on Thursday
Zoom (Eldridge)
5:00 PM PST on Thursday
Zoom Recording
Discussion Worksheet
Solutions
topic: graphs, bellman-ford
Week 7
Depth-First Search
Lecture 13 — Depth-First Search
Recommended Reading: Section 3.4 in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Thursday, Feb 18
part A: Nesting properties of DFS
part B: DAG and topological sort
Prof. Eldridge
Lecture Slides
Depth-First Search
Nesting Properties of DFS
Topological Sort
Lecture 12 — BFS for Shortest Paths
Recommended Reading: Section 3.3 in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Tuesday, Feb 16
part A: Using BFS for computing shortest path distances, and recovering shortest paths
part B: more about BFS trees and how they encode shortest paths
part C: Introduction to the DFS (depth-first-search) algorithm
Prof. Eldridge
Lecture Slides
Shortest Paths
Finding Shortest Paths with BFS
BFS Search Trees
Homework 7
Questions
LaTeX Template
and
how to use it
Solutions
Was due Wednesday, Feb 24 at 23:59 PM
Discussion 7
Zoom (Wang)
4:00 PM PST on Thursday
Zoom (Eldridge)
5:00 PM PST on Thursday
Zoom Recording
Discussion Worksheet
Solutions
topic: dfs
Week 6
Graphs and Breadth-First Search
Lecture 11 — Breadth First Search
Recommended Reading: Section 3.3 in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Thursday, Feb 11
part A: Graphs search strategy: Breadth-first search(BFS), the algorithm
part B: Full_BFS algorithm, and complexity analysis
part C: Shortest path in unweighted graphs: definition and properties
Prof. Eldridge
Lecture Slides
Breadth-First Search
Time Complexity of BFS
Lecture 10 — Graph Theory
Recommended Reading: Section 3.1 and 3.2 in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Tuesday, Feb 9
part A: Graphs: undirected and directed, motivations
part B: Basics about graphs: degrees, paths, connected components
part C: Graph representations: Ajacency matrix, Ajacency list, dictionary of sets
Prof. Eldridge
Lecture Slides
Graph Theory
Paths
Connected Components
Adjacency Matrices
Adjacency Lists
Dictionary of Sets
Homework 6
Questions
LaTeX Template
and
how to use it
Solutions
Was due Wednesday, Feb 17 at 23:59 PM
Discussion 6
Zoom (Wang)
4:00 PM PST on Thursday
Zoom (Eldridge)
5:00 PM PST on Thursday
Zoom Recording
Discussion Worksheet
Solutions
topic: graphs and bfs
Week 5
Hashing
Midterm 01 on Thursday, Feb 04
Lecture 9 — Hashing
Recommended Reading: None in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Tuesday, Feb 2
part A: Hashing, motivation and hash functions
part B: Hash tables
part C: Use Hash table for faster algorithms, and downside of Hash tables
Prof. Eldridge
Lecture Slides
Hashing and Hash Functions
Hash Tables
Faster Algorithms with Hashing
Homework 5
Questions
LaTeX Template
and
how to use it
Solutions
Was due Wednesday, Feb 10 at 23:59 PM
Week 4
Faster Selection and Queries
Lecture 8 — Binary Search Trees
Recommended Reading: None in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Thursday, Jan 28
part A: Binary search tree (BST): motivation and properties
part B: Operations in BST: search, min/max, insert...
part C: Balanced BST
Part D: Select operation in BST, augmenting data structures
Prof. Eldridge
Lecture Slides
Dynamic Sets, Many Queries
Binary Search Trees
Querying and Insertion in BSTs
Balanced and Unbalanced BSTs
Augmenting BSTs
Lecture 7 — Quickselect
Recommended Reading: None in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Tuesday, Jan 26
part A: Order statistics, and idea behind QuickSelect algorithm
part B: Partition procedure
part C: Time complexity of QuickSelect, Randomized QuickSelect (and expected time), QuickSort
Prof. Eldridge
Lecture Slides
Order Statistics
Quickselect
Partition
Analysis of Quickselect
Quicksort
Homework 4
Questions
LaTeX Template
and
how to use it
Solutions
Was due Tuesday, Feb 02 at 23:59 PM
Discussion 4
Zoom (Wang)
4:00 PM PST on Thursday
Zoom (Eldridge)
5:00 PM PST on Thursday
Zoom Recording
Discussion Worksheet
Solutions
topic: quicksort, quickselect, and bsts
Midterm 01 Sample Questions
Blank Worksheet
Solutions
Zoom Recording
Week 3
Recursion and Sorting
Lecture 6 — Sorting
Recommended Reading: Section 2.1 and 2.3 in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Thursday, Jan 21
part A: Sorting: SelectionSort, and loop invariants
part B: A faster algorithm: MergeSort, and solving its recurrence
part C: 3way MergeSort
Part D: The Movie problem revisited, and made faster!
Prof. Eldridge
Lecture Slides
Selection Sort and Loop Invariants
Mergesort
The Merge Operation
Analyzing Mergesort
Using Sorted Structure
Lecture 5 — Recurrences and Binary Search
Recommended Reading: Sections 2.4.1 and 2.2 in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Tuesday, Jan 19
part A: Binary search: motivation and recursive algorithm
part B: correctness of binary search algorithm
part C: time complexity analysis of binary search, solving recurrences
Part D: more examples of solving recurrences
Prof. Eldridge
Lecture Slides
Querying a Database
Binary Search
Thinking Inductively
Recurrence Relations
Recurrence for Binary Search
Homework 3
Questions
LaTeX Template
and
how to use it
Solutions
Was due Tuesday, Jan 26 at 23:59 PM
Discussion 3
Zoom (Wang)
4:00 PM PST on Thursday
Zoom (Eldridge)
5:00 PM PST on Thursday
Zoom Recording
Discussion Worksheet
Solutions
topic: recurrence relations and sorting
Week 2
Time Complexity
Lecture 4 — Expected Time and Lower Bounds
Recommended Reading: None in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Thursday, Jan 14
Zoom Lecture Recording
Prof. Eldridge
Lecture Slides
Average Case and Expected Time
Average Case for the Movie Problem
Theoretical Lower Bounds
Matrix Multiplication
Lecture 3 — Asymptotic Time Complexity, pt. II
Recommended Reading: Section 1.5 in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Tuesday, Jan 12
Zoom Lecture Recording
Prof. Eldridge
Lecture Slides
Properties of Asymptotic Notation
Notation Practicalities
The Movie Problem
Best and Worst Case Complexity
About the Notation
Homework 2
Questions
LaTeX Template
and
how to use it
Solutions
Was due Tuesday, Jan 19 at 23:59 PM
Discussion 2
Zoom (Wang)
4:00 PM PST on Thursday
Zoom (Eldridge)
5:00 PM PST on Thursday
Zoom Recording
Discussion Worksheet
Solutions
topic: best and worst time complexity
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
Recommended Reading: Section 1.1 - 1.4 in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Thursday, Jan 7
Zoom Lecture Recording
Supplementary Video: More on Nested Loops
Prof. Eldridge
Lecture Slides
News
Nested Loops
Linear and Quadratic
Big Theta Notation
Big O and Big Omega
Limit Definitions
Lecture 1 — Introduction
Recommended Reading: Section 1.6 in
Course Notes
Prof. Wang
Lecture Slides:
pdf
and
powerpoint
Zoom lecture
11:00 AM PST on Tuesday, Jan 5
Zoom Lecture Recording
Prof. Eldridge
Lecture Slides
The Syllabus
Introduction
Example: Brute Force Clustering
Measuring Efficiency of Algorithms
Time Complexity Analysis
Homework 1
Questions
LaTeX Template
and
how to use it
Solutions
Was due Tuesday, Jan 12 at 23:59 PM
Discussion 1
Zoom (Wang)
4:00 PM PST on Thursday
Zoom (Eldridge)
5:00 PM PST on Thursday
Zoom Recording
Discussion Worksheet
Solutions
topic: time complexity analysis
future weeks
Week 10
Conclusion
Final on Saturday, Mar 13