 |
 |
| Algorithms and Complexity |
       |
| |
| Orientation: |
| Heinz
Nixdorf Institute Algorithms and Complexity |
| |
| Web master |
»Search Algorithms«
Christian Schindelhauer
 |
Schedule
Lecture (Vorlesung) 11 Oct 2004 - 31 Jan 2005
Mo. 11.15 am - 12.45 pm, room FU.116
(Beethoven)Exercise Classes (Übung) 18 Oct 2004 - 2 Feb 2005
We. 1.00 pm - 1.45 pm, room E2.316by: Stefan
Rührup
Semester Schedule
| Week |
Date |
Event |
Contents |
Links |
| 42 |
10/11 |
1st
Lecture |
Organisation, Text Search: Rabin-Karp | Slides (ppt) Slides (pdf) |
| 42 |
- |
No Exercise |
- |
- |
| 43 |
10/18 |
2nd
Lecture |
Knuth-Morris-Pratt |
Slides
(ppt) Slides (pdf) |
| 43 |
10/18 10/20 |
1st Exercise |
Text Search:
1. The naive algorithm in 2-D 2. Rabin-Karp in 2-D |
1st Exercise (pdf) |
| 44 |
10/25 |
3rd
Lecture |
Boyer-Moore,
Huffman Codes, Shannon Bound, Kolmogorov Complexity |
Slides
(ppt) Slides (pdf) |
| 44 |
10/25 10/27 |
2nd Exercise |
3. Finite
Automata 4. Knuth-Morris-Pratt Pattern Matching |
2nd Exercise (pdf) |
| 45 |
11/1 |
no
lecture |
Allhallows |
- |
| 45 |
11/1 11/3 |
no exercise 21/2th Exercise |
Tutorial: KMP
& Boyer-Moore |
- |
| 46 |
11/8 |
4th
Lecture |
Liv-Zempel-Codes |
Slides
(ppt) Slides (pdf) |
| 46 |
11/8 11/10 |
3th Exercise |
5. Boyer-Moore 6. Knuth-Morris-Pratt pattern matcher on Huffman codes |
3rd Exercise (pdf) |
| 47 |
11/15 |
5th
Lecture |
Searching
in Compressed Text |
Slides
(ppt) Slides (pdf) |
| 47 |
11/15 11/17 |
4th Exercise |
7./8.
LZW-Compression |
4th Exercise (pdf) |
| 48 |
11/22 |
6th
Lecture |
Searching the Web: Google by Brin & Page | Slides
(ppt) Slides (pdf) |
| 48 |
11/22 11/22 |
5th Exercise |
The
ABF-Pattern Matcher |
5th Exercise (pdf) |
| 49 |
11/29 |
7th
Lecture |
Erratum
to the ABF-Pattern Matcher- Googles Pagerank algorithm |
Slides
(ppt) Slides (pdf) |
| 44 |
11/29 12/1 |
6th Exercise |
Eigenvalues,
eigenvectors, convergence of pagerank |
6th Exercise (pdf) |
| 50 |
12/6 |
8th
Lecture |
Searching the Web: Kleinberg's HITS algorithm | Slides
(ppt) Slides (pdf) |
| 44 |
12/8 |
Mid term exam |
written exam
(F1.110) -
no exercises on Monday |
- |
| 51 |
12/13 |
9th
Lecture |
The
Structure of the Web |
Slides
(ppt) Slides (pdf) |
| 44 |
12/13 12/15 |
Midterm exam results |
Presentation
of the midterm exam results |
- |
| 52 |
12/20 |
10th
Lecture |
Searching
in Power Law Networks |
Slides
(ppt) Slides (pdf) |
| 44 |
12/20 12/22 |
7th Exercise |
Pagerank and
HITS algorithm |
7th Exercise (pdf) |
| 01 |
1/3 |
no
lecture |
bridge
day |
- |
| 01 |
- |
no
exercise |
bridge
day/Feast of Epiphany |
- |
| 02 |
1/10 |
11th
Lecture |
Searching
with Uncertainty Competitive Deterministic Search |
Slides
(ppt) Slides (pdf) |
| 02 |
1/9 1/11 |
8th Exercise |
Pareto and
Poisson Distribution |
8th Exercise (pdf) |
| 03 |
1/17 |
12th
Lecture |
Competitive
Probabilistic Search, Smart Cows, The Wall Problem |
Slides
(ppt) Slides (pdf) |
| 03 |
1/17 1/19 |
9th Exercise |
Searching with
some uncertainty Competitive search for balls |
9th Exercise (pdf) |
| 04 |
1/24 |
no
lecture |
due
to illness |
- |
| 04 |
1/24 1/26 |
10th Exercise |
Proababilistic
online algorithms The wall, room and s-t problem |
10th Exercise (pdf) |
| 05 |
1/31 |
13th Lecture | The Art
Gallery problem, Searching in a Street, The watchmen problem |
Slides
(ppt) Slides (pdf) |
| 05 |
1/31 2/2 |
11th Exercise |
Lower bounds
for the s-t-problem, Near- and far-sighted exploration Wednesday exercise class cancelled |
11th Exercise (pdf) |
| 08 |
2/17
- 2/18 |
Exam |
Oral exam
- registration deadline: 1/31 |
- |
Created:
2004-09-15Last change: 2005-01-30
Christian Schindelhauer (email: schindel@upb.de)