Introduction to the Theory of Computing 2 (BMEVISZAA04)

2018 Spring semester


Lecturer:

Rita Csákány
E-mail: csakany_at_cs.bme.hu
Office: IB 137/a
Office hours: by arrangement

Classes:

Monday    10.15-12.00, IB138
Thursday 16.15-18.00, IB140


Requirements:
There will be one midterm during the semester, and two possibilities
to repeat it (one at the end of the semester, and one in the repeat
week).
To obtain a signature, you have to reach at least 40% on the midterm.
The final grade is based 30% on the midterm, 10% on an exercise (from the material not included in the midterm) in the exam and 60% on the oral exam.


Midterms:
April 23, Monday, 17-19 pm.
First repeat: May 14, Monday, 17-19 pm.


Syllabus

Topics:

  • Planar Graphs
  • Euler and Hamilton
  • Colorings
  • Matchings
  • Network Flows
  • Higher Connectivity

  • Exercise sets and solutions:

  • Exercise-set 1. , Solutions
  • Exercise-set 2. , Solutions
  • Exercise-set 3. , Solutions
  • Exercise-set 4. , Solutions
  • Exercise-set 5. , Solutions
  • Exercise-set 6. , Solutions
  • Exercise-set 7. , Solutions
  • Exercise-set 8. , Solutions
  • Exercise-set 9. , Solutions
  • Exercise-set 10. , Solutions
  • Exercise-set 11. , Solutions
  • Exercise-set 12. , Solutions
  • Exercise-set 13.

  • Online materials:

  • Graph Theory slides
  • R. Diestel: Graph Theory

  • Midterms from previous years:


    2017: first midterm, repeat, second repeat; second midterm, repeat, second repeat
    2016: first midterm, repeat, second repeat; second midterm, repeat, second repeat
    2015: first midterm, repeat, second repeat; second midterm, repeat, second repeat

    For the exam:

    List of questions
    List of exercises


    Consultations:

    June 1 Friday 2 pm. IB.134.
    June 6 Wednesday 2 pm. IB.134.
    June 13 Wednesday 2 pm. IE. 216.
    June 15 Friday 2 pm. IB.134.
    June 20 Wednesday 2 pm. IE. 216.
    June 22 Friday 2 pm. IB.134.