Welcome to the course! Make sure to
- self-register 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 therein-mentioned TED talk (15-minutes), 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.
- Course Goals
- Course Book
- Course Model
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 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 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.
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/to-the-point)
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"
- 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)
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 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."
- "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.
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.
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:
- 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).
Generally, each week n of the course has a major theme. The themes are
- Greedy algorithms
- Dynamic Programming
- Divide and Conquer
- Flow Networks
- NP Completeness
- 08:00 Assignment n-1 deadline (if n > 1)
- 08:00-09:45 Lecture
- 10:00-11:45 Lecture
- 13:15-15:00 Exercise session
- 15:15-17:00 Exercise session (repetition of previous slot)
- 11:00-12: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.
Here the lecturer teaches ideas and techniques related to the theme of the week the lecture occurs in.
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.
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.
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.
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/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 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.
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 e-mail address
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 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.
- a (single) source file, for your solution to the programming part of the problem (if any).
be submitted, electronically,
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.
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).
- 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 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?
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).
Your grade and feedback is provided through the Fire system.
- To contact us, write us an e-mail.
- 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 e-mailing us: prefix the subject line with "[TIN092]" (so we can set our e-mail server to filter incoming e-mail relevant to the course).
- We reserve the right to ignore course-related e-mails which are not prefixed with [TIN092].
- Expect >24 hour response time.
You obtain our e-mail addresses by appending "@chalmers.se" after the content of the "Contact" entry.
Has the following roles.
- 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.
- Chien-Chung Huang
- Office: 6455
- Contact: huangch
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 problem-solving 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
You obtain Eugene and Robert's e-mail 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.
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.
(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.