Homepage
	english only		EPFL > I&C > IIF > MTC

Problem Solving in Computer Science

Winter Semester 2008/9

Instructors:

• Lecturer: Tom Henzinger
• Assistant: Verena Wolf

Schedule:

Lectures

• Tuesday, 10:15-12:00, BC04
• Thursday, 10:15-12:00, BC01

Office hours

• On request (mail to verena.wolf@ ... )

Objectives:

Syllabus:

• Graph games.
• Computational Biology.
• Concurrent BDDs.
• Robotics.

• How to search the literature.
• How to write a proof.
• How to write a paper.
• How to referee a paper.
• How to give a presentation.

Prerequisites:

Grading:

Scribing Schedule:

Lecture 1 (Sept 16):

• What is this course about?
• How to write a definition.
• Defining graph games.
• Scribe notes by Radu Negoescu.

Lecture 2 (Sept 18):

• Defining Problem 1: pdf, tex file.
• Scribe notes by Paul Dütting.
• Related work:
  • A. Condon: The complexity of stochastic games.
  • A. Condon: On algorithms for simple stochastic games.
  • H. Gimbert and F. Horn: Simple stochastic games with few random vertices are easy to solve.

Lecture 3 (Sept 25):

• Brief progress reports.
• Technical Writing.
• Sample input file and the associated graph (pdf, tex).
• More samples
• Scribe notes by Tatjana Petrov.

Lecture 4 (Sept 30):

• Reports on Problem 1.
• Scribe notes by Horatiu Jula.

Lecture 5 (Oct 2):

• Technical Writing (continued).
• Scribe notes by Thomas Hofer.

Lecture 6 (Oct 7):

• Dry runs of the SSG algorithms.
• Scribe notes by Dan Alistarh.

Lecture 7 (Oct 9):

• Algorithm contest.
• Scribe notes by Alexander Pilchin.

Lecture 8 (Oct 14):

• Introduction of Project 2.
• Notes by V. Wolf.
• Scribe notes by Mihailo Kolundzija.

Lecture 9 (Oct 16):

• Project 2 (continued).
• Notes by V. Wolf.

Lecture 10 (Oct 21):

• Brief progress reports on Problem 2.
• Numerical Methods for Steady State Analysis of Markov Chains.
• Scribe notes by Quentin Bonnard.
• Useful Links:
  • Yousef Saad. Iterative methods for sparse linear systems (1st edition)
  • William J. Stewart. Numerical Methods for Computing Stationary Distributions of Finite Irreducible Markov Chains.

Lecture 11 (Oct 23):

• Brief progress reports on Problem 2.
• Numerical Methods for Steady State Analysis of Markov Chains (continued).
• Scribe notes by Ali Galip Bayrak.

Lecture 12 (Oct 28):

• Brief progress reports on Problem 2.
• How to write a proof.
• Scribe notes by Silviu Andrica.

Lecture 13 (Oct 30):

• How to write a proof (continued).
• Scribe notes by Sven Gowal.

Lecture 14 (Nov 4):

• Introduction of Project 3: a concurrent BDD implementation.
• Scribe notes by Fabrice Rousselle.

Lecture 15 (Nov 6):

• Brief progress reports on Problem 3.
• Concurrent reasoning for linked lists.
• Scribe notes by Salman Mirghasemi.

Lecture 16 (Nov 11):

• Project 3, implementation issues.
• Scribe notes by Romain Rossier.

Lecture 17 (Nov 13):

• Concurrent reasoning for linked lists (continued).
• Scribe notes by Vitaly Chipounov.

Lecture 18 (Nov 18):

• How to write a great research paper.
• Link to the video of Simon Peyton Jones on How to write a good research paper.
• Scribe notes by Hossein Hojjat.

Lecture 19 (Nov 20):

• Comparison of concurrent BDD implementations.
• How to write a great research paper (continued).
• Scribe notes by Quentin Bonnard.

Lecture 20 (Nov 25):

• Setting up Project 4: Lego NXT Cruise Control.
• Useful links:
  • First steps.
  • NXC guide.
  • NXC tutorial.
  • Sample file avoid.nxc.
  • How to give a good research talk.
  • Link to Simon Peyton Jones.
• Scribe notes by Thomas Hofer.

Lecture 21 (Nov 27):

• How to give a good research talk (continued).
• How to have a bad carreer in research/academia by David Patterson.
• More useful NXT links:
  • Firmware update.
  • NXT Software.
  • Software updates.
• Scribe notes by Dan Alistarh.

Lecture 22 (Dec 2):

• Talks:
  • Quentin (Underwater Rugby),
  • Paul (Human Computation - An Attempt to Combine the Computational Power of Humans and Computers),
  • Vitaly,
  • Xavier,
  • Fabrice,
• Scribe notes by Fabrice Rousselle.

Lecture 23 (Dec 4):

• Course evaluation.
• Carry-the-box-contest.
• Ian Parberry's Guide for New Referees in Theoretical Computer Science.
• Scribe notes: see scribe of notes lecture 25.

Lecture 24 (Dec 9):

• Talks:
  • Silviu,
  • Tatjana,
  • Romain,
  • Dan,
  • Thomas
• Scribe notes: see scribe notes of lecture 25.

Lecture 25 (Dec 11):

• Talks:
  • Radu,
  • Alex,
  • Ali,
  • Sven,
  • Salman,
  • Hossein
• Scribe notes by Xavier Jimenez.

Lecture 25 (Dec 16):

• Talks:
  • Horatiu
• Final NXT contest.