Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Home
 Contact
 Teaching
lectures
exercises
seminars
proseminars
research seminars
practical courses
WS 2020/21
SS 2020
WS 2019/20
SS 2019
WS 2018/19
SS 2018
WS 2017/18
SS 2017
WS 2016/17
SS 2016
WS 2015/2016
SS 2015
WS 2014/2015
SS 2014
WS 2013/2014
SS 2013
WS 2012/2013
SS 2012
WS 2011/2012
SS 2011
WS 2010/2011
SS 2010
WS 2009/2010
SS 2009
WS 2008/2009
SS 2008
WS 2007/2008
SS 2007
WS 2006/2007
SS 2006
WS 2005/2006
SS 2005
WS 2004/2005
SS 2004
Before 2004
 People
Publications
 Student Projects
Research
Tools
Heroes of Computer Science
 Help

































Complexity Theory 2010

  News | Dates | Grading | Content | Exercises | Exam | Material
  • August 4 Unfortunately, the definiton of maximal cliques in Exercise 4 of the exam was erroneous. It should simply have been defined as a largest clique wrt number of nodes in the clique to yield an exercise comparable to the one for maxIndset. For details, see the new sample solution.
    • part (a) was not affected and points remain the same
    • part (b) was solvable with either definition and people were awarded points if they solved it
    • parts (c) and (d) were incorrect with the wrong definition; hence everybody receives full score (3 points)
    The updated results can be found here.
  • August 03 A solution to the final exam can be found here[Updated 04.08.2010]
  • August 02
    • The preliminary results of the final exam can be found there: HERE[Updated 04.08.2010]
    • After the exam inspection on this Thursday (10:00 am, 03.09.014) the results will be published via TUMonline.
  • July 19
    • No lecture on July 20!
    • The exam is on August 2 starting at 9.30am. You have 120 minutes to work on it.
    • Please be in the lecture hall no later than 9.15am!
    • lecture hall: MW 2050
  • July 7
    • The number of bonus points rewarded for the questionnaires can be found here.

      Should you have any questions regarding the results, please feel free to ask us.

    • Everyone who has submitted an implementation of the QBF-IP-protocol has been rewarded an additional bonus point.

  • July 2 In Exercise 10.4(b) you need to adapt the algorithm from (a) such that it runs in time polynomial in n and the optimal value. You can do this by slight change to the data structures used in (a).
  • June 24 There was en error in Exercise 9.2(a): the time for calculating the probability should, of course, be polynomial in the length of the formula, not constant -- the latter makes only sense if the formulae are assumed to be of constant length.
  • June 15 Get an extra bonus point for the exam by implementing the interactive protocol to decide membership in QBF. Specification here.
  • June 2
    • The current results of the questionnaires are now online. You can access them via the exercise homepage.
    • No exercise today. Exercise sheet 6 is going to be discussed next week (09.02), exercise sheet 7 the week thereafter (16.02).
  • May 26 You can register for the exam at TUM online
  • May 26 Please come up with potential exam questions and put them in the envelope at the door of room 03.11.40!
  • No lecture on May 25!
  • April 30 There was an error in Ex.2.3(b). The language B must be non-trivial. Corrected version uploaded.
  • April 28 Updated content, material, uploaded slide sets 3 and 4.
  • April 21 Updated grading, content, material, uploaded slide sets 1 and 2.
  • April 20 First lecture at 8.30am, room 00.08.038.
  • February 9 Creation of this site.