# Coursework management

## Design & Analysis of Algorithms ECS 222A

- [Planner schedule and recordings](https://canvas.ucdavis.edu/courses/562076/pages/planned-schedule-and-recordings)
- [Syllabus](https://canvas.ucdavis.edu/courses/562076/assignments/syllabus)
- [Gradescope](https://www.gradescope.com/courses/258761)
- [Final Project](https://canvas.ucdavis.edu/courses/562076/assignments/669058)
- [Lecture Slides for Algorithm Design](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/)

---

### Lectures

- **Week 1: Divide and Conquer**
- **Lecture 1: 3/29 Intro, and review**
- [Tiny Math Primer](https://drive.google.com/file/d/1NyyYnK21z4g7Cn9nelwFm574Ez99v009/view?usp=sharing)
- Asymptotic Analysis: [Big-O, limit lemma theorem Introduction to Divide and Conquer solving recurrences via ](https://drive.google.com/file/d/1Ndc04MKD1DzUX2QXHWlKTONL18KZD36k/view?usp=sharing)
- [substitution  (Links to an external site.)](https://drive.google.com/file/d/1XmIuHTf1TDfxNUJ8DxTLACF9vF0Hq_C9/view?usp=sharing)
- [unwrapping/recurrence tree method  (Links to an external site.)](https://drive.google.com/file/d/1g9yi1pfN9TR9M2fViR-FBiyWH5wWHbkm/view?usp=sharing)
- [Masters theorem](https://drive.google.com/file/d/1_NR16nOXPTuRVZNvsxhtqBKlQlVGTyyo/view?usp=sharing)
- **Lecture 2: 3/31**
- [Deterministic selection in linear time  (Links to an external site.)](https://drive.google.com/file/d/13vDhBinGKVU2XX3Q4E4xyIqk5xvuFA_8/view?usp=sharing)

---

## Quizes

### Quiz 1

**Think of something like that:**
A disorganized carpenter has a mixed pile of  n  nuts and  n  bolts. The goal is to find the corresponding pairs of nuts and bolts. Each nut fits exactly one bolt and each bolt fits exactly one nut. By fitting a nut and a bolt together, the carpenter can see which one is bigger (but the carpenter cannot compare two nuts or two bolts directly). Design an algorithm for the problem that uses  nlog n  compares (probabilistically).

- **Some resources**
- http://seanzhou1023.blogspot.com/2017/04/quiz-6-princeton-algorithm.html
- https://github.com/ekalachev/nuts-and-bolts
- http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts.html
- https://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem/

Quiz 1: 4/5 
Quiz 2: 4/12 
**Midterm 1: 4/26**
Quiz 3: 5/3 
Quiz 4: 5/10 
Quiz 5: 5/17 
**Midterm 2 : Last day of class 6/2**

---

## Theory of Computation

- [Syllabus](https://canvas.ucdavis.edu/courses/556243/assignments/syllabus)

## Book Chapters
- [chapter 1: PrologueLinks to an external site.](https://video.ucdavis.edu/playlist/details/1_6f35d59n)
- [chapter 2: The BasicsLinks to an external site.](https://video.ucdavis.edu/playlist/details/1_92gxymmw)
- (There are no lectures for chapter 3.)
- [chapter 4: Needles in a Haystack: The Class **NP**Links to an external site.](https://video.ucdavis.edu/playlist/details/1_tc2y5uwz)
- [chapter 5: Who is the Hardest One of All? **NP**-CompletenessLinks to an external site.](https://video.ucdavis.edu/playlist/details/1_7rjn2t74)
- [chapter 6: The Deep Question: **P** vs. **NP**Links to an external site.](https://video.ucdavis.edu/playlist/details/1_ffeye37x)
- [chapter 7: The Grand Unified Theory of ComputationLinks to an external site.](https://video.ucdavis.edu/playlist/details/1_jb9526ok)
- [chapter 8: Memory, Paths, and GamesLinks to an external site.](https://video.ucdavis.edu/playlist/details/1_3x0aawln)

### Live Lectures
1a: [Lec 1a](https://ucdavis.zoom.us/rec/share/JXlnrYNJ1En4ryx1_ip_0nDrMru0GaGn7zmomWZaZjCj5oLoUTUYcHGG0emNCSJw.8GI5peokc3VZcPuT)

1c: [Lec 1c](https://ucdavis.zoom.us/rec/share/EsMILy8Nvngt6aUByQScDtKMlyXtGsn_CJ8PJHVCvkWFnxCXp6bSzNnIX0-hWxgC.mANNLQbNK8sRxrbM)

2a: [Lec 2a](https://ucdavis.zoom.us/rec/share/O-7_7ftD3kQNIXMYwUsJHSMvtU4pqq_CmFVWK28xDzA2adTZ0M-N55iAh7enhLru.2oC9hhW4XUY73x2A)

### Lectures

- [lecture-schedule](https://canvas.ucdavis.edu/courses/556243/pages/lecture-schedule)

---

## Software Engineering

### Lectures