Course syllabus

TIN093/DIT602, Period 1, 2021: Algorithms

Instructors

  • Birgit Grohe, birgit.grohe(at)cse.gu.se, EDIT 5483 (examiner in period 3).
  • Peter Damaschke, ptr(at)chalmers.se, EDIT 5480 (examiner in period 1).

Assistants

Email: add "(at)chalmers.se", unless said otherwise.

  • Amir Keramatian (amirke)
  • Emil Carlsson (caremil)
  • Ivan Oleinikov (ivanol)
  • Jeremy Pope (popje)
  • Yu Zheng (zhyu)

Student Representatives

  • to be announced

Announcements

  • empty

Exam Aids

Basically everything, in the case of a home exam. Information about the exam form will be given as early as possible.

The re-exam will be in March 2022, and it is identical to the regular exam of the course edition in period 3, 2022.

Some old exams: 2020 2020 (Aug.) 2019 2018 2017 2016 2015


Teaching

The plan is that Birgit will teach the first half and Peter the second half.

The methods (forms of lecturing and oral exercises, amount of self-study) depend on the pandemic situation. We will give announcements in good time.


Lecture Notes

Numbers indicate the related book sections. (Note: Chapters have different numbers in some editions of the book, in particular, chapters 4 and 5 are swapped. But it should be easy to recognize this and find the correct chapters by their titles anyway.) Sections with the label "Problem" describe the computational problems treated in the course; do not misunderstand them as exercises. <>pThe remaining schedule is always preliminary, and Lecture Notes will be added before or during the course.

  • Lecture 1. General notions: problem, instance, algorithm. Time complexity and O-notation (2.1, 2.2, 2.4).
  • Lecture 2. Greedy algorithms. Interval Scheduling (4.1).
  • Lecture 3. Dynamic programming. Weighted Interval Scheduling (6.1, 6.2).
  • Lecture 4. Dynamic programming for: Subset Sum and Knapsack (6.4). Segmentation problems (6.3).
  • Lecture 5. Dynamic programming for Sequence Alignment (6.6). Divide-and conquer. Binary search (end of 2.4). Skyline problem.
  • Lecture 6. Recurrences (5.1-5.2). Briefly about Sorting and Median Finding (5.1, 13.5).
  • Lecture 7. Counting Inversions (5.3). Fast Multiplication (5.5). Polynomial-time reductions (8.1).
  • Lecture 8. Complexity classes P and NP (8.3). NP-completeness (8.4). Satisfiability problem (8.2).
  • Lecture 9. Several NP-complete problems (from 8.5-8.7, very cursory).
  • Lecture 10. Graph traversal and Connectivity (3.2, 3.5). Coloring and Bipartiteness (3.4).
  • Lecture 11. Minimum Spanning Tree (4.5). Directed cycles and Topological Order, DAGs (3.6).
  • Lecture 12. Shortest and longest paths in DAGs and general graphs. Union-and-Find (4.6). Interval Partitioning (end of 4.1). Space-efficient Sequence Alignment (6.7).
  • Lecture 13. Closest points (5.4). Clustering with maximum spacing (4.7).

Assignments

  • Will be added here.

Recommended Book Exercises

Here we list some particularly recommended exercises from the book, for those who want to practice a bit more on their own. You are also welcome to send questions about them.

  • Greedy (chapter 4): 3 (loading trucks), 4 (subsequence), 5 (base stations on a road), 7 (assign jobs to computers), 13 (minimize the sum of weighted completion times), 17 (circular Interval Scheduling)
  • Dynamic programming (chapter 6): 2b (low and high stress), 4c (business in two cities), 6 (pretty printing), 17 (rising trend)
  • Searching and divide-and-conquer (chapter 5): 1 (median of two sets), 2 (significant inversions), 3 (equivalent majority), 5 (hidden surface removal)
  • Reductions and NP-completeness (chapter 8): 1 (reducible or not), 2 (diversity), 3 (qualified counselors), 5 (hitting set), 6 (monotone SAT), 14 (multiple interval scheduling)
  • DAGs (chapter 3): 3 (order or cycle), 12 (consistent historical data)
  • Proving some graph properties (chapter 3): 5 (number of nodes in a tree), 7 (high degree implies connectivity),

Times

See TimeEdit.


Literature

The course follows selected parts of the textbook
Jon Kleinberg, Eva Tardos: Algorithm Design. Pearson/Addison-Wesley 2006, ISBN 0-321-29535-8.


Brief Course Description

See also the syllabus in the Student Portal.

The course provides basic knowledge and methods for the design and analysis of fast and correct algorithms that solve new problems with the use of computers. 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 and G, VG will be announced there.


About the Assignments

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

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.

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 always Sunday 23:59. (Of course, you may submit earlier.) All assignments shall be done individually. Discussion is encouraged, but what you submit must be written in your own words and reflect your own understanding. Submission details: We use the Assignments feature in Canvas..

The level of assignments and exercies may 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.

 

Course summary:

Date Details Due