Algorithms
, autumn 2014

Course code: ( TIN093 , DIT600 , (prev. TIN092) ).
Wrong Algorithms course?

Announcements

Show previous announcements

Course announcements are made in the Google Group associated with this course. The group functions as a mailing list; after joining the group, you will receive course announcements by e-mail.

Link to the Fire system.

Index

  1. Welcome
  2. Course Goals
  3. Evaluation
    1. Sample Exams
    2. Cheating
  4. Course Book
  5. Course Model
  6. Assignments
    1. Validity
  7. People
  8. Announcements
  9. Schedule

Welcome


Shamelessly borrowed from xkcd.

Make sure to

  1. self-register if you are a GU student,
  2. join the mailing list, where all news and announcements will be made (read what's already there),
  3. sync your calendar to our schedule,
  4. get motivated:
    1. read this BBC News article,
    2. watch the therein-mentioned TED talk (15-minutes), and
    3. read this blog entry explaining the Amazon book incident,
    4. see how Google uses algorithms and maths to make billions of dollars each year,
    5. check who won the Nobel prize in 2012 (the creators of stable matching (lecture 1))
  5. buy the course book,
  6. solve the quiz.
We also suggest you read this page once, so you know what you are in for (~3 pages of A4 text).

Tip: Bookmark a link straight to the schedule. It contains most of what you need when you visit this page.

Tip: This page contains all course information. Try the "Find" function in your browser to find things.

Tip: Still have trouble finding course material or submitting assignments? See this howto video.

More on Algorithms in media: 1, 2

Course Goals

The goal of this course:

This course is not:

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

Evaluation

To pass the course, you (only) 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 6 bonus points to the score on your written exam in October 2014 by solving weekly assignments.

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 assignments the same way, we urge you to participate in them, so you have a better impression of what is expected of you (and thus are more likely to pass the exam).

Observe that the bonus points can be used during one academic year.

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

Exam Review

Date of exam review: To be determined

available for your review in the CSE Student Office ("Studieexpedition").

If you decide you want to query the grading of your exam submission, then do not remove your exam submission from the student office. Fill in this form by 2013-11-18 so we know which exams/problems to look at.

For us to consider your grading query, the query needs to be concrete and well justified. For instance, the following are not valid queries.

  • "My solution is correct, but I did not get a full score."
  • "The grade I got for this part is too low."
  • "I need a higher grade to pass."
Instead, your query should be along the following lines:
  • "The feedback indicates an omitted induction hypothesis, yet it is clear from the inductive step what the inductive hypothesis is [specify it]."
  • "My algorithm follows the same idea as the one given in the exam solution [summarise your approach]. However, I do not get a full grade, and it is not clear to me, or from the feedback, how my deviation from the exam solution justifies a non-full grade."
  • "While my algorithm differs from the one in the exam solution [summarise your approach], it does solve the problem [explain why], and runs within the required amount of time [explain why], yet I did not get full points."

If your query is valid, then you will receive, by e-mail, a time and place where we are available to discuss the matter with you. If you have not received an e-mail from us by 2013-11-19 at 23:59, your query is invalid.

Cheating

Short version: Don't.

Long version: Sadly, some serious remarks must be added here:

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

Cheating can lead to severe consequences, including suspension from studies. Do not try it.

If you have major difficulties achieving the course goals, 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. Published by Pearson / Addison-Wesley.

The "dream textbook", written by two of the foremost researchers and teachers in the field. It should be available at Cremona for ~660 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.

The book comes in several editions, all of which are valid. From left to right, these are:

If you find an edition of the book which we have not listed, then contact the course administrator; he will find out whether it is valid, just in case.

We refer to course book content using the following notation: [KT c.x], where c is the chapter number, and x is either a section number, or an exercise number (depending on context).

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. NP Completeness
The pattern of supervised sessions and deadlines for week n, for n > 1 (week 1 is abnormal; see the schedule), is as follows.

There should only be one active theme in lectures and exercise sessions during each week n. (we did our best to minimise the number of concurrent course themes, given our constraints and resources)

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

All course material (assignments, slides, exercise session notes, and so on) is located in the schedule.

Lectures

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

Exercise Sessions

Here a tutor demonstrates how to apply these ideas and techniques to solve problems, and, if time allows, will tutor you while you try this out yourself on exercises and assignments.

Consultation

Here, a tutor is available for drop-in questions involving assignments. If many students show up, more time can be added, or appointments can be booked for those that require further assistance. Please respect the lunch break starting at 12:00.

Lab Sessions?

The TimeEdit schedule has lab session slots, intended for solving assignments. The sessions are unsupervised and no lab is booked, so where you do them is up to you. If you need assistance, contact the contact person for the assignment you are working on in a timely fashion.

Assignments

There are 6 assignments in this course, one each week. The assignments are not compulsory, but they yield bonus points towards the exam. Each assignment consists of two problems. Each problem contains either a written part, programmed part, or both. Each assignment is graded on a scale from 0 to 10. At the end of the course, the bonus points on the exam are calculated as follows: BonusPoints = 0.1 * (sum of grades from assignments). Thus, up to 6 bonus points can be obtained throughout the course.

When grading your assignments, 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)

All assignments are individual (no groups). Discussing high-level ideas with fellow students is permitted (and encouraged!), but any concrete solution must be worked and written by you alone. Failure to comply with this constitues as cheating, for all parties involved.

We take no responsibility in the event that your submission does not reach us, such as when a physical page is lost, your files disappear, or when technical problems prevent an electronic submission from reaching the Fire system (in the latter case, e-mail your submission to the contact person of the assignment your submission solves). Whenever you submit, we suggest you make a habit of double-checking that the submision got submitted correctly.

The deadline for assignments is on Mondays at 23:59. We do not extend deadlines, and there are no resubmissions.

You will find the assignments embedded in the schedule under the weekly topic event.

ID

We need three things to be able to associate your submission to you, and thus award you bonus points:

  1. your name
  2. your personnummer
    • If you do not have a personnnummer, use instead YYMMDD0000, where YY are the last two digits of your year of birth, MM is your month of birth, and DD is your date of birth.
  3. your e-mail address
We refer to these three things together as your ID. Perform all submissions under the same ID.

Validity

Failure to comply with any of these requirements invalidates your submission, in part or in full.

For a submission for a problem in an assignment to be valid, it must

  1. consist of one or both of the following files (and nothing else):
    • a (single) source file, for your solution to the programming part of the problem (if any).
      • Permitted programming languages: C, C++, C#, Java, Python.
      • The program must compile. Program input/output must go via standard streams (stdin/stdout), and must strictly satisfy the input-output specification given in the problem description.
    • a (single) PDF file, for everything else.
      • The file must be formatted for portrait-mode A4-paper, PDF version 1.7 compliant, and readable on the screen as-is; no rotated/tilted pages, tiny/white-on-white text, encryption, etc.
  2. be submitted, electronically, in Fire, before the deadline.
    • Submit a solution to Assignment m Problem n to the Fire system entry named AmPn.
    • Upload the files as-is; do not compress or encrypt them.
    • Use the dotted lines (when present) drawn on the assignment as an indicator for how much detail to include in an answer (solutions which would clearly not fit in the space on the assignment are invalid). (You don't have to write in the space by hand and scan the result; you can deliver a PDF rendering of your solution written in plaintext, LaTeX, even Word).
    • When creating a user account in Fire, provide your ID. Use this one user account for all submissions you make to Fire.

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 with your real name on it, on the web, in a book, or in a research paper?

Guidelines

To get an impression of the level of detail expected, see solutions to the sample exams (the solution to Problem 1 a) and b) on the October 2009 requires no skills taught by this course, and thus can give you a full impression immediately).

We recommend writing a rough sketch of a solution on scratch paper, and then write (only) the complete solution in your assignment submission.

The general strategy for solving an assignment 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 (pseudo)code 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).

Feedback

Your grade and feedback is provided through the Fire system.

People

Please note:

Staff

You obtain our e-mail addresses by appending "@chalmers.se" after the content of the "Contact" entry.

Instructor

Has the following roles.

Assistants

We each have one or more of the following roles.

Student Representatives

Schedule

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

The schedule, along with handouts (slides, assignments, etc.), is given in the Google Calendar associated with the course:

This schedule supersedes the TimeEdit schedule (particularly relevant in the first week of the course). The schedule is likely to change (ours is an evolving course). Weekly reading should be pinned 1 week in advance, and concrete session topics pinned 3 working days in advance. The weekly themes, and the time slots, are fixed, however; in the unlikely event that time slots, or the general course plan, change, an announcement will be made through the mailing list associated with the course.