- Peter Damaschke, ptr(at)chalmers.se, EDIT 6478. (Make sure to use the correct mail address.)

- Aristide Tossou (aristide)
- Elena Pagnin (elenap)
- Oskar Abrahamsson (oskar.abrahamsson)
- Markus Aronsson (mararon)
- Victor Lopez Juan (lopezv)
- Yu-Ting Chen (yutingc)

- This page is preliminary. Some details may change.
- Course start: Wednesday 5 September.
- Student representatives: TBA.
- Probably there won't be lectures in course week 7, and that week will be devoted to reading about some more specialized topics, and resubmissions of assignments. However this is not yet decided. Detailed advice will be given in good time.

**Course pages of**period 4.- Exam from October 2015 with solutions.
- Exam from October 2016 with solutions.
- Exam from October 2017 with solutions.

- Lecture notes will be added here as the course progresses.

- TBA

Jon Kleinberg, Eva Tardos:

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.

**Grades** are based on the points in the written exam. Point limits for the
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 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 (compare to other skills!) one cannot learn these skills just by
listening, or by reading a lot of solutions written by others. 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:**

They are rather question hours, used to provide
help with the assignments. (However, we will not give away solutions.) This is
also a place to discuss and to ask questions about the course contents. Choose
any of the three time slots you like.

**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 **Thursday 23:59.** 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.

Make sure that you use only this one, 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.