Course syllabus

Jump to today
TIN093/DIT093, Period 1, 2022: 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).
  • Jonah Brown-Cohen, jonahb(at)chalmers.se (guest lecturer, topic NP-completeness)
  • For all of us: Always use email, no Canvas messages please!

Assistants

Email: add "(at)chalmers.se"

  • Yu Zheng, zhyu
  • Jeremy Pope, popje
  • Markus Pettersson, markus.pettersson
  • Ivan Oleinikov, ivanol
  • Emil Carlsson, caremil
  • Emil Holmberg, hoemil
  • Sanna Persson, pesanna

Student Representatives

  • Emmie Berger (GU) gusberemcg@student.gu.se
  • Oscar Birging (MPCAS)  oscarbi@student.chalmers.se 
  • Huitong Gao (MPALG) huitong@student.chalmers.se
  • Yijie Ren  (MPCAS) yijier@student.chalmers.se
  • Sebastian Selander  (GU) gusselase@student.gu.se

Announcements

Exam review (for the March 2023 exam): Wednesday, 5 April, 11:00-13:00 in room EDIT 5128.

  • Reading week 8: No lecture on Monday, last lecture on Wednesday. No exercise session on Monday, two exercise sessions (as usual) on Wednesday. Consultation hours as usual.
  • Reading week 7: No lecture on Monday, lecture on Wednesday as usual on campus. Exercise session on Monday over zoom, zoom link TBA, the sessions on Wednesday as usual on campus.
  • The lectures next week (3/10 and 5/10) are at the usual times, but online instead of in the classroom. You need to be logged in with your student account to be able to access the zoom room. Zoom link for Monday at 8.00 https://chalmers.zoom.us/j/64728235744 (passcode 093093), zoom link for Wednesday at 10.00 https://chalmers.zoom.us/j/61465425994 (passcode 093093)
  • The first lecture is on Wednesday 31/8 at 10:00 with the first lecture in room SB-H2. Welcome!
  • Link to Timeedit

Teaching & Scheduled Activities

Scheduled activities: Most weeks consist of two lectures and three exercise sessions. Schedule irregularities may occur, for details please see the schedule in timeedit below. At the end of each week, an Assignment is due. In addition to the lectures and exercise sessions, we will offer consultation hours two times a week (Thursday 15-16 and Friday 10-11).

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, Peter or Jonah).

Times

Link to Timeedit

Consultation hours (starting from week 2):

Reading week 2: Thursday 8/9 15-16 h with Birgit (zoom) and Friday 9th of September 11-12 with Markus - in his office on floor 5 D&IT, room nr 5471

Reading week 3: Thursday 15/9 at 15-16 h and Friday 16/9 at 10-11 in Ivan´s office floor 6 D&T, room 6449 (ring the doorbell by the main entrance to the corridor or knock on the glass door in the entrance Linsen staircase).

Reading week 4: Thursday 22/9 at 15-16 h and Friday 23/9 at 10-11: with Jeremy, floor 6, room 6213.

Reading week 5: Thursday 29/9 at 15-16 h with Markus in EG-5215A and Friday 30/9 with Birgit in EG-5209A

Reading week 6: Thursday 6/10 at 15-16 h and Friday 7/10, both with Ivan, room 3128. Text Ivan on his mobile .. if corridor is locked.

Reading week 7:  Thursday 13/10 at 15-16 in room 5207 (with Birgit), and on zoom (with Jonah)  Friday 10-11 zoom with Jonah (https://chalmers.zoom.us/j/61539448895 (Password: 245110)) 

Reading week 8:

Thursday 20/10 kl 15-16 room 6449 (floor 6, inside staff corridor, use the staircase F at the far end of Linsen and knock on the glass door,  with Ivan) (room was changed from floor 3 to floor 6)

Friday 21/10 kl 10-11 (zoom https://chalmers.zoom.us/j/61284140734 Password: 917137) (with Birgit)

Literature

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

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 may be swapped. It should be easy to recognize this and find the correct chapters by their titles.) Sections with the label "Problem" describe the computational problems treated in the course; do not misunderstand them as exercises.

Additional material (e.g. lecture slides if applicable etc.) may be added on the Additional course material page during the course.

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

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 ask the teachers or TAs questions about them.

  • Time complexity, O-notation (chapter 2): 1,2,3,4 (O() complexity), 6 (two dim array)
  • Greedy (chapter 4): 3 (loading trucks), 4 (sub-sequence), 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),

Exercise sessions:

In every reading week, there will be 3 exercise session with identical content. Choose the one where the time suits you best. The content will be a subset of the recommended exercises from the course book and will be announced below before each exercise class.

  • Content of exercise sessions in reading week 2: KT chapter 2 problems 3 and 6; Ass1 problem 2.  (TAs Markus and Ivan)
  • Content of exercise sessions in reading week 3: KT chapter 3 problem 7 (connected mobile devices); chapter 4 problem 6 (swim, bike, run) (TAs Ivan and Jeremy), if time allows: solution of Assignment 2, problem 4
  • Content of exercise sessions in reading week 4: KT chapter 6: problems 4 (NY-SF) and 6 (pretty printing), (TAs Markus and Yu)
  • Content of exercise sessions in reading week 5: KT chapter 5: problems 3 (credit cards) and 5 (hidden surface)  (TAs Ivan and Jeremy)
  • Content of exercise sessions in reading week 6: KT3 (problems 3 and 12) and Assignment 4, problem 8. (TA Ivan)
  • Content of exercise sessions in reading week 7: KT chapter 8, problems 1,3 and if time allows 5). Monday session over zoom with Jonah (https://chalmers.zoom.us/j/62625730557,  Passcode 492175), Wednesday sessions on campus with Yu.
  • Content of exercise session in reading week 8: old exam questions and Greedy proof Assignment 3 problem 6b (with Sanna and Jeremy)

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.

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.

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.

SUBMISSION INSTRUCTIONS:

We use the Fire submission system: LINK TO FIRE

Make sure that you use only this link to Fire, not a link from an earlier year. First create an account in Fire. You do this only once. As all assignments are individual, you don't have to create a group in Fire.

To create an account: Go to the submission system. Bookmark the link (you will need it again), click on "Click here to register as a student" and fill in your email address (preferably your student address). You will get a mail with a web address. Click this address, it leads you to a page where you can fill in your data: name, personal number, and a password. Spell your name correctly as "Firstname Surname" (only the most commonly used first name is needed, with big initial letters) and write your personal number as yymmdd-xxxx with the dash, i.e., the minus sign. Log on using the account you have just created.

To submit a solution: Log on to Fire again. Upload the file(s) that make up your solution. Finally press the "submit" button. (This is easy to forget.) Fire will close exactly at the given deadlines, therefore, do not wait until the last minute.

Solutions should be submitted as PDF files, created with a word processor or latex or by scanning handwritten sheets - provided that they are readable. Your files must contain your name. Please send a separate file for each problem.

From the grader you will receive a mail with comments. You can also download the comments from Fire. Special remark: By default you will always get "fail" the first time you submit, even if the solution was good; this has only technical reasons (possibility to resubmit an improved solution) and does not mean anything. Only the comments are of interest. You have the possibility to re-submit once and get further comments.

 

Exam: see Module Exam

 

Course summary:

Date Details Due