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