Differences

This shows you the differences between two versions of the page.

Link to this comparison view

en:projects:details:ola1 [2011/09/26 12:54]
osven created
en:projects:details:ola1 [2016/06/23 11:26]
Line 1: Line 1:
-/* This is the template for project details pages */ 
- 
-/*  
-  The database entry: 
-  "​type"​ is one of the following: phd theses, phd semester, master thesis, master semester, bachelor semester 
-  "​status"​ is one of the following: available, taken, completed (please upgrade accordingly!!!!!!!!!!) ​ 
-  "​by"​ should be filled as soon as the project is taken/​completed 
-  "​completed_dt"​ is the date when the project was completed (YYYY-MM-DD). ​ 
-  "​output_media"​ is the link to the pdf of the project (wiki syntax) 
-  "​table"​ must be "​projects"​ => don't touch it! 
-*/ 
----- dataentry project ---- 
-title : Spectral graph theory and its applications in algorithms 
-contactname:​ Ola Svensson 
-contactmail_mail:​ ola.svensson@epfl.ch 
-contacttel: 31204 
-contactroom:​ BC128 
-type : master semester 
-status : available 
-created_dt : 2011-09-26 
-taken_dt : YYYY-MM-DD 
-completed_dt : YYYY-MM-DD 
-by : the full name of the student 
-output_media : en:​projects:​mahdi_thesis.pdf|Download Mahdi'​s Thesis 
-table : projects 
-====== 
-template:​datatemplates:​project 
----- 
- 
-/* Description of the project */ 
-Spectral graph theory is a rich and powerful theory that relates 
-various graph properties with the eigenvalues and eigenvectors of matrices 
-associated to the graph, such as its adjacency matrix. 
- 
-One of the most famous results is Cheeger'​s inequality that relates the 
-expansion of a graph with the second largest eigenvalue of its adjacency 
-matrix. In addition to being an interesting theoretical result, Cheeger'​s 
-inequality has found numerous algorithmic applications in clustering, image 
-analysis, etc.. 
- 
-After reviewing the basics of spectral graph theory, the aim of this 
-project is to understand its various algorithmic applications. Based on 
-the student'​s interests this can be both a theoretical and practical study. 
-A theoretical study would aim towards understanding recent developments 
-where 
-better (theoretical) algorithms have been given for fundamental problems 
-by the use of spectral methods. A more practical study would instead aim 
-towards implementing some of the algorithms (e.g., clustering) 
-and analyze their performance. 
- 
-The prerequisite is being comfortable with the basics of graph theory and 
-discrete mathematics;​ and programming if the practical direction is chosen.