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 provided that you score at least 70 on the final. 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 ≤ 2
-
Masterful LaTex ≤ 0.5 credits
-
Cambridge level English ≤ 0.5 credits
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 ≤ 3
-
Masterful LaTex ≤ 0.5 credits
-
Cambridge level English ≤ 0.5 credits
Avi Wigderson
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
-
Masterful LaTex ≤ 0.5 credits
-
Cambridge level English ≤ 0.5 credits
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 ≤ 3
-
Masterful LaTeX ≤ 0.5 credits
-
Cambridge level English ≤ 0.5 credits
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.
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.
Tenants of linear algebra
Our encounter here with Spectral Graph Theory serves an additional purpose in that it allows us to review some core results and concepts from linear algebra.
Reading Assignment
Read Chapters 2,4,5,6 in this booklet.
Programming bonuses
-
Implement the Hungarian Method algorithm for finding a maximum matching in bipartite graphs | Credits ≤ 2.
-
Implement Brooks' algorithm for graph colouring | Credits ≤ 3
-
Edmonds devised an algorithm for finding a maximum matching in an arbitrary graph; it is often called the blossom algorithm. Research this algorithm and implement it | Credits ≤ 3
-
Implement any approximation algorithm taught in class for the minimum set cover problem employing linear programming. You can use black box packages for linear programming in this implementation | Credits ≤ 2
All programming bonuses must be accompanied with a GUI that can show incremental progress of the algorithm in a step-by step.
Defence slots for the bonuses
Please pick a slot for your team in this link