Program Organization

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 summer 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.

IMG_7963


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.

IMG_8588

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.


Main Group: Year-Long

During the year, most students from the summer 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 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: Summer

5057

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.

The following is a summary of a typical summer for Group 2:

2017
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.

2013
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.


Advanced Group

2012
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.

An advanced student preparing to present

2011

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.

Advertisements