- Peter Damaschke (ptr), EDIT 6478

- Erland Holmström (erland), EDIT 6474

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

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

**Course pages of**period 4.- Exam from October 2015 with solutions.
- Re-exam from January 2016 with solutions.
- Exam from October 2016 with solutions.
- Re-exam from December 2016 with solutions.

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

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

- Assignment 1, due Sunday 10 September (expired): Problem 1 and Problem 2
- Assignment 2, due Sunday 17 September (expired): Problems 1 and 2.
- Assignment 3, due Sunday 24 September (expired): Problems 1 and 2.
- Assignment 4, due Sunday 1 October (expired): Problems 1 and 2.
- Assignment 5, due Sunday 8 October (expired): Problems 1 and 2.
- Assignment 6, due Sunday 15 October (expired): Problems.

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

Jon Kleinberg, Eva Tardos:

It should be available at Cremona.

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.

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

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.

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.

**To create an account:** Go to the submission system. Use **only** the
link on the course homepage. Bookmark it (you will need it again), click on
"Click here to register as a student" and fill in your email address,
preferably the Chalmers address. You will get a mail with a web address. Click
the address, it leads you to a page where you can fill in your data: name,
personal security 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 just created.

**To submit a solution:** Log on to Fire again. Upload the file(s) that
make up your solution. Finally (easy to forget), press the "submit" button.
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 file must contain your names. Send one separate file for each problem.

From the grader you will receive a mail with comments. You can also download the comments from Fire.