Two groups of students participate in the summer program. Group I consists of high school students, most without significant background knowledge of computer science.
Some students continue their studies through the year-round program. These students participate in the following summer as part of Group II, along with undergraduate students and incoming graduate students with prior experience in theoretical computer science.
During some years, there is an advanced group consisting of incoming graduate students with significant experience in the field.
Starting 2023, students in Asia may also participate in the PACT Asia program which will be offered at a time that works well for students in Asian time zones.
In the main group, most students have limited experience with theoretical computer science. Students start the program by studying topics in discrete mathematics such as systematic counting and methods of proof. They then learn proof techniques, such as induction, and basic graph theory to prove various theorems.
Additionally, the students are exposed to combinatorics and probability. Though many students have been exposed to probability in school, the program introduces them to more theoretical and fundamental topics, developing sophisticated ideas from basic principles. Topics covered in these lectures advance in difficulty as students cover set theory, advanced permutations and combinations, conditional probability, independent events, random variables, and linearity of expectation. For the probability section of the course, the problem sets feature numerous challenging exercises that both verify and challenge students’ instincts as to the likelihood and independence of events.
Later in the summer, the main group may begin studying algorithms if time permits. Students may be introduced to topics like asymptotic analysis and Big-O notation as well as a few basic algorithms like Euclidean GCD.
Additionally, guest lecturers expose the group to other fields of computer science including computational geometry, cryptography, the probabilistic method, and planar graph coloring.
During the year, most students from the summer main group eagerly continue to meet every other weekend either virtually or on Princeton’s campus. During these sessions, Professor Gandhi gives lectures on specific classes of algorithms including divide and conquer, dynamic programming, network flows, and greedy algorithms. In addition, students learn about NP-completeness and how to make polynomial-time reductions from one decision problem to another. Students begin to explore more of the concepts featured in Algorithm Design by Jon Kleinberg and Éva Tardos.
Group 2 consists of students who have participated in PACT in previous years, and other students—usually undergraduate students—who have equivalent knowledge. Between lectures and homework, Group 2 students are responsible for mentoring Main Group students, grading their homework, and creating difficult and challenging exam problems.
The focus of Group 2 generally alternates between approximation algorithms and randomized algorithms. Guest Lecturers often come and teach specific topics to Group 2 students.
From 2023, students in Asia may also participate in the PACT Asia program. Lectures are given by the same instructor as PACT, Professor Gandhi, but at a time more convenient for Asian time zones.
Though sharing the same instructor and being run by past PACT students, PACT Asia is largely independent of PACT, with different enrollment procedures, TAs, and logistics in general. More information can be found on PACT Asia’s website and their official account on WeChat.
During the summer of 2017, Group 2 consisted of high school students previously involved in the program, several college undergraduates, and students from India who were studying abroad. During this summer, randomized algorithms were studied. The first two weeks consisted of lectures prepared by Prof. Rajiv Gandhi which covered material from the textbook Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Eli Upfal and Michael Mitzenmacher. For the duration of the program, there were several guest lecturers who spoke about a wide range of topics including Random Walks in Graphs, Zero-Knowledge Proofs, and the Lovász local lemma.
During the summer of 2013, Group 2 consisted of high school students previously involved in the program, an undergraduate, and two incoming doctoral students in computer science. The topics covered included the majority of the first eight chapters of the graduate-level text The Design of Approximation Algorithms by David Williamson and David Shmoys. This section of the course consisted of lectures prepared by Prof. Rajiv Gandhi and guest lecturers as well as of lectures by students in the program. This gave even high school students the opportunity to study both foundational and advanced topics in the field of approximation algorithms and to present to the group.
Guest lectures covered both advanced topics in approximation algorithms and other topics in theoretical computer science and discrete mathematics. The students thus were introduced to complexity theory and coding theory in their proper mathematical contexts.
A highlight of the summer was Professor David Williamson’s three day visit. David Williamson, a pioneer in the fields of graph and scheduling approximation algorithms and an author of the main textbook used in the course, gave six lectures on topics in approximation algorithms. These lectures included several advanced results in approximation algorithms, one of which was his own application of semidefinite programming to the Maximum Cut problem. This incredible opportunity was very educational for the students.
Over the course of the summer, students worked individually and in small groups on open problems, and continued their work after the summer.
During the summer of 2012, the advanced group consisted of 5 students: two recent high school graduates who had participated in the summer program previous years and three incoming graduate students from India who Professor Gandhi had taught as a Fulbright Scholar. These students all had taken the equivalent of a standard undergraduate algorithms course and were already familiar with approximation algorithms for NP-Hard problems. In the program, they worked through the book The Design of Approximation Algorithms by Williamson and Shmoys, a standard graduate-level text, thoroughly covering most of the material of the first nine chapters. They focused particularly on the Primal-Dual Method and on approximation algorithms for Cuts and Metrics problems. Vijay Vazirani’s Approximation Algorithms was used as a supplement to the students’ reading.
Both Professor Gandhi and the students themselves presented sections of the book to the other students in the group, which enabled each student to gain confidence in researching and presenting algorithms. In this manner, the students even presented such theoretically sophisticated topics as Fakcharoenphol, Rao, and Talwar’s algorithm for the Probabilistic Approximation of General Metrics by Tree Metrics and Goemans and Williamson’s Primal-Dual 2-Approximation for the Prize-Collecting Steiner Tree Problem. This work provided an opportunity for both independent thinking and group study.
Additionally, several guest lecturers presented to the advanced group. These lectures took two forms for the most part: some introduced the students to fields of computer science outside their immediate knowledge, such as Sublinear Algorithms or Secure Multiparty Computation, while others demonstrated uses of more advanced and specialized techniques, such as the use of the Probabilistic Method in Combinatorics and proofs using Incidence Theorems. They also had the opportunity to learn from speakers at a conference on Provable Bounds in Machine Learning held at Princeton that summer.
The advanced group spent a significant amount of time working with the main body of students, helping them with homework problems and marking their answers. This allowed them to further practice explaining theoretical concepts and also to review once more the basics.
Towards the end of the summer, the advanced group began to work on an open problem in scheduling.
The advanced group of students began the summer reviewing some techniques in approximations algorithms. They also learned semi-definite programming and techniques to obtain polynomial-time approximation schemes for NP-Hard problems. Probability was a major component of their studies; they learned about topics such as tail bounds and expectation in the context of randomized algorithms. Guest lecturers taught these students about more advanced topics, such as an introduction to computational complexity and spanner graphs, including some recent results. By the end of the summer, the students had begun to read research papers covering modern developments in approximation algorithms, and they attended the APPROX-RANDOM workshop.