Syllabus for |
|
| 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
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (compulsory)
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
TM Teknisk matematik, Year 2 (elective)
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
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (compulsory)
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)
TM Teknisk matematik, Year 2 (elective)
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.