lunduniversity.lu.se

Computer Science

Faculty of Engineering, LTH

Denna sida på svenska This page in English

Lectures

Lectures 2017

LectureDateWhat
1Tue 29 AugRandomized algorithms I
2Thu 31 Aug

Randomized algorithms II

3Tue 5 Sep

Approximation algorithms I

xThu 7 SepNo Lecture!
4Tue 12 SepApproximation algorithms II
5 Thu 14 SepExponential time algorithms
6Mon 18 SepRandomized algorithms III
7Mon 25 SepParameterized algorithms
8Mon 2 OctAlgebraic algorithms
9Mon 9 OctComplexity of hard problems

Detailed curriculum:

 

  1. Randomized algorithms I: [KT] 13.1–2
  2. Randomized algorithm II: [KT] 13.3-5
  3. Approximation algorithms I: [KT] 11.1–3
  4. Approximation algorithms II: [KT] 11.4, 11.6, 11.8, 12.4
  5. Exponential time algorithm: [exp-notes]
  6. Randomized algorithms III: [MU] 7.1
  7. Parameterized algorithms: [KT] 10.1-4, [ftp-notes]
  8. Algebraic algorithms: Strassen-slides, [exp-notes, section 4, “finding triangles”], Berkeley CS 367 2:1, CS 271 1,2 
  9. Complexity of hard problem: [ftp-notes] [inap]

 

[exp-notes]: Husfeldt, “Expontial Time Algorithms”

[ftp-notes]: Husfeldt, “supplementary notes for fixed parameter tractability”

[inap]: Husfeldt, “EDAN55, supplementary notes for inapproximability”

[MU] Mitzenmacher & Upfal, Probability and Computing, Cambridge.

Berkeley CS 367: http://theory.stanford.edu/~virgi/cs367/lecture2-0.pdf

Berkeley CS 271: https://people.eecs.berkeley.edu/~sinclair/cs271/n1.pdf, https://people.eecs.berkeley.edu/~sinclair/cs271/n2.pdf

Strassen-slides: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/05DivideAndConquerII-2x2.pdf, “matrix multiplication”

Current research:

 [V. Williams] Hardness of easy problems: Basing hardness on popular conjectures such as the Strong Exponential Time Hypothesis. 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). http://vesta.informatik.rwth-aachen.de/opus/volltexte/lipics-complete/lipics-vol43-ipec2015-complete.pdf

[Backurs-Indyk] Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). arxiv:1412.0348.

[Husfeldt] Computing Graph Distances Parameterized by Treewidth and Diameter. Handout.

 

 

Lectures 2016

LectureDateWhat
1Tue 30 AugRandomized algorithms I
2Thu 1 Sep

Randomized algorithms II

3Tue 6 Sep

Approximation algorithms I

4Thu 9 SepApproximation algorithms II
5 Tue 13 SepExponential time algorithms
6Thu 15 SepRandomized algorithms III
7Mon 19 SepParameterized algorithms
8Mon 26 SepAlgebraic algorithms
9Mon 3 OctComplexity of hard problems
10Mon 10 OctCurrent research

Detailed curriculum:

 

  1. Randomized algorithms I: [KT] 13.1–2
  2. Randomized algorithm II: [KT] 13.3-5
  3. Approximation algorithms I: [KT] 11.1–3
  4. Approximation algorithms II: [KT] 11.4, 11.6, 11.8, 12.4
  5. Exponential time algorithm: [exp-notes]
  6. Randomized algorithms III: [MU] 7.1
  7. Parameterized algorithms: [KT] 10.1-4, [ftp-notes]
  8. Algebraic algorithms: Strassen-slides, [exp-notes, section 4, “finding triangles”], Berkeley CS 367 2:1, CS 271 1,2 
  9. Complexity of hard problem: [ftp-notes] [inap]
  10. Current research: [Backurs-Indyk, V. Williams, Husfeldt]

 

[exp-notes]: Husfeldt, “Expontial Time Algorithms”

[ftp-notes]: Husfeldt, “supplementary notes for fixed parameter tractability”

[inap]: Husfeldt, “EDAN55, supplementary notes for inapproximability”

[MU] Mitzenmacher & Upfal, Probability and Computing, Cambridge.

Berkeley CS 367: http://theory.stanford.edu/~virgi/cs367/lecture2-0.pdf

Berkeley CS 271: https://people.eecs.berkeley.edu/~sinclair/cs271/n1.pdf, https://people.eecs.berkeley.edu/~sinclair/cs271/n2.pdf

Strassen-slides: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/05DivideAndConquerII-2x2.pdf, “matrix multiplication”

Current research:

 [V. Williams] Hardness of easy problems: Basing hardness on popular conjectures such as the Strong Exponential Time Hypothesis. 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). http://vesta.informatik.rwth-aachen.de/opus/volltexte/lipics-complete/lipics-vol43-ipec2015-complete.pdf

[Backurs-Indyk] Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). arxiv:1412.0348.

[Husfeldt] Computing Graph Distances Parameterized by Treewidth and Diameter. Handout.

 

 

Lectures 2014

LectureDateWhat
1Mon 1 SepRandomized algorithms I
2Thu 4 Sep

Randomized algorithms II

3Mon 8 Sep

Approximation algorithms I

4Thu 11 SepApproximation algorithms II
5 Mon 15 SepExponential time algorithms
6Thu 18 SepRandomized algorithms III
7Mon 22 SepParameterized algorithms
8Mon 29 SepComplexity of hard problems
9Mon 6 OctStreaming algorithms
10Mon 13 OctCurrent research

Detailed curriculum:

 

  1. Randomized algorithms I: [KT] 13.1–2
  2. Randomized algorithm II: [KT] 13.3-5
  3. Approximation algorithms I: [KT] 11.1–3
  4. Approximation algorithms II:
  5. Exponential time algorithm: [Hu-draft]
  6. Randomized algorithms III: [MU] 7.1
  7. Parameterized algorithms: [KT] 10.1-4, [ftp-notes]
  8. Own notes
  9. McGregor and Mutukrishnan
  10. Shortest two disjoint paths in polynomial time by Andreas Björklund and Thore Husfeldt. ICALP 2014. [PDF]

 

Curriculum for 2013 (obsolete but interesting)

  1. Randomized algorithms I. Randomized contention resolution. Karger’s algorithm. Coupon collecting. Guessing cards. Event, probability, random variable, and expectation. Use of indicator random variables to compute expectation. [KT] 13.1-3
  2. Exponential time algorithms. Brute force. Branching. Divide-and-conquer. Ryser’s algorithm for bipartite matchings. Finding triangles via matrix multiplication; application to independent set. Dynamic programming over the subsets. [HU-draft]
  3. Approximation algorithms I. Set cover, vertex cover [KT] 11.3-4. PTAS for Knapsack 11.8.
  4. Randomized algorithms II. Quicksort. Randomized max 3-satisfiability. Markov chains. Schöning’s algorithm. [KT] 13.3-5, [MU] 7.1.
  5. Approximation algorithms II, Algebraic algorithms. Wigderson’s 3-colouring approximation. Maximum cut. Algebraic algorithms.
  6. Parameterized algorithms. FPT for Vertex Cover, greedy independent set on trees, weighted independent set on trees, circular arc colouring, tree decompositions [KT] 10.1-4, Bodlaender’s algorithm, colour coding [ftp-notes] 10.6.
  7. Streaming algorithms. [KT] sec 13.6. [MM] Andrew McGregor and S. Mutukrishnan, Data Stream Algorithms for Vectors, sec. 1.1.1, 1.2.1, 1.3.1. [B+] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan, section 2 in Counting distinct elements in a data stream, Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings. Lecture Notes in Computer Science 2483 Springer 2002, p. 1–10.
  8. Complexity of hard problems. Inapproximability [inap]. W[1]-hardness [FG06]. Exponential Time Hypothesis [ETH].
  9. Graph colouring. Chapter Graph Colouring Algorithms (2nd draft from 20 Sep 2013).

 

Lecture Plan (2012)

1. Introduction to randomized algorithms.

Mon 3 Sep 2012, 8–10.

Topics

Contention Resolution. Minimum Cut.

Materials

[KT] sec. 13.1–2

Secondary reading

[E] lecture 13. [MU] chapter 1 (in particular, 1.4). [RM] 1.1, 10.2, [H] 3.5.3, [Ka], [KS]

2. Introduction to approximation algorithms.

Wed 5 Sep 2012, 15–17.

Greedy Load balancing. FPTAS for Knapsack. Expectation, linearity, indicator random variables, coupon collecting. Randomized Max 3-Sat.

Materials

[KT] sec. 11.1, 11.8, 13.3–4.

3. Advanced approximation algorithms.

Mon 10 Sep 2012, 8–10.

Weighted Vertex Cover, Set Cover, Coloring 3-colorable Graphs, Max Cut.

Lecture Slides

aaai.pptx 

aaaii.pptx 

Materials

[KT] sec. 11.4, 12.4.

Secondary reading

Set Cover on wikipedia

Goemans Williamson's Max Cut algorithm on wikipedia (See example 3)

4. Exponential time algorithms.

Wed 12 Sep 2012, 15–17.

Decrease-and-conquer, dynamic programming, inclusion-exclusion, brute force

Materials

[Hu-draft], [Hu11]

Secondary reading

[Er] chap. 4. [Hr] chap 3.

5. Markov chains and random walks.

Mon 17 Sep 2012, 8–10.

Markov chains, Schöning’s algorithm, derandomization

Materials

[MU] Chapter 7.1, [Da+]

6. Parameterized algorithms.

Wed 19 Sep 2012, 13–15.

FPT. Vertex cover. Independent set on trees. Tree decompositions. Colour coding.

Lecture Slides

tw&k-path

Materials

[KT] sec 10.1-4, [fpt-draft]

Secondary reading

Tree decompositions on wikipedia

7. Streaming algorithms.

Mon 24 Sep 2012, 8–10.

(lecture by Rasmus Pagh, ITU Copenhagen)

Materials

  • [KT] sec 13.6
  • [MM] Andrew McGregor and S. Mutukrishnan, Data Stream Algorithms for Vectors: Draft Chapter, 3 Oct. 2012. (handed out).
  • Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan, Counting distinct elements in a data stream, Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings. Lecture Notes in Computer Science 2483 Springer 2002, p. 1–10.

8. Algebraic algorithms.

Mon 1 Oct 2012, 8–10.

Strassen's matrix multiplication, Freivald's fingerprinting, Tutte-Edmunds-Lovász perfect matching algorithm.

Lecture Slides

algalg.pptx

Materials

[KT] sec 5.6

[S11a,S11b]

9. Computational complexity of hard problems.

Mon 8 Oct 2012, 8–10.

Approximation complexity. W[1]-hardness. Exponential Time Hypothesis

[FG06] chapter 1.1-1.4

10. Current research, leftovers

Mon 15 Oct 2012, 8–10.  

Algorithm for motif detection. Selection. Quicksort.

Materials

[KT] sec 13.5

[BKK]