DSC 40B – Theoretical Foundations of Data Science II
This Week
Recursion and Sorting
Lecture 5 — Recurrences and Binary Search
 📖 Reading Sections 2.4.1 and 2.2 in course notes
 🍿 Watch Party 5pm on Zoom
 🎞️ Slides

🎥 Videos

Searching a Database
podcast • prerecorded 
Binary Search
podcast • prerecorded 
Thinking Inductively
podcast • prerecorded 
Recurrence Relations
podcast • prerecorded 
Binary Search Recurrence
podcast • prerecorded

Searching a Database
Lecture 6 — Sorting
 📖 Reading Section 2.1 and 2.3 in course notes
 🍿 Watch Party 5pm on Zoom
 🎞️ Slides

🎥 Videos

Selection Sort and Loop Invariants
podcast • prerecorded 
MergeSort
podcast • prerecorded 
Merge
podcast • prerecorded 
Time Complexity of Mergesort
podcast • prerecorded 
Using Sorted Structure
podcast • prerecorded

Selection Sort and Loop Invariants
Discussion 3
 5:00 pm on Friday via Zoom
 Worksheet not yet posted...
past weeks
Week 2
Time Complexity
Lecture 3 — Asymptotic Time Complexity, pt. II
 📖 Reading Section 1.5 in course notes
 🍿 Watch Party 5pm on Zoom
 🎞️ Slides

🎥 Videos

BigOh and BigOmega
podcast • prerecorded 
Properties
podcast • prerecorded 
Asymptotic Notation Practicalities
podcast • prerecorded 
The Movie Problem
podcast • prerecorded 
Best and Worst Cases
podcast • prerecorded 
About Notation
podcast • prerecorded 
Asymptotic Notation and Limits
prerecorded

BigOh and BigOmega
Lecture 4 — Expected Time and Lower Bounds
 📖 Reading None
 🍿 Watch Party 5pm on Zoom
 🎞️ Slides

🎥 Videos

Average Case
podcast • prerecorded 
Average Case in Movie Problem
podcast • prerecorded 
Expected Time Complexity
podcast 
Lower Bound Theory
podcast • prerecorded 
Matrix Multiplication
podcast • prerecorded

Average Case
Week 1
Introduction
Welcome to DSC 40B!
Here is how to get started:
 Read the syllabus.
 Join our
Campuswire
and
Gradescope
with the email invitations you received earlier this week. If
you didn't receive an email, you can use access code
4210
for Campuswire andJBX6YY
for Gradescope.  The first lecture video will be posted on YouTube and linked below on Tuesday. If you'd like a synchronous lecture experience, feel free to come to the watch party on Tuesday at 5:00 pm on Zoom.
See you in lecture!
Lecture 1 — Introduction
future weeks
Week 4
Faster Selection and BSTs
Week 5
Hashing
Midterm 01 on Thursday, Feb 03
Week 6
Graphs
Week 7
Graph Search
Week 8
Weighted Shortest Paths
Week 9
Minimum Spanning Trees
Midterm 02 on Thursday, Mar 03
Week 10
Conclusion 🏁
Week 11
Final Exam Week
Redemption Exams on Thursday, Mar 17