186.814 Algorithmics
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2023W, VU, 4.0h, 6.0EC
TUWELLectureTube

Properties

  • Semester hours: 4.0
  • Credits: 6.0
  • Type: VU Lecture and Exercise
  • LectureTube course
  • Format: Hybrid

Learning outcomes

After successful completion of the course, students are able to use advanced techniques to design efficient algorithms for the solution of computational problems. Furthermore, the students can justify the correctness of their algorithmic solutions and can determine their efficiency by theoretical methods.

Subject of course

This module covers advanced algorithms and data structures and algorithm analysis. It has an emphasis on (but is not limited to) algorithms on graphs and methods for problem solving and optimization. The module consists of a lecture together with exercises.

Topics covered:

  • Network flows and matchings
  • Planarity of graphs
  • A* algorithm
  • Randomized algorithms
  • Linear and (mixed) integer linear programming
  • Parameterized algorithms and kernelization
  • Graph decompositions and treewidth
  • Geometric Algorithms

Teaching methods

Introduction and explanation of general methods, discussion of examples, justification by giving formal arguments and proofs, independent problem solving, presentation and discussion of solutions.

Mode of examination

Immanent

Additional information

Organization

The course is divided by topics into six blocks, each consisting of three lectures and one exercise.

The final grade will be based on the exercises and on the final exam. There are six mandatory units of exercises.

All lectures, exercises, and exams are held in presence, but lectures are also recorded and provided online.

The first lecture takes place on Monday, October 2, 9:15-10:45 in EI5. It includes a presentation of the course organization. 

Exercises

They will take place on Thursday 19.10., 9.11., 23.11., 30.11., 14.12., and 21.12., each day in several groups at different times.
You will receive instructions a few weeks before these units and are expected to submit your solutions in advance and also to be able to present your solutions in the exercises.
You have to register to one of the groups in TISS and attendance to the exercise sessions of your particular group is compulsory.
Exercise sheets will be available for download.

Final Exam

The final written exam takes place on January 25, 2024, 10:00-13:00. An additional exam opportunity will be on March 15, 2024, 16:00-19:00.
If you do both exams, then the better result counts.

Grading

The mark you receive depends on this final exam (40%) and your performance at the blackboard exercises (60%).
Blackboard exercises will influence your grade via two different measures:

  • the total number of exercises you indicate to have accomplished and submitted before the deadlines (40%),
  • your presentations of exercises at the blackboard (20%);

The minimal requirements for a positive grade are:

  • >=37% of all blackboard examples marked and successfully submitted in TUWEL (both) before the deadlines as well as at least 3 exercises per exercise sheet from at least 5 of the 6 exercise blocks
  • >=50% on average on your blackboard presentations
  • >=40% on at least one of the two written exams

To obtain full points for the exercises it is sufficient to mark and submit >=75% of all blackboard examples  in addition to getting all points on your presentations.

Overall grade distribution:
S1: [88%,100%]
U2: [75%,88%)
B3: [63%,75%)
G4: [50%,63%)
N5: [0%,50%)

As an additional exception, you can also get the positive grade G4 in case you cannot attend both of the exams but have marked >= 90% of all blackboard examples and have >=50% on average on your blackboard presentations. We remark that this rule is only intended for exceptional cases and strongly encourage you to do at least one of the exams.

Note: Once you attended at or submitted your solutions for at least one blackboard exercise session you will in any case receive a grade at the end of the term.

Course material

The lecture slides will be available in TUWEL.

Estimated effort

Hours   Activity
       32   Lecture
       65   Preparation of exercises
         6   Exercise groups
       45   Exam preparation
         2   Written exam
================
     150   Overall 

Please send general and organisational questions to algorithmics@ac.tuwien.ac.at.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Mon09:00 - 11:0002.10.2023 - 11.12.2023EI 5 Hochenegg HS Lecture
Wed09:00 - 11:0004.10.2023 - 06.12.2023EI 5 Hochenegg HS Lecture
Thu10:00 - 13:0019.10.2023 - 14.12.2023Seminarraum FAV 01 A (Seminarraum 183/2) Exercises
Thu14:00 - 18:0019.10.2023 - 14.12.2023Seminarraum FAV EG C (Seminarraum Gödel) Exercises
Thu10:00 - 13:0011.01.2024Seminarraum FAV 01 A (Seminarraum 183/2) Exercise
Thu14:00 - 18:0011.01.2024Seminarraum FAV EG C (Seminarraum Gödel) Exercise
Mon09:00 - 10:0022.01.2024EI 5 Hochenegg HS Algorithmics Q&A
Algorithmics - Single appointments
DayDateTimeLocationDescription
Mon02.10.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Wed04.10.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Mon09.10.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Wed11.10.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Mon16.10.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Wed18.10.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Thu19.10.202310:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Exercises
Thu19.10.202314:00 - 18:00Seminarraum FAV EG C (Seminarraum Gödel) Exercises
Wed25.10.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Mon30.10.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Mon06.11.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Wed08.11.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Thu09.11.202310:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Exercises
Thu09.11.202314:00 - 18:00Seminarraum FAV EG C (Seminarraum Gödel) Exercises
Mon13.11.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Thu16.11.202310:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Exercises
Thu16.11.202314:00 - 18:00Seminarraum FAV EG C (Seminarraum Gödel) Exercises
Mon20.11.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Wed22.11.202309:00 - 11:00EI 5 Hochenegg HS Lecture
Thu23.11.202310:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Exercises

Examination modalities

Submission of solutions of examples, presentation of independent solutions in exercise classes, solving exam questions in written tests.

Group dates

GroupDayTimeDateLocationDescription
Exercise Group 1Thu10:00 - 11:0019.10.2023 - 21.12.2023Seminarraum FAV 01 A (Seminarraum 183/2) 186.814 Algorithmics Exercise Group 1
Exercise Group 2Thu11:00 - 12:0019.10.2023 - 21.12.2023Seminarraum FAV 01 A (Seminarraum 183/2) 186.814 Algorithmics Exercise Group 2
Exercise Group 3Thu12:00 - 13:0019.10.2023 - 21.12.2023Seminarraum FAV 01 A (Seminarraum 183/2) 186.814 Algorithmics Exercise Group 3
Exercise Group 4Thu14:00 - 15:0019.10.2023 - 21.12.2023Seminarraum FAV EG C (Seminarraum Gödel) 186.814 Algorithmics Exercise Group 4
Exercise Group 5Thu15:00 - 16:0019.10.2023 - 21.12.2023Seminarraum FAV EG C (Seminarraum Gödel) 186.814 Algorithmics Exercise Group 5
Exercise Group 6Thu16:00 - 17:0019.10.2023 - 21.12.2023Seminarraum FAV EG C (Seminarraum Gödel) 186.814 Algorithmics Exercise Group 6
Exercise Group 7Thu17:00 - 18:0019.10.2023 - 21.12.2023Seminarraum FAV EG C (Seminarraum Gödel) 186.814 Algorithmics Exercise Group 7

Course registration

Begin End Deregistration end
05.09.2023 00:00 16.10.2023 23:59

Group Registration

GroupRegistration FromTo
Exercise Group 110.10.2023 09:0018.10.2023 18:00
Exercise Group 210.10.2023 09:0018.10.2023 18:00
Exercise Group 310.10.2023 09:0018.10.2023 18:00
Exercise Group 410.10.2023 09:0018.10.2023 18:00
Exercise Group 510.10.2023 09:0018.10.2023 18:00
Exercise Group 610.10.2023 09:0018.10.2023 18:00
Exercise Group 710.10.2023 09:0018.10.2023 18:00

Curricula

Literature

Slides and relevant articles will be made available for download.

Previous knowledge

A good understanding of basic algorithms and data structures and methods to analyze them.

Preceding courses

Continuative courses

Language

English