Course code: ( TIN092 , DIT600 ). Wrong Algorithms course?
Welcome to the course! Make sure to
 selfregister if you are a GU student,
 join the mailing list, where all news and announcements will be made (read what's already there),
 sync your calendar to our schedule,
 get motivated:
 read this BBC News article,
 watch the thereinmentioned TED talk (15minutes), and
 read this blog entry explaining the Amazon book incident,
 see how Google uses algorithms and maths to make billions of dollars each year,
 check who won the Nobel prize in 2012 (the creators of stable matching (lecture 1))
 buy the course book,
 solve the quiz.
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.
Shamelessly borrowed from xkcd.
More on Algorithms in media: 1, 2
Index
Course Goals
The goal of this course:
 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 realworld 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 programming assignments),
 just a collection of a few standard "push button" packages for particular problems.
Prerequisites: (Suitable courses providing this knowledge depend on the study programme)
 Programming: basic imperative programming with arrays (or pointers) and recursion.
 Data structures, such as: arrays, lists, stacks, queues, graphs.
 Mathematics: elementary logic, sets, functions, sums, recursive/inductive definitions, rules of logarithms, proofs (induction, contradiction). Wondering why? Read this and this.
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):
 Chalmers: "3": 28, "4": 36, "5": 48.
 GU: "G": 28, "VG": 48.
When determining to which extent you have obtained the course goals, we evaluate
 correctness and efficiency of your solution to exam problems, and
 quality of the presentation of said solution (which should be rigorous/logical/concrete/short/simple/tothepoint)
Observe that the bonus points cannot be used for any other exam than the one directly after the course (October 2013).
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, October 2013. (exam), (solution)
 Exam, October 2012. (exam & solution)
 Exam, October 2011. (exam)
 Exam, October 2010. (exam), (solution sketch)
 Exam, October 2009. (exam), (solution)
Exam Review
The exams are graded and 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 20131118 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."
 "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 nonfull 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 email, a time and place where we are available to discuss the matter with you. If you have not received an email from us by 20131119 at 23:59, your query is invalid.
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, including suspension from studies. Do not try it.
 We are here to help.
Course Book:
Jon Kleinberg, Eva Tardos: Algorithm Design. Published by Pearson / AddisonWesley.
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:

US Edition
 Hardcover, Printed in 2006, ISBN10: 0321295358, ISBN13: 9780321295354

Pearson International Edition
 Paperback, Printed in 2006, ISBN10: 0321372913, ISBN13: 9780321372918

Pearson New International Edition
 Paperback, Printed in 2013, ISBN10: 1292023945, ISBN13: 9781292023946
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
 Preliminaries
 Greedy algorithms
 Dynamic Programming
 Divide and Conquer
 Flow Networks
 NP Completeness
 Monday:
 08:00 Assignment n1 deadline (if n > 1)
 08:0009:45 Lecture
 Wednesday:
 10:0011:45 Lecture
 13:1515:00 Exercise session
 15:1517:00 Exercise session (repetition of previous slot)
 Friday:
 11:0012:00 Consultation
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 dropin 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
 correctness and efficiency of your solution, and
 quality of the presentation of said solution (which should be rigorous/logical/concrete/short/simple/tothepoint)
All assignments are individual (no groups). Discussing highlevel 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, email your submission to the contact person of the assignment your submission solves). Whenever you submit, we suggest you make a habit of doublechecking that the submision got submitted correctly.
The deadline for assignments is on Mondays at 08:00. 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:
 your name
 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.
 your email address
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

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 inputoutput specification given in the problem description.
 a (single) PDF file, for everything else.
 The file must be formatted for portraitmode A4paper, PDF version 1.7 compliant, and readable on the screen asis; no rotated/tilted pages, tiny/whiteonwhite text, encryption, etc.

a (single) source file, for your solution to the programming part of the problem (if any).

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 asis; 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 nontrivial claim must be supported with a rigorous justification/proof (science settles for nothing less).
 You are free to cite/reference material from the course book / slides / course notes.
 You must cite/reference if you quote material from elsewhere, or if parts of your solution are strongly based on material from elsewhere. Failure to do so constitutes as plagiarism, which we treat the same way as cheating.
A useful ruleofthumb: 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!).
 Formalize abstract details of the problem (only as needed to solve the problem),
 Solve the (formalized) problem using theory (some learned in the course),
 Prove that the solution is correct (your solution solves the problem).
 Introduce notation for a list of integers,
 Give the (pseudo)code for an algorithm which sorts the list (using the notation you introduced),
 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:
 To contact us, write us an email.
 If you wish to meet us, come to the consultation hours, or make an appointment before dropping by (we have many responsibilities beyond the course, and we need to plan/prepare our day; an unexpected interruption in our work is a setback for us).
 When emailing us: prefix the subject line with "[TIN092]" (so we can set our email server to filter incoming email relevant to the course).
 We reserve the right to ignore courserelated emails which are not prefixed with [TIN092].
 Expect >24 hour response time.
Staff
You obtain our email addresses by appending "@chalmers.se" after the content of the "Contact" entry.
Instructor
Has the following roles.

lecturer: Teaches.
 When you have questions about slides or other material presented in lectures, contact this person.

examiner: Course responsible.
 When you need special consideration for joining or passing the course, contact this person.
 ChienChung Huang
 Office: 6455
 Contact: huangch
Assistants
We each have one or more of the following roles.

administrator: Website maintainer, course planner.
 When in doubt of who to contact, contact this person.

tutor: Supervises exercise sessions.
 When you have questions relating to material and problemsolving techniques presented at a specific exercise session, contact the tutor of that session.

grader: Grades assignments.
 When you have questions concerning a specific assignment, contact to the contact person for that assignment.

fireman: Administers the Fire submission system.
 When you have questions concerning the Fire submission system, contact this person.
 Willard Rafnsson
 Role: administrator, tutor, grader
 Office: 5449
 Contact: willard.rafnsson
 Fredrik Johansson
 Role: tutor, grader, fireman
 Office: 6447
 Contact: frejohk
 Olof Mogren
 Role: tutor, grader
 Office: 6447
 Contact: mogren
 Bassel Mannaa
 Role: grader
 Office: 6103
 Contact: bassel
Student Representatives
You obtain Eugene and Robert's email address by appending "@gmail.com" after the content of their "Contact" entry.
 Eugene Groshev
 Contact: eugene.groshev
 Robert Edström
 Contact: robert.edstrom
 Christoffer Karlsson
 Contact: chrika
 Daniel Toom
 Contact: toom
General information about course evaluation at Chalmers can be found here. In short: You have some responsibility, but there is a reward.
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 email.
Schedule
(Slides with kind permission of Kevin Wayne @ Princeton, and Chandra Chekuri @ U. of Illinois (UrbanaChampaign).)
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.