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
TIN093 - Algorithms  
 
Syllabus adopted 2017-02-20 by Head of Programme (or corresponding)
Owner: MPALG
7,5 Credits
Grading: TH - Five, Four, Three, Fail
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
Maximum participants: 185

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 Summer course No Sp
0114 Examination 7,5 c Grading: TH   7,5 c   21 Oct 2017 pm SB_MU,  20 Dec 2017 am M,  30 Aug 2018 pm SB_MU

In programs

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

Examiner:

Bitr professor  Peter Damaschke


Course round 2

The course in sp4 is full. No additional course registrations can be offered.
Teaching language: English
Open for exchange students
Block schedule: A+

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 Summer course No Sp
0114 Examination 7,5 c Grading: TH   7,5 c   30 May 2018 am M,  20 Dec 2017 am M,  30 Aug 2018 pm SB_MU

In programs

MPEES EMBEDDED ELECTRONIC SYSTEM DESIGN, MSC PROGR, Year 1 (elective)
MPENM ENGINEERING MATHEMATICS AND COMPUTATIONAL SCIENCE, MSC PROGR, Year 1 (compulsory elective)
MPENM ENGINEERING MATHEMATICS AND COMPUTATIONAL SCIENCE, MSC PROGR, Year 2 (elective)
MPSOF SOFTWARE ENGINEERING AND TECHNOLOGY, MSC PROGR, Year 1 (compulsory elective)
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 1 (elective)
TKDAT COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)
TKITE SOFTWARE ENGINEERING, Year 2 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (elective)

Examiner:

Univ adjunkt  Erland Holmström


Replaces

TIN090   Algorithms TIN092   Algorithms


  Go to Course Homepage

Eligibility:


In order to be eligible for a second cycle course the applicant needs to fulfil the general and specific entry requirements of the programme that owns the course. (If the second cycle course is owned by a first cycle programme, second cycle entry requirements apply.)
Exemption from the eligibility requirement: Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling these requirements.

Course specific prerequisites

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)

  1. Knowledge and understanding
    • describe your algorithms and their qualities: explain algorithms in writing, so that others can understand how they work, why they are correct and fast, and where they are useful.
    • recognize that non-trivial computational problems, which need to be solved by algorithms, appear in various real-world computer applications and to formalize them.
    • intractability: recognize intractable problems and other classes of problems like P, NP, NPC.
    • prove the correctness of algorithms.

  2. Skills and abilities
    • design: apply the main design techniques for efficient algorithms (for instance greedy, dynamic programming, divide-and-conquer, backtracking, heuristics) to problems which are similar to the textbook examples but new.
    • perform the whole development cycle of algorithms: problem analysis, choosing, modifying and combining suitable techniques and data structures, analysis of correctness and complexity, filling in implementation details, looking for possible improvements, etc.
    • perform simple reductions between problems, explain NP completeness, recognize various computationally hard problems which tend to appear over and over again in different applications, cope, at least in principle, with computationally hard problems, using heuristics, refinements of exhaustive search, approximative solutions, etc.
    • implement algorithms properly and evaluate them in theory and experiment.

  3. Judgement and approach
    • critically assess algorithmic ideas and demonstrate the ability to resist the temptation to create obvious and seemingly plausible algorithms (which often turn out to be incorrect).
    • analyse: explain why the time efficiency of algorithms is crucial, express the time complexity in a rigorous and scientifically sound manner, analyze the time complexity of algorithms (sum up operations in nested loops, solve standard recurrences, etc.) i.e. perform an objective evaluation of the performance and be able to compare it to other algorithms performance.
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 efficient algorithm?
  • Tools for analysis of algorithms. O-notation. Analyzing loops and recursive calls. Solving recurrences.
  • Data structures and algorithms. Review of basic data structures.
  • Combining data structures. Merge-and-find.
  • Graph algorithms.
  • Greedy algorithms.
  • Divide-and-conquer.
  • Dynamic programming.
  • Backtracking and Implicit search trees. Branch-and-bound.
  • Short introduction to local search and approximation algorithms.
  • Basic complexity theory. Complexity classes P, NP, and NPC, reductions. Examples of NP-complete problems. Coping with hard problems.
  • Short introduction to other design techniques: local search, approximation algorithms, randomized algorithms, pre-processing, network flow.

Organisation

The course is given as lectures, combined with tutorial groups for problem solving related to the course 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

The course is examined by an individual written hall-exam.


Page manager Published: Thu 04 Feb 2021.