The program begins in late June, continuing for six to eight weeks through the summer. Students attend for about seven hours each day, spending some time in lectures and the rest working on problem sets.
In addition, some students continue their studies on Saturdays throughout the year on Princeton University’s campus.
Two groups of students participate in the program. The main group consists of high school students, most without significant background knowledge of computer science. Group II consists of high school students who participated in the program for a year, 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.
Main Group: Summer
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 begins studying algorithms, including stable matching, and graph algorithms. Throughout this portion of the summer, the importance of run-time analysis is stressed through the use of Big-O (asymptotic) notation, and all algorithms are proved to give the correct result. Students background in combinatorics and probability then help students to determine the run-times of various algorithms. Topics discussed in class are extended through the use of problem sets, which require the students to both extend pre-existing algorithms and design new algorithms for a particular situation.
Additionally, guest lecturers expose the group to other fields of computer science including computational geometry, cryptography, the probabilistic method, and planar graph coloring.
Main Group: Year-Long
During the year, most students from the main group eagerly continue to meet every other Saturday 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 more on 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.
The focus of Group 2 alternates between approximation algorithms and randomized algorithms. Approximation algorithms are studied during odd-numbered years, and randomized algorithms are studied during even-numbered years.
The following is a summary of a typical odd-numbered year for Group 2:
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.
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.