HONOURS PROGRAM
This section of the course website is dedicated to the bonuses available to the members of the honours program. Bonus points you accumulate through these assignments will be added additively to the grade of the final exam (post factor in case there is one granted) and according to the following rules
​
-
If your final exam grade is < 60.00 (pre-factor and roundings if any), then bonus points accumulated will not be added to your exam grade.
-
If your final exam grade is ≥ 60.00 (pre-factor and roundings if any), then all bonus points accumulated will be added to your final exam grade.
-
Bonus point can never be used to pass the course; only to improve an already passing grade.
At most 20 bonus points can be accumulated.
​
On all bonuses you can work in groups of at most 4 students.
All bonus work is to undergo a defence attended by the entire team in a group interview. The grades of these defences are individual. Each team member is evaluated on how he or she performed during the interview.
​
Be aware of the following policies:
​
General Instructions
On the hitchhiker
phenomenon
Allowing so called hitchhikers into your team is forbidden. It is an offence that the whole team is responsible for. Upon the identification of a hitchhiker within a team through a defence (this identification is determined by the staff), all members of the team will receive a grade of zero for the entire course.
​
hitchhiker := a person who joins a team but contributes nothing but his or her name (according to the staff's definition).
How many guards does it
take to guard an art gallery?
Read and study the linked sketch of a proof by Fisk for a result of Chvátal asserting that essentially n/3 guards are necessary and sufficient in order to guard any n-polygon.
​
You are to supply an accurate summary of the proof sketch and complete any missing details if there are any.
In your defence, you will be asked to reproduce this proof.
​
-
Submit a pdf file
-
Credits ≤ 1.5
-
Must be prepared using LaTex
-
Cambridge level English expected
Wigderson's paper
An Approximation algorithm for the graph colouring problem
Proposition 5.23 in the course booklet describes an algorithm for colouring a 3-colourable graph using √n colours. This algorithm is taken from a paper of Avi Wigderson (Institute for Advanced Studies, Princeton). This proposition is also covered in one of the TA-sessions.
​
Read Wigderson's paper (on the left). State Wigderson's main result in this paper and prove it. Be careful not to merely copy the paper. Complete all missing details.
-
Submit a pdf file. ​
-
Credits ≤ 2
-
Must be prepared using LaTex
-
Cambridge level English expected
​​
Avi Wigderson
Abel Prize | Turing Award
Avi Wigderson is the first person to win both the Abel Prize (as a mathematician) as well as the Turing Award (as a computer scientist).
Determining the chromatic index of a graph is NP-hard
Vizing's Theorem pins the chromatic index of a graph between its maximum degree and its maximum degree plus 1. Despite this fairly tight containment of the chromatic index it is NP-hard to distinguish which alternative is the truth.
​
Read the paper associated with this section (see on the right) and prove that determining the chromatic index of a graph is NP-complete.
-
Submit a pdf file
-
Credits ≤ 2
-
Must be preperaed using LaTex
-
Cambridge level English expected
Chromatic index is NP-hard
A result of Dirac shows that every k vertices lie on a common cycle in k-connected graphs. This result cannot be extended to edges. The writeup on the left handles the case of 3 edges sharing a common cycle in 3-connected graphs. In particular, the writeup delivers a result characterising the positioning of the edges, so to speak, for which a common cycle containing them all is possible.
​
Read the sketched proof and write it up carefully and precisely.
-
Submit a pdf file​
-
Credits ≤ 4
-
LaTeX here is optional; if the lecturer is impressed this can land more credit points.
-
Cambridge level English is expected
Solve 11 LeetCode questions at the hardest difficulty.
-
House your solutions on a publicly accesible GitHub account.
-
For each proglem you are to iclude both a mathematical proof of correctness + the most efficient code solving the problem.
-
In the group interview, you will have to:
-
Defened your work.
-
Defend your choice of problems and impress the lecturer that what you chose is in fact quite hard to solve.
-
You will be handed a new LeetCode question during the interview and you will be asked to solve it during the interview. It is possible that several new LeetCode questions will be presented to you in order to cover the entire group.
-
-
Submit a GitHub link (during the interview)
-
Credits ≤ 5
Handeling Big Data
TESTING A FRACTION OF THE DATA
In the field of Property Testing, we seek sub-linear algorithms (i.e. ones that do not read their entire input) yet are able to determine whether the a given object has a desired property with appropriate probability or it is "far" away from having it with appropriate probabilty. This field of study is intimately related to the field of Learning Theory. The canonical algorithm in this area is granted oracle access to the object being tested and the aim is to minimise the number of queries made to the oracle in order to make the above probabilistic assertions about the object.
Oded Goldreich
Israel Prize
The Assignment(s)
TAKE ON GOLDREICH'S BOOK
-
Study the material above
-
Come to the interview and defend your knowledge.
-
During the interview you might be handed a new question to solve on the board or a related text to read and explain in real time.
-
Credits ≤ 6
On the spectrum of graphs
Several matrices can be associated with graphs & networks. In this part of the course, we focus on two such matrices, namely the adjacency matrix of a graph and its Laplacian matrix. For a single graph, these two matrices are spectrally related (i.e., there are connections between the eigenvalues of these). The emergence of patterns and other invariants can be deduced or read out from the spectrum of these matrices.
The Assignment
-
Study the material above.
-
Come to the interview and defened your knowledge.
-
Be ready to be handed a new question to solve on the board or a text to read and explain in real time.
-
Credits ≤ 6​