191.126 Competitive Programming for Programming Contests
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2023S, VU, 2.0h, 3.0EC
TUWEL

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise
  • Format: Presence

Learning outcomes

After successful completion of the course, students are able to

  • analyze programming problems efficiently and in depth,
  • find and extract the required algorithmic patterns in the problems, and
  • apply efficient programming techniques to create correct and well performing solutions.

Subject of course

Introduction to Programming Contests in General

Detailed Analysis of the ACM ICPC Programming Contest

  • type of problems
  • problem formats (input and output)
  • understanding and using the Online Judge
  • current contests

Introduction to Commonly Needed Algorithms

  • graph algorithms (BFS, DFS, Single Source Shortest Path)
  • string matching algorithms
  • number systems, Big Integer Programming
  • sorting

 Programming Techniques

  • dynamic programming
  • backtracking
  • branch-and-bound
  • encodings

Selected Algorithms and Their Implementation

  • Dijkstra
  • Knuth-Morris-Pratt
  • Bellman-Ford
  • Kruskal’s Algorithm

Efficient Programming Techniques

  • avoid syscalls
  • write testable code
  • efficient use of datatypes (width, packing)
  • code inlining
  • loop unrolling
  • effizient data structures (hashes, adjacency lists vs. arrays, etc.)

In addition, the best teams will represent TU Wien at the “Central Europe Regional Contest” (CERC) of the ACM ICPC programming contest.

Teaching methods

  • Programming exercises
  • Solving problems of previous programming contests

Mode of examination

Immanent

Additional information

ECTS breakdown

lectures: 10h (5x2h)
exercises: 6h (3x2h)
assignments: 35h (3x15h)
exam preparation: 14h
total: 75h = 3 ECTS

Please see German page for more details.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Thu13:00 - 15:0009.03.2023FAV Hörsaal 2 Lecture
Thu13:00 - 15:0020.04.2023 - 29.06.2023EI 6 Eckert HS Lecture
Competitive Programming for Programming Contests - Single appointments
DayDateTimeLocationDescription
Thu09.03.202313:00 - 15:00FAV Hörsaal 2 Lecture
Thu20.04.202313:00 - 15:00EI 6 Eckert HS Lecture
Thu27.04.202313:00 - 15:00EI 6 Eckert HS Lecture
Thu04.05.202313:00 - 15:00EI 6 Eckert HS Lecture
Thu11.05.202313:00 - 15:00EI 6 Eckert HS Lecture
Thu25.05.202313:00 - 15:00EI 6 Eckert HS Lecture
Thu01.06.202313:00 - 15:00EI 6 Eckert HS Lecture
Thu15.06.202313:00 - 15:00EI 6 Eckert HS Lecture
Thu22.06.202313:00 - 15:00EI 6 Eckert HS Lecture
Thu29.06.202313:00 - 15:00EI 6 Eckert HS Lecture

Examination modalities

The students need to pass the exercise and the exam part of this course.

The exercise part consists of solving programming exercises in groups.

In the exam, the students will have to solve a programming problem on their own.

Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Thu14:00 - 16:0027.06.2024Seminarraum AE U1 - 7 assessed01.05.2024 00:00 - 25.06.2024 23:59TISSExam

Course registration

Begin End Deregistration end
31.01.2023 00:00 23.03.2023 23:59 31.03.2023 23:59

Registration modalities

The course is primarily targeted to students that are eligible for representing TU Wien at the ICPC. Thus, participants should have finished less than 8 semesters (strictly smaller than 8).

Curricula

Literature

No lecture notes are available.

Previous knowledge

The participaents are expected to have a certain knowledge of the following areas:

  • a good knowledge of at least one of the following programming languages: C/C++, Java, Python
  • operating systems
  • compilers
  • data structures
  • graph theory
  • Linux
  • basic algorithms (e.g., quicksort)

Language

English