Search programme

​Use the search function to search amongst programmes at Chalmers. The programme overview and the 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: 0701 - Datavetenskap DI CTH/GU


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   21 Oct 2003 pm M,  17 Jan 2004 am M,  27 Aug 2004 pm V  
0283 Laboratory 1,5 c Grading: UG   1,5 c    

In programs

TM Teknisk matematik, Year 2 (elective)
TM Teknisk matematik, Year 1 (elective)
TAUTA AUTOMATION AND MECHATRONICS ENGENEERING, Year 4 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (compulsory)
TITEA INFORMATION ENGINEERING, Year 3 

Examiner:




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   26 May 2004 pm M,  17 Jan 2004 am M,  27 Aug 2004 pm V
0283 Laboratory 1,5 c Grading: UG   1,5 c    

In programs

TM Teknisk matematik, Year 2 (elective)
TM Teknisk matematik, Year 1 (elective)
TAUTA AUTOMATION AND MECHATRONICS ENGENEERING, Year 4 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (compulsory)
TITEA INFORMATION ENGINEERING, Year 3 (elective)
TITEA INFORMATION ENGINEERING, Year 2 

Examiner:





  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.

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. Hard graph prob-lems. Implicit search trees and backtracking. Branch-and-bound. Game trees.
* 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

Brassard & Bratley: Fundamentals of Algorithmics.

Examination

Passed assigments and a written exam.


Page manager Published: Thu 03 Nov 2022.