Kursöversikt
Course-PM TIN093/DIT602 Algorithms, period 3 VT19 (7,5hp)
Instructors:
- Peter Damaschke
- Devdatt Dubhashi
- Muhammad Azam Sheikh
- Birgit Grohe, grohe(at)chalmers.se EDIT6483 (examiner and course coordinator)
Assistants
- Aristide Tossou, aristide(at)chalmers.se
- Markus Aronsson, mararon(at)chalmers.se
- Oskar Abrahamsson, aboskar(at)chalmers.se
- Simon Robillard, simon.robillard(at)chalmers.se
Announcements
- 22/1 The lecture on Wednesdays collides for many students. We are investigating to move the Wednesday lecture to 8-10 or 15-17 from reading week 2, more information will be announced later this week.
- Link to previous years homepages.
- Link to schedule in timeedit.
- Student representatives:
- Afshin Soltani (MPCSN), afshins@student.chalmers.se
- Akshita Bhatt (MPCSN), bhatta(at)student.chalmers.se
- TBA
- TBA
- Exam aids: TBA
Lecture Notes
Numbers indicate the related book sections. (Note: Chapters have different numbers in some editions of the book. But it should be easy to recognize this and find the correct chapters by their titles.) Sections with the label "Problem" describe computational problems that will be discussed in the following lectures; the idea is that you should already become familiar with the problem.
- Lecture 1. General introduction: problems, instances, algorithms. Time complexity and O-notation (2.1, 2.2, 2.4). Slides from the first half of the lecture, lecture notes written by Peter Damaschke
- Lecture 2. Greedy algorithms. Interval Scheduling (4.1).
- Remaining lectures may cover topics within: Dynamic programming. Weighted Interval Scheduling (6.1, 6.2). Dynamic programming for Subset Sum and Knapsack (6.4). Segmentation problems (6.3). Sequence Alignment (6.6). Divide-and conquer. Binary search (end of 2.4). Skyline problem. Recurrences (5.1-5.2). Briefly about Sorting and Median Finding (5.1, 13.5). Counting Inversions (5.3). Fast Multiplication (5.5). Polynomial-time reductions (8.1). Complexity classes P and NP (8.3). NP-completeness (8.4). Satisfiability problem (8.2). Several NP-complete problems (from 8.5-8.7). Graph traversal and Connectivity (3.2, 3.5). Coloring and Bipartiteness. Minimum Spanning Tree (4.5). Directed cycles and Topological Order, DAGs (3.6). Shortest and longest paths in DAGs. Union-and-Find (4.6). Interval Partitioning (end of 4.1). Space-efficient Sequence Alignment (6.7). Closest points (5.4). Clustering with maximum spacing (4.7). Articulation points in graphs.
Recommended Book Exercises
Here we will list some particularly recommended exercises from the book, for those who want to practice a bit more on their own. Some of them appear(ed) in the exercise sessions. You are also welcome to send questions about them.
- TBA
Times and Places
Lectures: Mondays 10.00 - 11.45 and Wednesdays 13.15 - 15.00 in HA2 (no lecture 6/2 due to CHARM). Link timeedit.
Exercise classes usually Wednesdays 15.15 -17.00 in EE and Thursdays 15.15 - 17.00 in ES53 (with a few deviations in reading week 3 and 4). Link timeedit.
Consultation hours every Friday afternoon before a deadline: TBA.
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 and kurs-pm.
The course provides basic knowledge and methods for the design and analysis of fast and well-founded (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 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.
Grades are based on the points in the written exam. Point limits for the grades 3, 4, 5 and G, VG will be announced.
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, by doing assignments.
While they are voluntary, it is strongly recommended to work on these problems 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.
- Assignment 1: pdf - deadline Sunday 27/1
- Assignment 2..
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 non-trivial part of the job. 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 must be written in your own words and reflect your own understanding.
The submission is done individually in the FIRE system.
The graders will try to give feedback within 4-5 working days after the deadline. You can resubmit to improve your solution and get further feedback. Maximum number of re-submissions per Assignment is 1. If after the second round of feedback there are still questions left, you may book an individual appointment with your grader.
Exercise sessions:
The two exercise sessions within a week are identical. Choose one of the time slots. If one session is too crowded, we may ask you to consider another time.
In the sessions, assistants will discuss solutions to a few selected exercises from e.g. the book, but a large part of the exercise session is intended to be a question hour where you can work on the assignments and get help. (However, we will not give away solutions.) This is also a place to discuss and to ask questions about the course contents in general.
Seeking more help:
Feel free to send any questions or to book consultations by mail. You may also drop by our offices, but we may be busy or away, therefore it is advisable to make appointments by mail.
Examination form
Exam date, exam aids, points, TB
Link to the Some Previous Exams
- Course pages of both course versions.
- Exam from October 2015 with solutions.
- Exam from October 2016 with solutions.
- Exam from October 2017 with solutions.
Kurssammanfattning:
| Datum | Information | Sista inlämningsdatum |
|---|---|---|