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.

2021W, VU, 4.0h, 6.0EC
Lecture TubeTUWEL

Properties

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

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.

Due to Covid-19, all lectures will either take place via live Zoom video meetings (where you also have the possibility to ask questions via chat) and/or provided as video streams.

The first live session takes place on October 4, 15:15-16:45, and is accessible via 

https://tuwien.zoom.us/j/9548931682 UPDATED!

After a brief presentation of the course organization, the first lecture will be given. 

Exercises

They will take place on Thursday 21.10., 28.10., 18.11., 2.12., 9.12., and 13.1., 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 at the blackboard.
You have to register to one of the six groups in TISS and attendance to the exercise lessons of your particular group is compulsory.
Exercise sheets will be available for download.

The exercises take place via Zoom video meetings. It is your responsibility to have a stable internet connection and the necessary hardware (PC/laptop with webcam) available to participate. Video must always be switched on during the exercises.

Final Exam

The final written exam takes place on January 28, 2021, 16:00-19:00 at rooms of TU Wien if the Covid situation will allow it or otherwise at the same time online via Zoom. An additional exam opportunity will be in March, 2021.
At least one exam has to be taken, if both are done then only the best result counts, and only one certificate will be issued.

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

To obtain full points for the exercises it is sufficient to mark and submit >=75% of all blackboards examples.

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

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
Mon15:00 - 17:0004.10.2021 - 13.12.2021 ZoomLecture
Wed09:00 - 11:0006.10.2021 - 15.12.2021 ZoomLecture
Thu09:30 - 16:3021.10.2021 - 13.01.2022 via Zoom (LIVE)Exercise Groups 1-6 (refer to the groups for exact times)
Wed09:00 - 10:0026.01.2022 Zoom (LIVE)Algorithmics Question Time
Algorithmics - Single appointments
DayDateTimeLocationDescription
Mon04.10.202115:00 - 17:00 ZoomLecture
Wed06.10.202109:00 - 11:00 ZoomLecture
Mon11.10.202115:00 - 17:00 ZoomLecture
Wed13.10.202109:00 - 11:00 ZoomLecture
Mon18.10.202115:00 - 17:00 ZoomLecture
Wed20.10.202109:00 - 11:00 ZoomLecture
Thu21.10.202109:30 - 16:30 via ZoomExercise Groups 1-6 (refer to the groups for exact times)
Wed27.10.202109:00 - 11:00 ZoomLecture
Thu28.10.202109:30 - 16:30 via ZoomExercise Groups 1-6 (refer to the groups for exact times)
Wed03.11.202109:00 - 11:00 ZoomLecture
Mon08.11.202115:00 - 17:00 ZoomLecture
Wed10.11.202109:00 - 11:00 ZoomLecture
Wed17.11.202109:00 - 11:00 ZoomLecture
Thu18.11.202109:30 - 16:30 via ZoomExercise Groups 1-6 (refer to the groups for exact times)
Mon22.11.202115:00 - 17:00 ZoomLecture
Wed24.11.202109:00 - 11:00 ZoomLecture
Mon29.11.202115:00 - 17:00 ZoomLecture
Wed01.12.202109:00 - 11:00 ZoomLecture
Thu02.12.202109:30 - 16:30 via ZoomExercise Groups 1-6 (refer to the groups for exact times)
Mon06.12.202115:00 - 17:00 ZoomLecture

Examination modalities

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

Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Fri16:00 - 19:0028.01.2022EI 3 Sahulka HS - RPL written01.10.2021 00:00 - 27.01.2022 15:00TISSVorlesungsprüfung
Fri16:00 - 19:0028.01.2022EI 3A Hörsaal written01.10.2021 00:00 - 27.01.2022 15:00TISSVorlesungsprüfung

Group dates

GroupDayTimeDateLocationDescription
Exercise Group 1Thu10:00 - 11:0021.10.2021 - 13.01.2022 Zoom186.814 Algorithmics Exercise Group 1
Exercise Group 2Thu11:00 - 12:0021.10.2021 - 13.01.2022 Zoom186.814 Algorithmics Exercise Group 2
Exercise Group 3Thu12:00 - 13:0021.10.2021 - 13.01.2022 Zoom186.814 Algorithmics Exercise Group 3
Exercise Group 4Thu14:00 - 15:0021.10.2021 - 13.01.2022 Zoom186.814 Algorithmics Exercise Group 4
Exercise Group 5Wed15:00 - 16:0020.10.2021 - 12.01.2022 Zoom186.814 Algorithmics Exercise Group 5
Exercise Group 6Thu16:00 - 17:0021.10.2021 - 13.01.2022 Zoom186.814 Algorithmics Exercise Group 6
Exercise Group 7Thu17:00 - 18:0021.10.2021 - 13.01.2022 Zoom186.814 Algorithmics Exercise Group 7

Course registration

Begin End Deregistration end
21.09.2021 00:00 11.10.2021 23:59

Group Registration

GroupRegistration FromTo
Exercise Group 112.10.2021 09:0017.10.2021 23:59
Exercise Group 212.10.2021 09:0017.10.2021 23:59
Exercise Group 312.10.2021 09:0017.10.2021 23:59
Exercise Group 412.10.2021 09:0017.10.2021 23:59
Exercise Group 512.10.2021 09:0017.10.2021 23:59
Exercise Group 612.10.2021 09:0017.10.2021 23:59
Exercise Group 712.10.2021 09:0017.10.2021 23:59

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