Theory Pearls, Fall 2008
Course plan
Lectures
The course Pearls of Theory (Teoripärlor) is
a series of lectures on several important and/or
interesting topics in theoretical computer science
given by different guest and departmental speakers.
The lectures (on Mondays 1 p.m. - 3 p.m.) are followed
by rounding-off sessions (on Fridays 1 p.m. - 3 p.m.)
usually devoted to problem solving and discussions.
The lectures will be given in English.
Goals
Pearls of Theory is really a seminar-series, where the students are
exposed to different researchers and have to show initiative in
seeking complementary materials, flexibility in adapting to different
styles and of course the ability to solve theoretical problems
individually.
Recommended for
For those interested in PhD studies, especially of
theoretical character, it is a very good introduction enabling to come
closer to the research frontier.
Examination
In order to pass the course, students are
required to return
acceptable solutions for a sufficient number of homework problems.
Prerequisites
The participants are expected to know the basics
of theoretical computer science
(e.g., corresponding to DAT107, DAT119 or DAT302).
Contents
The tentative plan of the course is as follows:
- September 1, 1 p.m. - 2 p.m.,
"Introduction meeting",
Andrzej Lingas, Lund University.
- September 8, 1 p.m. - 3 p.m.,
"Approximation algorithms for traveling salesperson problem",
Andrzej Lingas, Lund University, article,
homework.
- September 22, 1 p.m. - 3 p.m.,
"Lowest Common Ancestors in Directed Acyclic Graphs",
Andrzej Lingas, Lund University,
article,homework
.
- October 6, 1 p.m. - 3 p.m., "Sampling in Large Matrices and
Approximation of CSP",
M. Karpinski, Bonn University slides,
homework.
- October 13, 1 p.m. - 3 p.m.,
"Memory Efficient Graph Exploration",
L. Gasieniec, Liverpool
University, article,
slides.
- October 29, 2 p.m. - 3 p.m.,
"Repetitive patterns", J. Gudmundsson, NICTA Sydney,
article, slides.
- November 10, 1 p.m. - 3 p.m.,
"Art Gallery Problems", B. Nilsson, Malmo University,
slides, homework.
- November 17, 1 p.m. - 3 p.m., "The Union-Find Problem", R. Karlsson, Lund
University
.
- November 24, 1 p.m. - 3 p.m., "Edge coloring of graphs
using a bounde number of colors", A. Kosowski, Bordeaux
and Gdansk Universities, article1,
article2, article3.
- December 8, 1 p.m. - 3 p.m., "Shearer's entropy lemma and the
TSP", T. Husfeldt, Lund
University, slides.
Preliminary results
For G at least 450,
for VG at least 610, (*) the grade can be upgrated
after returning the extra 1st assignment.
- Antoniadis Antonios 874 VG (A, first place)
- Haseeb Baluch 612 VG (C)
- Isen Begiri 493.5 G (E)
- Cui Di 586.5 G (D)
- Roubesh Jhumun 467.5 G (E)
- Märta Leffer 431 (almost G) (E)
- Hanna Mikhailava 450 G (E)
- Paul Stapleton 804.5 VG (A, second place)
- John Wangoudu 599.5 G (D)
- Leo Taslaman 681 VG (B, third place)*
- Dennis Lindblad 135*
Last edited December 29, 2008 by Andrzej
Lingas
