Algorithms (Algoritmer) TIN092/DIT600 (7.5 points)

Period 1, September-October 2009

Announcements

Course homepage from spring 2008.
Course homepage from HT 2008.
Exam with solutions.
The compulsory programming assignment. Link to the Fire system for this course.
Re-exam with solutions.

News

2009-11-10 The exam solutions can be found here.
2009-11-10 The date, time and place for the exam review session (tentagranskning) is now set. It will be held on Friday, November 13th, at 15:00-16:00, in room 6471 (next to Devdatt's office).
2009-10-15 Problem set 6 is graded. You may look at our frequent comments and grading criteria for ps6.
2009-10-15 In addition to the normal consultation hours, we offer an extra consultation hour on the day before the exam, monday 19/10 13-15 in Birgits and Willards offices.
2009-10-14 You may bring the following aids to the exam on tuesday, 20th of october: Dictionary, course book, printout of lecture notes, exercise session notes and other material from the course homepage. But nothing else.
2009-10-09 Problem set 5 is graded. You may look at our grading criteria for Problem set 5.
2009-10-08 Notes from today's (and the coming Monday's) excercise sessions are now available here, and in the Exercise Diary section of this page.
2009-10-07 On tuesday, we had the second meeting with the course evaluators, the minutes can be found here.
2009-10-01 Problem set 4 is marked. Details as usual. Unfortunately many have misunderstood problem 4.1 and got fewer points in total compared to the previous problem sets.
2009-09-25 Problem set 3 is marked. Details as usual.
2009-09-25 The grading of progamming assignment 1 is still going on. Because of high workload the groups that have the grader Filippo Tedesco will get feedback by the end of the weekend. We apologize for the delay!
2009-09-22 Clarification about the programming assignment: You must work in groups of 2 persons, neither more or less than 2. If you have special reasons you must contact us in advance to get special permission. Otherwise you will not be able to submit in fire.
2009-09-22 Following suggestions of the course evaluators we have added extra consultation hours on wednesdays (see below) and also changed the exercise schedule to make it more syncornized with the lectures (see below). Minutes from the first course evaluation meeting can be found here.
2009-09-18 15:30 Problem set 2 is marked. You can fetch your submission (even electronical) next to the submission box. Your bonus points are written on your submission. Since we got over 100 submissions we cannot notify you in any other way about your bonus points.
2009-09-16 We have now found 5 students that are going to be course evaluators. For general information about course evaluation, at Chalmers, see this link.
2009-09-11 21:30 Problem set 1 is marked. You can fetch your submission (even electronical) next to the submission box. Your bonus points are written on your submission. Since we got over 100 submissions we cannot notify you in any other way about your bonus points.
2009-09-03 It is not possile under any circumstances to do the programming assignments in groups of more than 2 people. If you cannot find a labpartner yourself, please email Birgit. She will help you to find one.

The Sexiest Jobs!

Why study algorithms? Because it will have the sexiest jobs in the next ten years, according to Hal Varian, Head honcho at Google economics.

I keep saying that the sexy job in the next 10 years will be statisticians, And I am not kidding. Though at the fore, statisticians are only a small part of an army of experts using modern statistical techniques for data analysis. Computing and numerical skills, experts say, matter far more than degrees. So the new data sleuths come from backgrounds like economics, computer science and mathematics.

Note: if you read carefully, when he says "statistics" he really means "statistical algorithms". One of the authors of our textbook also features in this New York Time story. In general, algorithms are increasing playing a very important role in technological developments from web search, on--line advertisement and commerce to bioinformatics and biomedicine. Companies like Google, Microsoft and Yahoo! or AstraZeneca and Applied Biosystems are looking for people with algorithmic skills. Algorithms are also just great fun! Try out these challenges from last year's Nordic Programming Championship andd see how the skills you learn here can help you in this year's championship !

Course goals

To understand the notion of efficient algorithms and their importance.
To learn paradigm techniques for solving computational problems.
To apply them to various concrete examples of problems which lie at the core of real-world computer science applications.
To rigorously analyze the performance of algorithms, i.e., correctness and time complexity.
To discuss the efficient use of data structures in complex algorithms.
To see how new computational problems can be solved: how to analyze problems, how to choose suitable algorithmic techniques, how to adapt and combine them.
To train how algorithms are explained, especially in written form.
To know the limits of efficient computation.

This course is not:

a course in programming (even though it includes a programming assignment),
just a collection of a few standard "push button" packages for particular problems.

Prerequisites: (Suitable courses providing this knowledge depend on the study programme.)

Computer programming: some imperative programming language, including recursion.
Data structures, such as: lists, stacks, queues, arrays, graphs.
Mathematics: elementary logic, sets and functions, rules of logarithms, mathematical proofs, induction. Please read why math?

Evaluation

To pass the course, you have to pass

the programming assignment.
the final written exam.

Your grade will be based only on your score in the final written exam (max. 60):

Chalmers: "3": 24, "4": 36, "5": 48.
GU: "G": 28, "VG": 48.

However, you can add upto a maximum of 12 bonus points to the score on your written exam in october 2009 by solving problems assigned weekly, see below. Observe that the bonus points cannot be used for any other exam than the one directly after the course, in october 2009.

Practical information

Course book:
Jon Kleinberg, Eva Tardos: Algorithm Design. Pearson/Addison-Wesley 2006, ISBN 0-321-29535-8.

The "dream textbook", written by two of the foremost researchers and teachers. It should be available at Cremona for ca 650 SEK, but it may be cheaper at other places. However, note that it is planned to use this book also in the Advanced Algorithms Course in period 2.

Instructor:
Devdatt Dubhashi: room 6478, dubhashi(at)chalmers.se. (Lectures.)

Assistants:
Birgit Grohe, [vacant; contact Devdatt instead] (overall responsibility for course administration, exercise sessions, grading of problem sets)
Filippo Del Tedesco, room 5472, tedesco(at)chalmers.se (grading of programming assignment and problem sets)
Leonid Molokov, room 6476, molokov(at)chalmers.se (lab supervision and grading of problem sets)
Azam Sheikh Muhammad, room 6453, azams(at)chalmers.se (mainly grading of programming assignment)
Willard Rafnsson, room 6449, willard.rafnsson(at)chalmers.se (exercise sessions, grading of problem sets)

When you contact us: The subject line of every email should start with "Algorithms" and course code.

Student representatives for course evaluation:
Malin Ahlberg, ahlberg.malin(at)gmail.com
Jafari Hamidreza, hamidrjafari(at)gmail.com
Faiza Munir, faizam(at)student.chalmers.se
Mehvish Rashid, mehvish(at)student.chalmers.se
Rafaél Vandon, vandonr(at)esiee.fr
For general information about course evaluation at Chalmers see this link.

Schedule: (Possible changes of single classes will be announced.)

Lectures: Tuesday, 8:00-9:45. Thursday, 13:15-15:00, both in HB1.
Exercise sessions: Change in Exercise Session Schedule! From reading week 5 on, the exercise sessions topics will follow the lectures in a better way. Each tuesday the lectures start with a new topic and the first exercise session with the same new topic will be on thursdays. The monday session will therefore have the same content as the preceeding thursday. The exercise session on monday 28 okt is cancelled.
Mondays, 10:00-11:45 in EF, (cancelled: 28/10)
Thursdays, 10:00-11:45 in EE,
Thursday, 15:15-17:00, in ED.
Exercise sessions are mainly used for discussion of solutions to selected exercises. A short introduction to the two programming assignments will be given 1-2 weeks before the respective deadline. If there is time left, hints for the problem sets will be given before the deadline for submission, and solution sketches will be presented after the deadline.
Notes (the instructures slides) can be found below, see exercise diary.
Lab supervision Please read about the computer assignments and the role of the lab supervision here.
Thursay 17/9 at 9:00-12:00 in room E6225.
Thursday 1/10 at 9:00-12:00 in room E6225.
Consultation hours If you want to discuss questions regarding the problem sets, you can drop by the following offices:
NEW! Wednesdays 11-12 and 13-14 in 6476 (Leonid)
Fridays 11-12 and 13-14 in offices 6449 or 6451 (Willard or Birgit)
Please respect the lunch break 12-13

Schedule in TimeEdit

Language:
The course language is English. According to Chalmers central regulations for master's programmes, solutions to the exam problems must be written in English (with exceptions in well justified cases only). We ask you to use English also for submissions of the programming assignment and the problem sets since none of the staff in the course is from Sweden.

Lecture Diary

(Slides with kind permission of Kevin Wayne, Princeton and Chandra Chekuri, U. of Illinois, Urbana-Champaign.)

[Week 36] Introduction to course, Stable Matchings [KT 1.1], Greedy algorithms [KT 4.1]
1. [Sept. 1] Stable matchings and Greedy .
2. [Sept. 3] Greedy algorithms cont'd, [KT, 4.2, 4.4]. Please review priority queues from [KT 2.5] and Dijkstra's algorithm from [KT 4.4] same slides as Sept. 1.
[Week 37] Greedy algorithms [KT 4.2 - 4.8]
1. [Sept. 8] Minimum spanning trees., [KT 4.5, 4.6]
2. [Sept. 10] Huffman Codes , [KT 4.8]
[Week 38] Dynamic programming [KT 6.1 - 6.9]
1. [Sept. 15] Dynamic Programming [KT 6.1 - 6.4].
2. [Sept. 17] Dynamic prog (concluded) RNA secondary structure [KT 6.5] sequence alignment [KT 6.6] and all pairs shortest paths [KT 6.8, 6.9].
[Week 39] Divide--and--Conquer [KT 5.1 - 5.5]
1. [Sept. 22] Divide-and-Conquer , Multiplication by Divide-and-Conquer
2. [Sept. 24] Closest points and selection via Divide and Conquer.
[Week 40] Network Flow [KT 7.1 - 7.3, 7.5, 7.10, 7.12]
1. [Sept. 29] Network Flows [KT 7.1 - 7.2]
2. [Oct. 1] Network Flows applications [KT 7.5, 7.6, 7.10, 7.12]
[Week 41] NP-completeness [KT 8.1 - 8.10]
1. [Oct. 6] Introduction to NP-completeness [KT 8.1]
2. [Oct. 8] More reductions [KT 8.2]
[Week 42] Wrap up and review
1. [Oct. 13] NP [KT 8.3, 8.4]. Minesweeper is NP-complete! .
2. [Oct. 15] Sample Exam . Sample Exam solutions.

Exercise Diary

Please observe the change in Exercise Session Schedule, see above.
[Week 36] Solved Exercises p. 65--66. Notes from the exercise session i reading week 1
[Week 37] Solved Exercises, p. 183 --188. Notes from the exercise session in reading week 2
[Week 38] Solved Exercises, p. 242 - 246.
[Week 39] Solved Exercises, p.307-310. Notes from the exercise session in reading week 4
[Week 40] Solved Exercises, p. 411 - 414. Notes from the exercise session in reading week 5
[Week 41] Solved Exercises, p. 500 - 505. Notes from the exercise session in reading week 6
[Week 42] Wrap up and review: We will go through the exam from 21 okt 2008, see top of this page.

Problem Sets

They are voluntary, but strongly recommended. You can get up to a maximum of 12 bonus points to add to your score on the exam in october 2009 to determine the grade. In each week's problem set, you may submit upto 2 problems for grading and for each problem you can get a maximum of 2 points . For the maximum 2 points, the solution should be complete, correct and elegant. To get any credit, you must have made non-trivial progress on the problem - simply submitting a scribble will not get any points. You may discuss problems with each other but you must write up your own solutions . Each week on Monday, a new Problem Set will appear here with at least 3 problems. Deadlines are strict !
The deadline for submission of the problem sets are on monday mornings at 10:00. Please submit in the box in linsen, 6th floor, marked with the course name and code. The problem set grading will be finished by friday lunchtime and you can get back you submission with bonus point notification in the open box next to the submission box in linsen.

[Week 36] Problem Set 1 . There are a limited amout of paper copies of the problem set for those who have not bought the course book (yet). Fetch them in the shelf next to the submission box in linsen floor 6.
[Week 37] Problem Set 2. . Paper copies available.
[Week 38] Problem Set 3. . Now paper copies available.
[Week 39] Problem Set 4. . Paper copies available.
[Week 40] Problem Set 5. . Paper copies available.
[Week 41] Problem Set 6. .

About cheating

Sadly, some serious remarks must be added here: Submitting others' work in your own name is cheating. This applies to both theoretical solutions and program code, partially or completely copied, exactly copied or modified. Observe carefully any specific rules that may have been given for the respective course requirements (e.g., programming assignments, written exam). You are also responsible for not giving others the opportunity to copy from your work. Cheating can lead to severe consequences, in very bad cases even suspension from studies. Do not try. If you have major difficulties fulfilling the course requirements, the proper way is to approach the teachers and ask for advice. We are here to help. A useful link that claifies the difference between collaboration and cheating.