Course syllabus
TIN093/DIT093, Period 3, 2023: Algorithms
Instructor
- Peter Damaschke, ptr(at)chalmers.se, EDIT 5480, is instructor and examiner in this period.
- Birgit Grohe, birgit.grohe(at)cse.gu.se, EDIT 5483, is examiner for the same course in period 1, and for the re-exam in August 2023.
For contact, please use ordinary email, no canvas massages.
Assistants
Email: add "(at)chalmers.se", unless said otherwise.
- Markus Pettersson (markus.pettersson)
- Jeremy Pope (popje)
- student TA: Emil Holmberg - only for help with the assignment feedback
Student Representatives
- Edvin Alestig (edvale), Adam Calais (calais), Karl Olausson (karlola)
Announcements
-
Exam with solutions: algexam230315.pdf
- Exam review: Wednesday, 5 April, 11:00-13:00 in room EDIT 5128.
- The re-exam is in August. (There had been some misleading central information about an alleged re-exam in June.) The correct dates are in the course plans.
Exam Aids
Dictionary, printouts of the Lecture Notes (which may contain own annotations), one additional handwritten A4 paper (both sides).
Some old exams (from the same instructor): 2021 2019 2018 2017 2016 2015
Teaching
It consists of normally two lectures per week (Monday and Wednesday 10-12, with some exceptions), some form of exercises and/or consultations, and written assignments. None of these items are compulsory, and the grade is solely based on the written exam.
See TimeEdit for the schedule.
Consultation sessions on Wednesday afternoons (called Exercises in TimeEdit) are held in seminar rooms. They are intended to be an open forum where you can come by and ask or discuss any questions about course topics, get help with the assignments and with additional book exercises that you have tried.
You can drop in at any time. For an efficient use of time, please prepare clear questions. If you got stuck on an exercise, also prepare explanations of what you have tried and what you are wondering about. We will not give away complete solutions, but we try to help you advance further from the point where you are.
If you rather prefer a "private" consultation on some matters, send a mail to make an appointment.
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.
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). alg1-2023.pdf
- Lecture 2. Greedy algorithms. Interval Scheduling (4.1). alg2-2023.pdf
- Lecture 3. Dynamic programming. Weighted Interval Scheduling (6.1, 6.2). alg3-2023.pdf
- Lecture 4. Dynamic programming for: Subset Sum and Knapsack (6.4). Segmentation problems (6.3). alg4-2023.pdf
- Lecture 5. Dynamic programming for Sequence Alignment (6.6). Divide-and conquer. Binary search (end of 2.4). Skyline problem. alg5-2023.pdf
- Lecture 6. Recurrences (5.1-5.2). Briefly about Sorting and Median Finding (5.1, 13.5). alg6-2023.pdf
- Lecture 7. Counting Inversions (5.3). Fast Multiplication (5.5). Polynomial-time reductions (8.1). alg7-2023.pdf
- Lecture 8. Complexity classes P and NP (8.3). NP-completeness (8.4). Satisfiability problem (8.2). alg8-2023.pdf
- Lecture 9. Several NP-complete problems (from 8.5-8.7, very cursory). alg9-2023.pdf
- Lecture 10. Graph traversal and Connectivity (3.2, 3.5). Coloring and Bipartiteness (3.4). alg10-2023.pdf
- Lecture 11. Minimum Spanning Tree (4.5). Directed cycles and Topological Order, DAGs (3.6). alg11-2023.pdf
- 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). alg12-2023.pdf
- Lecture 13. Closest points (5.4). Clustering with maximum spacing (4.7). alg13-2023.pdf
Assignments
Literature
The course follows selected parts of the textbook
Jon Kleinberg, Eva Tardos: Algorithm Design. Pearson/Addison-Wesley 2006, ISBN 0-321-29535-8. (Any edition of the book is usable.)
Recommended Book Exercises
Here we list some particularly recommended exercises from the book. If you practice book exercises on your own, you are welcome to send questions about them.
- Greedy (chapter 4): 3 (loading trucks), 4 (subsequence), 5 (base stations on a road), 6 (sports schedule), 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),
Brief Course Description
See also the syllabus.
The course provides basic knowledge aabout methods for the design and analysis of correct and fast 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 algorithm design techniques 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, 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 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 algorithm design techniques to new problems, or at least adapt known algorithms to new variants of known problems. Therefore this course is problem-oriented and the exam requires problem solving, too.
Moreover, one cannot learn these skills just by listening, or by reading a lot of solutions written by others. (Compare it to other skills: Can one learn to play a musical instrument just be watching others playing? Of course, one has to practice!) It is important to actively solve problems. The course offers possibilities, mainly by assignments.
While the assignments are voluntary, it is strongly recommended to work on them as much as you can. Then you are not only in a much better position in the exam, we also hope that 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, as 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.
The level of assignments and exercies may be higher than the level of typical exam problems. This is intended. 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 Details
We plan to use the Fire submission system rather than the Assignments feature of Canvas. Fire allows us a smoother coordination and is also convenient to use.
Follow only the link to Fire provided here, not a link from an earlier year. Fire
First create an account in Fire. You do this only once. As all submissions are individual, you don't have to create a group in Fire.
To create an account: Go to the Fire system. Bookmark the link (you will need it again), press "Click here to register as a student" and fill in your student email 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, with big initial letters) and write your personal number as yymmdd-xxxx with the dash, i.e., the minus sign. If you do not have a Swedish personal number, use a made-up number. 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 - do not wait until the last minute.
Submit solutions as PDF, created with a word processor or latex. Scanning handwritten sheets is discouraged, but if you must, they have to be readable. Your files must contain your name.
From the grader you will receive a mail with comments. You can also download the comments from Fire.
Special remark: By default you may always get "fail"; this has only technical reasons (possibility to resubmit an improved solution) and does not mean anything. Only the comments are of interest.
Course summary:
| Date | Details | Due |
|---|---|---|