TIN093/DIT602, Period 1, 2017: Algorithms

Assistants

Email: add "(at)chalmers.se", unless said otherwise.
• Aristide Tossou (aristide)
• Erland Holmström (erland)
• Inari Listenmaa (inari.listenmaa(at)cse.gu.se)
• Markus Aronsson (mararon)
• Victor Lopez Juan (lopezv)
• Yu-Ting Chen (yutingc)

Announcements

• Student representatives: Victor Tardieu (tardieu), Denis Furian (den.furian(at)gmail.com), Christopher Meszaros (christophermeszaros07@gmail.com), Jan Phillip Bläs (gusblasja(at)student.gu.se), Simon Ceder (guscedersi(at)student.gu.se), Karl Strigen (strigen).
• Exam with solutions.
• Re-exam with solutions.
• Re-exam review: in January, by appointment, no later than 23 January.

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.)

• Lecture 1 (slides): General introduction. Notions of algorithm, problem, instance. Modelling of problems. Pseudocode. Some examples.
• Lecture 2 (slides): Time complexity and O-notation (2.1-2.4).
• Lecture 3 (slides): Greedy algorithms, with a detailed example: Minimum Spanning Tree, Kruskal's algorithm (4.5). Union-find data structure (4.6). Clustering (4.7).
• Lecture 4: Arriving at a greedy algorithm for Interval Scheduling (4.1). About greedy algorithms is general.
• Lecture 5: Weighted Interval Scheduling (6.1, 6.2). Dynamic programming in detail. Subset Sum and Knapsack (6.4).
• Lecture 6: Sequence Alignment (6.6). Idea of divide-and-conquer. Special recurrences (5.2).
• Lecture 7: Very briefly about Sorting. A bit of randomness: Median finding (13.5). Counting Inversions (5.3). Fast Multiplication (5.5).
• Lecture 8: Reductions between problems, examples: Clique, Independent Set, Vertex Cover (8.1). Complexity classes P and NP, and NP-completeness (8.3,8.4).
• Lecture 9: Conjunctive normal forms, SAT and 3-SAT (8.2). Reducing 3-SAT to Independent Set (in 8.2). Final remarks about NP-completeness. (Not a mistake; these notes are short.)
• Lecture 10: Graph traversals (3.2) with some applications: Connectivity (3.2, 3.5). Bipartiteness, 2-Coloring (3.4). Directed cycles and Topological Order (3.6).
• Lecture 11: Fast construction of a topological order (3.6). Shortest and longest paths in acyclic graphs. Network Flow (7.1-7.2).
• Lectures 12-13: (only the "book topics"): Bipartite Matching (7.5). Interval Partitioning (in 4.1). Space-efficient Sequence Alignment (6.7). Closest Points (5.4).

Exercises

Do not confuse them with the assignments. Some of these exercises are discussed in the sessions. The exercises (except set 1) are taken from the textbook.
• Exercise set 1
• Exercise set 2: chapter 4: exercises 3, 4, 5, 7, 13; 1, 2, 8.
• Exercise set 3: chapter 6: exercises 2b, 4c, 5, 6, 10b, 11, 12, 15b.
• Exercise set 4: chapter 6: exercises 18, 14; chapter 5: exercises 1, 3, 5, 7; chapter 2: exercise 8.
• Exercise set 5: chapter 8: exercises 1, 2, 3, 5, 14, 15.
• Exercise set 6: chapter 3: exercises 1, 3, 7, 9, 12.

Times and Places

Lectures:
Monday 8:00-9:45, room HA4
Wednessday 10:00-11:45, room HB3

Exercise sessions:
Monday 10:00-11:45, room EC
Wedneday 13:15-15:00, room EC
Wedneday 15:15-17:00, room EC

Literature

The course material consists of parts of the textbook
Jon Kleinberg, Eva Tardos: Algorithm Design. Pearson/Addison-Wesley 2006, ISBN 0-321-29535-8.
It should be available at Cremona.

Brief Course Description

The course provide 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 (and explain why) 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, if one wants to solve a new problem with the help of computers.

Grades are based on the points in the written exam. Point limits for grades 3, 4, 5 and G, VG will be announced.

Oral Exercises and Written 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 techniques to new problem, or adapt and adjust known algorithms to new variants of known problems. Therefore this course is problem-oriented. Also the exam will require problem solving.

Moreover, one cannot learn these skills just by listening and reading. It is important to invest own work and actively solve problems. The course offers possibilities for that:

Exercises and assignments:
They are voluntary, but 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:
They are used to discuss and solve problems, e.g., from the textbook. This is also a place to ask questions about the course contents and the assignments. We have three identical sessions per week, so you should choose one of them.

Written solutions to assignments:
Most importantly, train your ability to explain solutions in written form. Comprehensible writing is not trivial, and 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. The deadline is always Sunday 23:59. (That is, the system will close at that time. 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

The link to the Fire submission system is here.

First create an account in the Fire system. You do this only once.

As all assignments are individual, you don't have to create a group in Fire.