# DSC 40B – Theoretical Foundations of Data Science II

# This Week

## Final Exam Week

Redemption Exams (Eldridge) on Friday, Dec 10

Redemption Exams (Wang) on Thursday, Dec 09

past weeks

# Week 10

## Minimum Spanning Trees 🏁

Lecture 18 on *Complexity Theory* is optional, and won't appear
in the homework. Feel free to watch it at your leisure if you'd
like to know more about one of the most important open problems in
mathematics and computer science: does P = NP?.

### Lecture 18 — Complexity Theory (Optional)

### Lecture 17 — Kruskal's Algorithm

- 📖 Reading Section 3.5 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)

### Lecture 16 — Minimum Spanning Trees and Prim's Algorithm

# Week 9

## Thanksgiving Week

Midterm 02 on Tuesday, Nov 23

**Reminder**: there is no lecture this week due to the midterm exam and the Thanksgiving holiday. Happy holidays!

# Week 8

## Weighted Shortest Paths

### Lecture 15 — Dijkstra's Algorithm

### Lecture 14 — Bellman-Ford

### Midterm 02 Practice

# Week 7

## Depth-First Search

**Reminder**: no lecture on Thursday, November 11 due to Veterans Day.

### Lecture 13 — Depth-First Search

- 📖 Reading Section 3.4 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)

# Week 6

## Breadth-First Search

### Lecture 12 — BFS for Shortest Paths

- 📖 Reading Section 3.3 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)

### Lecture 11 — Breadth First Search

- 📖 Reading Section 3.3 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)

# Week 5

## Graphs

Midterm 01 on Tuesday, Oct 26

### Lecture 10 — Graph Theory

- 📖 Reading Section 3.1 and 3.2 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)

# Week 4

## BSTs and Hashing

### Lecture 9 — Hashing

### Lecture 8 — Binary Search Trees

### Midterm 01 Practice

# Week 3

## Sorting and Faster Selection

### Lecture 7 — Quickselect

### Lecture 6 — Sorting

- 📖 Reading Section 2.1 and 2.3 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)

# Week 2

## Expected Time and Recursion

### Lecture 5 — Recurrences and Binary Search

- 📖 Reading Sections 2.4.1 and 2.2 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)

### Lecture 4 — Expected Time and Lower Bounds

# Week 1

## Time Complexity

### Lecture 3 — Asymptotic Time Complexity, pt. II

- 📖 Reading Section 1.5 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)

### Lecture 2 — Asymptotic Time Complexity, pt. I

- 📖 Reading Section 1.1 - 1.4 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)

# Week 0

## 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
`7589`

for Campuswire and`3YWRDV`

for Gradescope. - Fill out the poll to determine when our second midterm should be.
- Come to the first lecture on Thursday:
- Prof. Wang's lecture is at 9:30 am in WLH 2207;
- Prof. Eldridge's is at 12:30 pm in WLH 2204.

See you in lecture!

### Lecture 1 — Introduction

- 📖 Reading Section 1.6 in course notes
- 🎞️ Slides (Prof. Eldridge)
- 🎞️ Slides (Prof. Wang)
- 🎥 Videos (Prof. Eldridge)