Address

Jakob-Haringer-Str. 2

5020 Salzburg, Austria


Room 2.17


Phone

+43 (0)662 8044 6417

+43 (0)662 8044 611 (fax)


Skype ana_sokolova

Home

Papers

Talks

Teaching

Personal

Many thanks to Silviu Craciunas for the photo (RTAS 2010 in Stockholm) and his help with iWeb!

Formale Languages and Complexity Theory 511.023 (instructions)
Winter semester 2016/2017

Schedule:            Tuesdays 1pm-2pm starting 11.10.16 in T01 (my group)

                           Wednesdays 2pm-3pm starting 12.10.16 in T03

                           (group of Sebastian Arming)


First meeting:       Tuesday 11.10.16 at 1pm / Wednesday 12.10.16


Language:           Teaching in English, course material (mainly) in German

Prerequisites:  The course is self-contained, but knowledge of basics of theoretical computer science is expected.

Rules:   Presence in class is obligatory. Each student can miss one class, but not more than that without a serious reason.


Each week after the lecture (Tuesdays evening) the students are given a set of several homework exercises that are to be solved in groups of at most three people, signed, and delivered to the lecturer for the corresponding group before the following Tuesday 9 am.  These exercises are to be discussed during class on that same Tuesday/Wednesday. We will correct one randomly chosen exercise per week and the students will get a grade for that one. The corrected homework will be returned to the students with grades the same week. Needless to say, copying between different groups is unacceptable and will be sanctioned.  


During class we will present the solution of the chosen corrected exercise and the students will be asked to present the solutions/discuss the other exercises. We may also present additional solutions.


Grading: The grade of a student is determined by: (1) his/her grades of corrected homeworks, and (2) activity (ability to present solutions of exercises) in class. Hence, this is a course with permanent evaluation, there will be no exam.

Tasks per week:


  1. •Week2, Tuesday 11.10.16/Wednesday 12.10.16. The solutions are to be handed in before Tuesday 11.10.16, 9am. You will get the feedback on the corrected task in class.

  2. •Week3, Tuesday 18.10.16/Wednesday 19.10.16. The solutions are to be handed in before Tuesday 18.10.16, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  3. •Week4, Tuesday 25.10.16/Wednesday 26.10.16. The solutions are to be handed in before Tuesday 25.10.16, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  4. •In Week5 (Tuesday 1.11.16/Wednesday 2.11.16) there is no class due to public holiday.

  5. •Week6, Tuesday 8.11.16/Wednesday 9.11.16. The solutions are to be handed in before Tuesday 8.11.16, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  6. •Week7, Tuesday 15.11.16/Wednesday 16.11.16. The solutions are to be handed in before Tuesday 15.11.16, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  7. •Week8, Tuesday 22.11.16/Wednesday 23.11.16. The solutions are to be handed in before Tuesday 22.11.16, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  8. •Week9, Tuesday 29.11.16/Wednesday 30.11.16. The solutions are to be handed in before Tuesday 29.11.16, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  9. •Week10, Tuesday 6.12.16/Wednesday 7.12.16. The solutions are to be handed in before Tuesday 6.12.16, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  10. •Week11, Tuesday 13.12.16/Wednesday 14.12.16. The solutions are to be handed in before Tuesday 13.12.16, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  11. •Week12, Tuesday 20.12.16/Wednesday 21.12.16. The solutions are to be handed in before Tuesday 20.12.16, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  12. •Week13, Tuesday 17.1.17/Wednesday 18.1.17. The solutions are to be handed in before Tuesday 17.1.17, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  13. •Week14, Tuesday 24.1.17/Wednesday 25.1.17. The solutions are to be handed in before Tuesday 24.1.17, 11am via the online system fl.cosy.sbg.ac.at. You will get the feedback on the corrected task in class.

  14. •Extra class on Friday 27.1.17 (3pm-4pm in T02) -- no HW for this class, we constructed and discussed further PDA and DPDA examples.

Course description:  These are the instructions accompanying the lectures Formal Languages and Complexity Theory 2016. Each week the students are given a set of few excercises to solve which we then discuss in class. 

Literature:


  1. •Textbook: Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Pearson/Addison-Wesley, 2007.

  2. •Textbook: Introduction to the Theory of Computation, by Michael Sipser, Cengage, 2005.


The books can be ordered via Amazon.de . Some copies are available at the department library.


I will use the teaching materials of Prof. Robert Elsaesser (on sabbatical this semester), with small changes, and make them available via http://fl.cosy.sbg.ac.at

Ana Sokolova

Dr. TU Eindhoven, The Netherlands, 2005


Associate Professor


Computational Systems Group

Department of Computer Sciences

University of Salzburg

Austria


anas@cs.uni-salzburg.at