TIN092 - Algorithms (7.5 points) (DIT600 @ GU) - Course Information

Back to front page.

Index

Announcements

Welcome to the course! Right now, make sure to
  1. join the Google Group, where all future announcements will be made (read announcements already made there),
  2. sync your calendar to our Google Calendar (calendar e-mail) (HTTP),
  3. read this BBC News article (which helps motivate this course),
  4. watch the therein-mentioned (15-minute) TED talk, and read this blog entry explaining the Amazon book incident,
  5. buy the course book,
  6. start reading [KT 1.1, 2.1, 2.2, 2.4].
  7. solve the quiz.
We also recommend you read this whole page once, so you know what you are in for.

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 2008 year's Nordic Programming Championship and see how the skills you learn here can help you in this year's championship!

Course goals

This course is not:

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

Evaluation

To pass the course, you have to pass the final written exam. Your grade will be based only on your score in the final written exam (max. 60):

  1. Chalmers: "3": 28, "4": 36, "5": 48.
  2. GU: "G": 28, "VG": 48.
However, you can add up to 12 bonus points to the score on your written exam in October 2011 by solving weekly exercises and biweekly labs.

When determining to which extent you have obtained the course goals, we evaluate

  1. correctness and efficiency of your solution to exam problems, and
  2. quality of the presentation of said solution (which should be rigorous/logical/concrete/short/simple/to-the-point)
As we evaluate your exercise and lab submissions the same way, we urge you to participate in them, so you have a better impression of what is expected of you (and thus a better chance of passing the exam).

Observe that the bonus points cannot be used for any other exam than the one directly after the course, in October 2011.

Exam aids: "anything on print is permitted, which includes textbook, slides, exercise session notes, student's personal notes, old exams, and so on"

Sample exams

Cheating

Short version: Don't.

Long version: 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 it. We are here to help. If you have major difficulties fulfilling the course requirements, the proper way is to approach the teachers and ask for advice. A useful link that clarifies the difference between collaboration and cheating.

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 ~650 SEK, but it may be cheaper at other places. Note that the plan is to also use this book in the Advanced Algorithms course in period 2.

Course model

Generally, each week n of the course has a major theme. The themes are

  1. Preliminaries
  2. Greedy algorithms
  3. Dynamic Programming
  4. Divide and Conquer
  5. Flow Networks
  6. TBA
The pattern of supervised sessions and deadlines for week n is as follows.

(Note: There is only one exercise session per week. If that turns out to be too little, we will add more. If this is an issue for you, contact the course administrator.)
(Note-note: We have added an extra exercise session for theme 2 and 3. If participation in exercise sessions stays strong, these extra exercise sessions per week will also be added for the remaining theme weeks.)

Here, there should only be one active theme in lectures and exercise sessions during each week n. You will then also be working on the theme from week n-1 ("last week" if week n is the current week) in the exercises. (we did our best to minimise the number of concurrent course themes, given our constraints and resources)

This illustration might be helpful:

The course language is English. According to Chalmers central regulations for master's programmes, everything must be written in English (with exceptions in well justified cases only).

Lectures:

Here the lecturer teaches ideas and techniques related to the theme of the week the lecture occurs in.

Exercise sessions:

For discussing solutions to selected exercises from the book and, if time allows, solution sketches for last week's exercises, and hints for current exercises.

Consultation hours:

Here, an exercise session supervisor (Willard or Leonid) is available for drop-in questions involving the weekly exercises. If many students show up, more time can be added, or separate meetings can be booked for those that require further assistance. Please respect the lunch break starting at 12:00.

Lab sessions

These time slots show time you should be spending on your labs. The sessions are unsupervised, so where you do them is up to you. If you need assistance, contact the lab graders (Filippo or Azam) in a timely fashion.

Deliverables

There are two kinds of deliverables in this course, neither of which are mandatory.

At the end of the course, the bonus points in the exam are calculated from these grades as follows:

BonusPoints = 0.1 * (sum of grades from exercises) + sum of grades from labs

Thus, a maximum of 12 bonus points can be obtained; 6 from solving exercises (1 for each exercise), 6 from solving labs (2 for each lab).

When grading your submissions, we evaluate

  1. correctness and efficiency of your solution, and
  2. quality of the presentation of said solution (which should be rigorous/logical/concrete/short/simple/to-the-point)
As we evaluate your exam the same way, we urge you to participate in solving these exercises and labs, so you have a better impression of what is expected of you (and thus a better chance of passing the exam).

Exercise sets

You will find the exercise sets embedded in the schedule.

Validity

For a submission to be valid, it must be

  1. Written, legibly, by hand, by you, with a non-red marker, on the space given on an A4 printout of the entire exercise set.
  2. Marked with your name, personnummer, and e-mail address, in the indicated space on the printout.
  3. Delivered, physically, in the marked mailbox, located on the 6th floor of Linsen in the EDIT building, or to Devdatt in the Thursday lecture, before the deadline.
Failure to comply with any of these requirements invalidates your submission, in part or in full.

Grading

We expect you to submit complete solutions. Include enough detail to convince a suspicious (but rational) stranger who has completed this course that your solution is accurate. Any non-trivial claim must be supported with a rigorous justification/proof (science settles for nothing less).

We also expect the solutions to be presented in a clear manner. Make sure the solution is coherent, easy to read, and not confusing / misleading.

Obtainable points for a solution which is not complete or clear is lowered depending on the severity of the omission / lack-of-clarity / confusion / writing (and can be as low as 0).

A useful rule-of-thumb: Would you publish your solution, in a research paper, a book, or in an algorithms community mailing list?

Guidelines & other useful information

We recommend writing a rough sketch of a solution on scratch paper, and then write (only) the complete solution on the exercise sheet.

The general strategy for solving an exercise is the following (this is the recipe for using science to solve real problems!).

  1. Formalize abstract details of the problem (only as needed to solve the problem),
  2. Solve the (formalized) problem using theory (some learned in the course),
  3. Prove that the solution is correct (your solution solves the problem).
Example: If asked for an algorithm which sorts a list of integers in time O(n log n), you must
  1. Introduce notation for a list of integers,
  2. Give the pseudocode for an algorithm which sorts the list (using the notation you introduced),
  3. Prove that your algorithm sorts the list, and has running time no worse than O(n log n).

We will write feedback on your submission with a red marker. Submit a copy of your submission if you want to keep an intact original.

Labs

See the labs for directions on how to solve and submit them.

People

Please note:

Instructor:

You obtain a person's e-mail address by appending "@chalmers.se" after the content of the "Contact" entry.

Assistants:

You obtain a person's e-mail address by appending "@chalmers.se" after the content of the "Contact" entry.

Student Representatives:

You obtain a person's e-mail address by appending "@gmail.com" after the content of the "Contact" entry.

General information about course evaluation at Chalmers can be found here.

Schedule

Available here:

For convenience, we give last year's full course plan below. It will change (ours is an ever-evolving course). Weekly reading should be fixed 1 week in advance, and session topics pinned 3 working days in advance.

The time slots are fixed, however. Deviations in time slots, or in the general course plan, will be announced through the Google Group mailing list associated with the course.

  1. Preliminaries
      Reading: [KT 1.1, 2.1, 2.2, 2.4]
      Quiz: here
    1. 2011-08-30 (Tuesday), 08:00-09:45. Lecture.
    2. 2011-09-01 (Thursday), 13:15-15:00. Lecture.
      • Topics: basics of algorithm analysis, running time, asymptotics
      • Location: HC2
    3. 2011-09-01 (Thursday), 15:15-17:00. Exercise session.
  2. Greedy algorithms
      Reading: [KT 4.1-4.8]
    1. 2011-09-06 (Tuesday), 08:00-09:45. Lecture.
      • Topics: Greedy [KT 4.1-4.4] (review priority queues [KT 2.5] and Dijkstra's algorithm [KT 4.4]),
      • Location: HC2
    2. 2011-09-08 (Thursday), 13:15-15:00. Lecture.
    3. 2011-09-08 (Thursday), 15:15-17:00. Exercise session.
  3. Dynamic programming
      Reading: [KT 6.1-6.9]
    1. 2011-09-13 (Tuesday), 08:00-09:45. Lecture.
    2. 2011-09-15 (Thursday), 13:15-15:00. Lecture.
      • Topics: RNA secondary structure [KT 6.5], sequence alignment [KT 6.6], all pairs shortest paths [KT 6.8, 6.9].
      • Location: VA
    3. 2011-09-15 (Thursday), 15:15-17:00. Exercise session.
      • Topics: recurrence relations, implementation, memoization. notes, exercise set 3.
      • Location: EB
  4. Divide-and-Conquer
      Reading: [KT 5.1 - 5.5]
    1. 2011-09-20 (Tuesday), 08:00-09:45. Lecture.
    2. 2011-09-22 (Thursday), 13:15-15:00. Lecture.
      • Topics: Closest points and selection via Divide and Conquer.
      • Location: HA1
    3. 2011-09-22 (Thursday), 15:15-17:00. Exercise session.
  5. Network Flow
      Reading: [KT 7.1 - 7.3, 7.5, 7.10, 7.12]
    1. 2011-09-27 (Tuesday), 08:00-09:45. Lecture.
    2. 2011-09-29 (Thursday), 10:00-11:45. Exercise session.
  6. Network Flow & NP-completeness
      Reading: [KT 8.1 - 8.10]
    1. 2011-10-04 (Tuesday), 08:00-09:45. Lecture.
    2. 2011-10-06 (Thursday), 13:15-15:00. Lecture.
    3. 2011-10-06 (Thursday), 15:15-17:00. Exercise session.
  7. Wrap up and Review
      Reading: Old Exams
    1. 2011-10-11 (Tuesday), 08:00-09:45. Lecture.
    2. 2011-10-13 (Thursday), 13:15-15:00. Lecture.
      • Topics: Algorithms and Machine Learning, a guest lecture by Vinay Jethava
      • Location: VA
    3. 2011-10-13 (Thursday), 15:15-17:00. Exercise session.
      • Topics: Old Exams
      • Location: EB
(Slides with kind permission of Kevin Wayne @ Princeton, and Chandra Chekuri @ U. of Illinois (Urbana-Champaign).)