Pact Group 2
I really enjoyed my second year in PACT as part of their group 2 with Dr. Rajiv Gandhi (see my work for group 1). I joined about 25 other people in group 2 during the summer of 2022. I didn't attend the year round program (due to a scheduling conflict), so normally I wouldn't be allowed to join group 2. Since I was really eager to join group 2 and dive deeper into theoretical CS, I independently studied the year round material. Dr. Gandhi then assessed my understanding and determined that I was eligible for group 2! :)
Group 2 description
Group 2 studies more advanced topics in theoretical computer science, specifically approximation and randomization algorithms. See exactly what topics are covered in the Topics column of Class Materials. I wanted to continue with PACT since I really enjoyed group 1 and CS Theory is REALLY interesting.
As part of group 2, I got to mentor 6 of the group 1 students. I remember how helpful my mentor was in group 1. Since the topics were new to me, I asked my mentor a lot of questions to clarify the topics. I hope I did as good of a job mentoring as my group 1 mentor did.
Another Major Part PACT group 2 is the Guest Speakers. See the Guest Speakers section of the README.
Class Materials
The following is a table used to break down all the materials and supplements for each day. It is a way to organize all the necessary resources per day. NOTE: Many links won't be usable by the public in order to not give away other people work. Specifically, the "lecture materials" and "additional reading" sections are not available for the public.
Additional info:
- For all WS in the Additional Reading section use this for the book The Design of Approximation Algorithms by Williamson and Shmoys.
- VV in the Additional Reading section refer to Vijay Vazirani's Approximation Algorithms book.
- Probability and Computing: Randomized Algorithms and Probabilistic Analysis book by Mitzenmacher and Upfal is written as MU in the Additional Reading section.
- All recording passwords are located here (private file).
| Date | Topics | Lecture Materials | Additional Reading | Homework |
|---|---|---|---|---|
| June 27 Morning | Vertex Cover K-Center |
Class Notes Recording |
K-Center | |
| June 27 Evening | Probability Review | Class Notes Recording |
Probability | |
| June 28 Morning | K-Center Scheduling Parallel Machines Traveling Salesman Problem |
Class Notes Recording |
WS section 2.4 | Question Answer Solution |
| June 28 Evening | Variance Chebyshev's Inequality |
Class Notes Recording |
Probability | Question Answer Solution |
| June 29 | Set Cover | Class Notes Recording |
||
| June 30 | Maximizing float in bank accounts | Class Notes Recording |
WS section 2.5 | |
| July 1 | Linear Programming, LP-rounding | Class Notes Recording |
LP Notes Vertex Cover |
|
| July 5 | Knapsack, Binomial Distribution | Class Notes Recording |
VV sections 8.1-8.2 Probability |
|
| July 6 | Bin Packing, Karger's min-cut algorithm | Class Notes Recording |
Bin Packing MU section 1.4 |
Question Answer Solution |
| July 7 | LP-rounding | Class Notes Recording |
WS sections 4.1-4.3 | |
| July 8 | LP-rounding, Primal-dual | Class Notes Recording |
WS section 4.5 | |
| July 11 | Primal-dual | Class Notes Recording |
Facility Location | |
| July 12 | Estimating a parameter, Randomized Rounding | Class Notes Recording |
Randomized Rounding Chernoff bounds |
Guest Speakers
A large portion of our time in PACT group 2 is with guest speakers. Very accomplished people will come to talk to PACT group 2 and give talks or lectures about various topics in Theoretical Computer Science. All the guest speakers' notes are stored in the "GuestSpeakers" private folder.
| Date | Guest Speaker | Topic | Notes | Lecture Recording |
|---|---|---|---|---|
| July 13 Morning | Professor Sanjeev Khanna | PCP Theorem and its applications | Notes PDF | Recording |
| July 13 Evening | Shreya Mogulothu | Steaming | Notes PDF Lecture Notes |
Recording |
| July 14 | Professor Jelani Nelson | Frequent Items | Notes PDF | Recording |
| July 15 | Professor David Williamson | Max-SAT | Notes PDF WS section 5.1-5.5 |
Recording |
| July 18 | Professor David Williamson | Maximizing Submodular functions | Notes PDF | Recording |
| July 19 | Professor Sepehr Assadi | Graph Streaming | Notes PDF Lecture Notes |
Recording |
| July 20 | Aadityan Ganesh | An invitation to Algorithmic Game Theory | Notes PDF Lecture Notes |
Recording |
| July 21 | Professor Aravind Srinivasan | Dependent Rounding | Notes PDF | Recording |
| July 22 | Aadityan Ganesh | Prophet Inequalities | Notes PDF | Recording |
| July 25 | Vihan Shah | Sublinear Algorithms | Notes PDF Lecture Notes |
Recording |
| July 26 | Professor Matt Weinberg | Bitcoin and Selfish Mining | Notes Slides | Recording |
| July 27 | Rajmohan Rajaraman | Epidemics, Random Walks, and Rumor Spreading | Notes PDF | Recording |