Search course

Use the search function to find more information about the study programmes and courses available at Chalmers. When there is a course homepage, a house symbol is shown that leads to this page.

Graduate courses

Departments' graduate courses for PhD-students.

​​​​
​​

Syllabus for

Academic year
TIN092 - Algorithms
 
Syllabus adopted 2008-02-21 by Head of Programme (or corresponding)
Owner: MPALG
7,5 Credits
Grading: TH - Five, Four, Three, Not passed
Education cycle: Second-cycle
Major subject: Computer Science and Engineering, Information Technology
Department: 37 - COMPUTER SCIENCE AND ENGINEERING


Course round 1


Teaching language: English

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 No Sp
0106 Examination 7,5c Grading: TH   7,5c   21 Oct 2008 pm M,  13 Jan 2009 am V,  18 Aug 2009 pm V
0206 Laboratory 0,0c Grading: UG   0,0c    

In programs

TKDAT COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 1 (compulsory)
MPIES INTEGRATED ELECTRONIC SYSTEM DESIGN, MSC PROGR, Year 2 (elective)
MPNET NETWORKS AND DISTRIBUTED SYSTEMS, MSC PROGR, Year 2 (elective)
MPSEN SOFTWARE ENGINEERING AND TECHNOLOGY, MSC PROGR, Year 1 (compulsory)
MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR - All specializations, Year 2 (elective)

Examiner:

Univ adjunkt  Erland Holmström
Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke



Course round 2


Teaching language: English

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 No Sp
0106 Examination 7,5c Grading: TH   7,5c   25 May 2009 pm V
0206 Laboratory 0,0c Grading: UG   0,0c    

In programs

TKDAT COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (elective)
TKITE SOFTWARE ENGINEERING, Year 2 (elective)
MPIES INTEGRATED ELECTRONIC SYSTEM DESIGN, MSC PROGR, Year 1 (elective)
MPNET NETWORKS AND DISTRIBUTED SYSTEMS, MSC PROGR, Year 1 (elective)
MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR - All specializations, Year 1 (elective)

Examiner:

Univ adjunkt  Erland Holmström
Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke



Replaces

TIN090   Algorithms


  Go to Course Homepage

Eligibility:

For single subject courses within Chalmers programmes the same eligibility requirements apply, as to the programme(s) that the course is part of.

Course specific prerequisites

An introductory course in data structures and elementary knowledge in discrete mathematics.

Aim

The algorithms course revolves around three central questions that appears naturally when one wants to use a computer to compute a problem:

  • Is the problem computationally solvable at all?
  • How can we do it?
  • How fast can the solution be?

The course shall provide basic knowledge and methods to answer these types of question as precisely as possible, and improve the ability to write fast and well-founded programs.


Other important aspects are: to improve the intuitive sense of time complexity of problems and algorithms in general, to show how the choice of data structures can influence speed of a program, and how data structures must be adapted to algorithms.


The most important goal of the course is to give general principles of creating good algorithms for new problems for which you cannot find any published algorithm.

Learning outcomes (after completion of the course the student should be able to)

After attending the course you will be able to:

  • Model problems: Formulate a clear mathematical model of real world problems.
  • Design algorithms: Construct algorithms with several algorithm design methods
    and be able to choose appropriate data structures and abstractions.
  • Describe your algorithms and their qualities to others.
  • Prove correctness: Prove that your algorithms are correct.
  • Analyse algorithms: perform an objective evaluation of the performance and be able to compare it to other algorithms performance.
  • Recognize intractable problems and other classes of problems like P, NP, NPC
  • Recognize a number of specific algorithms for basic problems which tend to appear over and over again in different applications

You will also know something about

  • Problem analysis: how to analyse the complexity of a problem e.g. how much
    resources are require to solve a problem.
  • Approximation algorithms: how to solve problems with exponential complexity.

However, be aware that this is not a course in programming! The main focus is on the design of algorithms from a given problem specification and the analysis of efficiency of these algorithms. This is, so to speak, the analytical work that has to be done before writing any line of code, if one wants to solve a new problem with the help of computers.

Content

The course topics are as follows:

  • Introduction. What is an algorithm? Description of algorithms. What is an efficient algorithm?
  • Tools for analysis of algorithms. O-notation. Analyzing loops and recursive calls. Amortized analysis. Solving recurrences.
  • Data structures and algorithms. Review of basic data structures. Combining data structures. Merge-and-find.
  • Graph algorithms.
  • Greedy algorithms.
  • Dynamic programming.
  • Divide-and-conquer.
  • Backtracking and Implicit search trees. Branch-and-bound.
  • Introduction to local search and approximation algorithms.
  • Basic complexity theory. Complexity classes P, NP, and NPC, reductions. Examples of NP-complete problems. NP-hard problems. Coping with hard problems.
  • Short introduction to other design techniques: local search, approximation algorithms, randomized algorithms, preprocessing band network flow.

Organisation

The course is given as lectures, combined with tutorial groups for problem solving related to the course and programming exercises (laboration) and a number of assignments intended to develop the skill of analyzing and designing algorithms.

Literature

Information about literature is given on the course homepage before course start.

Examination

Examination consist of two parts: written exam and laboration.
To pass the course you have to finish both these parts during the course (within one year from course start).


Page manager Published: Thu 04 Feb 2021.