Course syllabus

Jump to today
TIN093/DIT093, Period 1, 2024: Algorithms

Instructors

  • Birgit Grohe, birgit.grohe(at)cse.gu.se, EDIT 5483 (examiner in period 1).
  • Peter Damaschke, ptr(at)chalmers.se, EDIT 5480 (examiner in period 3).
  • For all of us: Always use email, no Canvas messages please!

Assistants

Email: add "(at)chalmers.se"

  • Hanna Ek, hanna.ek, EDIT 6447
  • Alexander Gower, gower, EDIT 5121A
  • Ahmet Zahid Balcioglu, ahmet.balcioglu
  • Markus Pettersson, markus.pettersson
  • Ivan Oleinikov, ivanol
  • Andrzej Bruksman Rzeczycki, andrze@student.chalmers.se  

Student Representatives

  • Wenqi Zhang (MPALG) wenqiz(at)chalmers.se
  • Bastien Corgnac (MPALG/exchange) corgnac(at)student.chalmers.se
  • Victor Wellsmo (MPCAS) vicwel(at)student.chalmers.se
  • Chiara Cesarini (MPALG) chiarace(at)student.chalmers.se
  • Janna Leong Yia Ji (GU exchange) gusleoji(at)student.gu.se
  • Daniel Nikolaev (GU single subject) gusnikoda(at)student.gu.se

Announcements

  • The course starts on Wednesday 4/9 at 10:00 with the first lecture in room HB3. Welcome!
  • Watch a greeting from the examiner: welcome video, and slides.

  • The exam has been graded and the results have been reported to ladok. The exam papers are available at the CSE student office. If you wish to discuss your exam paper with the examiner (exam review/tentagransking), you can email to the examiner birgit.grohe(at)cse.gu.se and arrange a time during the last week of November or the first week of December.

    Exam paper with solutions pdf

Teaching & Scheduled Activities

Link to Timeedit

Scheduled activities: Most weeks consist of two lectures and several exercise sessions.

Lectures: Mondays and Wednesdays 10-12

Exercise sessions: Wednesdays 13-15 and 15-17 (start week 2)

Read more about the exercise sessions in the course material module.

Schedule irregularities may occur, for details please see the schedule in timeedit. In addition to the lectures and exercise sessions, we will offer consultation hours two times a week, where students can ask questions about the Assignments, exercises from the book or the course material in general,  usually:

Consultation hours: Thursday 15-16 and Friday 15-16 in room 5483 (start week 2)

If you have questions about the course structure or material, you are welcome to contact the examiner Birgit Grohe by email. If the questions are content specific, you may contact the teacher who gave the lectures about the topic (Birgit or Peter).

At the end of each week, an Assignment is due (for details scoll down to section Assignments). 

Course Material and Literature

Information about the course book, download of lecture notes, info about recommended book exercises and the content of the exercise sessions: course material module.

Outline of course topics per lecture (the exact order may change during the course):

  • Lecture 1. General notions: problem, instance, algorithm. Time complexity and O-notation
  • Lecture 2. Greedy algorithms. Interval Scheduling
  • Lecture 3. Dynamic programming. Weighted Interval Scheduling
  • Lecture 4. Dynamic programming for: Subset Sum, Knapsack. Sequence Alignment
  • Lecture 5. Segmentation problems, Dynamic programming summary. Divide-and conquer. Binary search. Skyline problem.
  • Lecture 6. Skyline problem, Recurrences. Briefly about Sorting.
  • Lecture 7. Lower bound comparison based sorting. Counting Inversions. Fast Multiplication.  
  • Lecture 8: Median Finding, Closest points.
  • Lecture 9. Graph traversal and Connectivity. Coloring and Bipartiteness.
  • Lecture 10. Minimum Spanning Tree. Directed cycles and Topological Order, DAGs.
  • Lecture 11. Polynomial-time reductions. Complexity classes P and NP. NP-completeness. Satisfiability problem.
  • Lecture 12. Several NP-complete problems.
  • Lecture 13. Shortest and longest paths in DAGs and general graphs.  Interval Partitioning. Space-efficient sequence alignment.
  • Lecture 14. Space-efficient sequence alignment. Union-and-Find.
  • Lecture 15: Clustering with maximum spacing. And guest lecture by Esther Galby (parameterized complexity and graph problems)

Brief Course Description

Make sure to also read the course syllabi in the Student portals: Syllabus TIN093 (Chalmers). Syllabus DIT093 (GU). We would like to emphasize that this is a course on advanced level and that we assume that you are familiar with the prerequisites listed in the respective course plan, in particular data structures and discrete mathematics.

The course provides basic knowledge and methods for the design and analysis of fast and correct algorithms that solve new problems. The intuitive notion of time complexity is applied in a strict sense. After completion of this course, you should be able to:

  • describe algorithms in writing, prove that they are correct and fast,
  • recognize non-trivial computational problems in real-world applications and formalize them,
  • recognize computationally intractable problems,
  • apply the main design techniques for efficient algorithms to problems which are similar to the course examples but new,
  • perform the whole development cycle of algorithms: problem analysis, choosing, modifying and combining suitable techniques and data structures, analysis of correctness and complexity, filling in implementation details, looking for possible improvements, etc.,
  • perform simple reductions between problems,
  • explain on a technical level what NP completeness means,
  • critically assess algorithmic ideas,
  • explain why time efficiency and correctness proofs are crucial.

This is not a course in programming! The main focus is on the analytical work that has to be done before writing any line of code. Accordingly, the implementation of algorithms is NOT practiced here.

Grades are based on the points in the written exam. Point limits for the grades 3, 4, 5 will be announced.

Assignments

"Tell me and I forget. Show me and I remember. Let me do and I understand." (attributed to Confucius)

The assignments are not compulsory, but very highly recommended. Since the exam is done individually, so is the submission of the assignments. If you feel it helps your learning, you can discuss the assignments with a classmate, but make sure you write up the solution yourself. It is ok to submit partial solutions. you will get feedback on the parts you submitted and the possibility to submit an improved version.

The Assignment content will appear below every Monday.

Computational problems in practice rarely occur in nice textbook form. We must be able to apply general algorithm design techniques to new problems, or at least adapt and adjust known algorithms to new variants of known problems. Therefore this course is problem-oriented and the exam will require problem solving, too.

Moreover, one cannot learn these skills just by listening, or by reading a lot of solutions written by others. (Compare to other skills: One cannot learn to play a musical instrument just be watching others playing. Of course, one has to practice!) It is important to invest own work and actively solve problems. The course offers possibilities for that, mainly by doing assignments.

While the assignments are voluntary, it is strongly recommended to work on them as much as you can. Then you will be in a much better position in the exam, but we also hope that you work on them because you find them interesting as such. The assignments are not part of the examination of this course, neither directly as credits nor as bonus points. That allows you to discuss your thoughts with other students before you write up and submit your solution in Fire.

Written solutions to assignments:
Most importantly, train your ability to communicate solutions in written form. Even when you have solved an exercise and the solution seems clear to you, comprehensible writing remains a challenge. Moreover, in the exam you must do it - and you want the graders to understand your solutions. We advise you to submit written solutions to the assignments, as many as you can. The deadline is usually Sunday 23:59. (Of course, you may submit earlier.) All assignments shall be done individually. Discussion is encouraged, but what you submit should be written in your own words and reflect your own understanding. We will use the FIRE system for submission (not Canvas Assignments). Instructions and link will follow during the first week of the course.

The level of assignments and exercises may sometimes be higher than the level of typical exam problems. This is quite intended, because during the course you have more time and leisure for practicing more challenging and fun problems, and after all, one learns for the profession, not only for the next exam.

Where to submit the weekly assignment: Read the SUBMISSION INSTRUCTIONS page.

Exam: see Module Exam

 

Course summary:

Date Details Due