18.434 Undergraduate Seminar in Theoretical Computer Science
Spring 2013
Instructor: Lorenzo Orecchia
Lecture:
MWF12
(4-144)
Office Hours: W 3:30-5pm and by appointment
(2-363A)
:
Course Information
This is an undergraduate seminar in Theoretical Computer Science. It carries CIM credit for the Math department. As with all CIM subjects, the emphasis is on communication, both oral and written. Enrollment is limited by the department.
Subject Matter The topic for this spring is Spectral Graph Theory and Algorithms. The core idea of the spectral approach is to look at graphs as linear operators, i.e. matrices, and exploit our understanding of linear algebra and geometry to study these operators. Surprisingly, this approach is able to reveal many important combinatorial properties of graphs and is very useful in the design of algorithms in many real-world applications, e.g. image segmentation, clustering, webpage ranking. The design of very efficient spectral algorithms for fundamental graph problems is a active area of research in TCS (particularly so here at MIT ).
See the Syllabus sheet for a tentative list of topics covered in the course
.
Administration
Student Presentations Each student in the class will, in turn, lead a class, on a subject assigned by the Instructor. The material the presenter is expected to cover will usually come from freely available online lecture notes or manuscript. See the Online Resources sheet for a list of sources of which we will make use.
Homework Occasional homework and at least one short writing composition will be assigned in the first part of the semester.
Final Project The final project will consist of reading, presenting and writing a report about a research article (or a number of related research articles). By Spring Break (March 25), each student will be expected to choose a final project. The Instructor will provide a list of possible projects, but students are encourage to propose their own project in consultation with the Instructor.
Be sure to read the course information sheet for more detailed information about course policies.
Announcements
Assignment Grades
Homework 1 and 2 have been graded. Grades should be available on Stellar. Comments are accessible via Stellar, if you handed in your homework. Otherwise, you may pick up your homework in my office.Paper and presentation grades will be available tomorrow.
Announced on 18 May 2013 10:39 p.m. by Lorenzo Orecchia
Deadline Extensions II
Dear all,It has been pointed out to me that I never uploaded the lecture notes about the classes relating to Homework 2. I apologize, and I will do that in the next few days. Meanwhile, I am postponing the deadline for Homework 2 to next Monday, May 6.
Also, do not forget that the final version of your paper is due May 10.
All the best,
Lorenzo
Announced on 28 April 2013 12:19 p.m. by Lorenzo Orecchia
Deadline Extensions
In light of recent events, I am extending the deadline for the submission of the paper draft to Friday, 4/26, and the homework deadline for homework to Monday, 4/29.If you have been particularly affected by the past few days, feel free to contact me to discuss other possible arrangements.
All the best,
Lorenzo
Announced on 20 April 2013 9:44 p.m. by Lorenzo Orecchia
Reading Assignment for Friday
A reading assignment for this Friday has been posted under homework. The assignment involves answering a few questions that should be handed in during class. This assignment helps you to prepare for the writing workshop on Friday.Announced on 09 April 2013 5:59 p.m. by Lorenzo Orecchia
Class Cancelled Today 4/8
Dear all,Apologies for the late notice. Today's class is canceled. Class will resume regularly on Wednesday, when we will finish our coverage of random graphs and start preparing for the writing workshop, which will be held by Susan Ruff on Friday.
I am sorry again for the late change of plan. I hope you do enjoy an early lunch.
Best,
Lorenzo
Announced on 08 April 2013 11:16 a.m. by Lorenzo Orecchia
