lunduniversity.lu.se

Computer Science

Faculty of Engineering, LTH

Denna sida på svenska This page in English

Materials

Materials

Books

  • [FG06] Flum and Grohe, Parameterized Complexity Theory, Springer 2006. Chapter 1 online.
  • [Hr] Hromkovic, Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics , 2nd edition, Springer (2010)
  • [KT] Jon Kleinberg and Éva Tardos, Algorithm Design, Addison Wesley; 1st edition, 2005. Kevin Wayne’s slides for this book: www.cs.princeton.edu/~wayne/kleinberg-tardos/
  • [MM] Andrew Mc-Gregor and S. Muthukrishnan, Data Stream Algorithms and Sketches. Draft at http://people.cs.umass.edu/∼mcgregor/book/book.html. Password is on Thore Husfeldt’s office door. Do not distribute without permission of the authors.
  • [MR] Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
  • [MU] Mitzenmacher and Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press (2005)

Lecture notes

Papers

  • [BKK] Björklund, Kaski, Kowalik, Probably optimal graph motifs, arxiv:1209.1082.
  • [Ka] David R. Karger: Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) 1993: 21-30
  • [KS] David R. Karger, Clifford Stein: An O~(n2) algorithm for minimum cuts. STOC 1993: 757-765
  • [Hu11] Thore Husfeldt Invitation to Algorithmic Uses of Inclusion-Exclusion, Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Zürich, Switzerland, July 4-8, 2011, Part II, Springer LNCS 6756, 2011, pages 42-59. arxiv.org/abs/1105.2942
  • [Da+] Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning: A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search. Theor. Comput. Sci. 289(1): 69-83 (2002)[PDF]

Syllabus

  • [KT]: 10.1–10.4, 11.1, 11.4, 11.8, 12.4, 13.1-6
  • [HU-draft], [fpt-draft], [inap]
  • [HU11] sections 1-7
  • [MU] Chapter 7.1
  • [S11a] 1.2, [S11b]
  • [MM] section 0, 1.1–2, 2.1, 3.1
  • [FG06] chapter 1.1–1.4

Exams