Search programme

​Use the search function to search amongst programmes at Chalmers. The study programme and the study programme syllabus relating to your studies are generally from the academic year you began your studies.

Syllabus for

Academic year
TIN092 - Algorithms
 
Syllabus adopted 2013-02-09 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
Open for exchange students
Block schedule: A

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 Summer course No Sp
0106 Examination 7,5 c Grading: TH   7,5 c   26 Oct 2013 pm H,  13 Jan 2014 pm M,  27 Aug 2014 pm V
0206 Laboratory 0,0 c Grading: UG   0,0 c    

In programs

MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 1 (compulsory)
TKDAT COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (elective)
MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Year 2 (elective)
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 2 (elective)
MPEES EMBEDDED ELECTRONIC SYSTEM DESIGN, MSC PROGR, Year 2 (elective)
MPSOF SOFTWARE ENGINEERING, MSC PROGR, Year 2 (elective)

Examiner:

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



Course round 2


Teaching language: English
Open for exchange students
Block schedule: A

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 Summer course No Sp
0106 Examination 7,5 c Grading: TH   7,5 c   28 May 2014 am V,  27 Aug 2014 pm V
0206 Laboratory 0,0 c Grading: UG   0,0 c    

In programs

TKDAT COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (elective)
TKITE SOFTWARE ENGINEERING, Year 2 (elective)
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 1 (elective)

Examiner:

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



Replaces

TIN090   Algorithms

Course evaluation:

http://document.chalmers.se/doc/271ffdfc-919a-46f9-b4a8-93ee535103e7


  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

The requirement for the course is to have successfully completed two years with the subject Computer Science or equivalent. Particularly relevant are an introductory course in data structures and 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 written exam and assignments, both teorethical
and practical (i.e. programming).
The assignments will give bonus points on the exam.


Page manager Published: Mon 28 Nov 2016.