TIN093/DIT602, Period 1, 2018: Algorithms
Instructor
- Peter Damaschke,
ptr(at)chalmers.se, EDIT 6478. (Make sure that you use the correct mail
address.)
Assistants
Email: add "(at)chalmers.se", unless said otherwise.
- Aristide Tossou (aristide)
- Elena Pagnin (elenap)
- Oskar Abrahamsson (oskar.abrahamsson)
- Markus Aronsson (mararon)
- Victor Lopez Juan (lopezv)
- Yu-Ting Chen (yutingc)
Announcements
- Exam with solutions.
- Re-exam with solutions.
- Re-exam review: Tuesday 22 January, 11:00-13:00, room EDIT 4128.
Link to the Spring Version and Some Previous Exams (Autumn)
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 complextiy 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). - with some additional information that was not in the lecture.
- 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.
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). Articulation points in graphs.
Assignments
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. Some of them appear(ed) in the
exercise sessions. 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 and Places
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 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.
Exercise sessions:
The three exercise sessions within a week are
identical. Choose one of the three time slots. If one session is too
crowded, we may ask you to consider a later time.
In the sessions, assistants will discuss solutions to a few selected exercises
from the book, but the major part 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.
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
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: see below.
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.
Submission Details
Fire submission system.
Make sure that you use only this link, 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. 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"; this has only technical reasons (possibility to resubmit an improved
solution) and does not mean anything. Only the comments are of interest.