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
TIN090 - Algorithms
 
Owner: TDATA
4,0 Credits (ECTS 6)
Grading: TH - Five, Four, Three, Not passed
Level: A
Department: 37 - COMPUTER SCIENCE AND ENGINEERING


Course round 1


Teaching language: Swedish

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 No Sp
0183 Examination 2,5 c Grading: TH   2,5 c   18 Oct 2005 pm V,  14 Jan 2006 am V,  29 Aug 2006 am V
0283 Laboratory 1,5 c Grading: UG   1,5 c    

In programs

TM Teknisk matematik, Year 2 (elective)
TITEA SOFTWARE ENGINEERING - Software development and management, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Data communication, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Embedded systems, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Interaction design, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Interactive simulations, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Bioinformatics, Year 4 
TITEA SOFTWARE ENGINEERING, Year 3 
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (compulsory)
TAUTA AUTOMATION AND MECHATRONICS ENGENEERING, Year 4 (elective)

Examiner:

Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke



Course round 2


Teaching language: Swedish

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 No Sp
0183 Examination 2,5 c Grading: TH   2,5 c   23 May 2006 am V,  14 Jan 2006 am V
0283 Laboratory 1,5 c Grading: UG   1,5 c    

In programs

TM Teknisk matematik, Year 2 (elective)
TITEA SOFTWARE ENGINEERING - Software development and management, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Data communication, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Embedded systems, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Interaction design, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Interactive simulations, Year 4 (elective)
TITEA SOFTWARE ENGINEERING - Bioinformatics, Year 4 
TITEA SOFTWARE ENGINEERING, Year 2 
TITEA SOFTWARE ENGINEERING, Year 3 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (compulsory)
TAUTA AUTOMATION AND MECHATRONICS ENGENEERING, Year 4 (elective)

Examiner:

Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke




Eligibility:

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

Aim

The algorithms course revolves around three central questions that naturally appear if one wants a computer to do something:
* Is the problem computationally solvable at all?
* How can it work?
* How fast can the solution be?
The course shall provide basic knowledge and methods to answer these types of question as pre-cisely as possible, and improve the ability to write fast and well-founded programs.
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.
Other important aspects are: to improve the intui-tive sense of time complexity of problems and algo-rithms 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. Moreover, we go through a number of specific algorithms for basic problems which tend to appear over and over again in different applications. How-ever, 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.

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.
* Greedy algorithms. General scheme and examples.
* Divide-and-conquer. General scheme and examples
* Dynamic programming. General scheme and examples.
* Basic complexity theory. Complexity classes P, NP, and NPC, reductions. Satisfiability of Boolean formulae and Cook's Theorem. Examples of NP-complete problems. NP-hard problems. Coping with hard problems.
* Graph traversal and search. Depth-first- and breadth-first-search. Examples. Implicit search trees and backtracking. Branch-and-bound.
* Local search. General scheme and examples.
* Other design techniques. Randomized algorithms. Linear and integer programming. Preprocessing. Dynamic algorithms. Faster implementation of basic algorithms.

Organisation

The course contains one programming exercise (laboration) and a number of assignments intended to develop the skill of analyzing and designing algorithms yourself. See the course home page for the most up to date information.

Literature

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

Examination

Passed assigments and a written exam.


Page manager Published: Mon 28 Nov 2016.