Introduction to the Theory of Computing 2 (BMEVISZAA04)

2019 Spring semester


Lecturer:

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


Practice instructor:

Padmini Mukkamala
E-mail: padmini.mvs_at_gmail.com

Classes:

Lecture:       Monday, 10.15-12.00, IE 220
Practices:    Friday, 12.15-14.00, R508  and  Friday, 14.15-16.00, R508


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 40% on the midterm and 60% on the oral exam.


Midterms:
May 3, Friday, 8-10 am.
First repeat: May 20, Monday, 10-12 am, Q1
Second repeat: May 29, Wednesday, 10-12 am.

Syllabus

Topics:

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

  • Exercise sets and solutions:

  • Exercise-set 1. , HW: 7, 8, 13, 17, 18, Solutions
  • Exercise-set 2. , HW: 2, 3, 10, 11, 16, 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.
  • Exercise-set 13.

  • Online materials:

  • Graph Theory slides
  • R. Diestel: Graph Theory

  • Midterms from previous years:

    2018: midterm, repeat, second repeat
    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