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
TDA250 - Algorithms, advanced course
 
Owner: TDATA
4,0 Credits (ECTS 6)
Grading: TH - Five, Four, Three, Not passed
Level: A
Department: 0701 - Datavetenskap DI CTH/GU


Teaching language: Swedish

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 No Sp
0198 Examination 4,0 c Grading: TH   4,0 c    

In programs

TTFYA ENGINEERING PHYSICS, Year 4 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING - Algorithms, Year 4 (compulsory)
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)
DCMAS MSc PROGR IN DEPENDABLE COMPUTER SYSTEMS - Dependable Architectures, Year 1 (elective)
DCMAS MSc PROGR IN DEPENDABLE COMPUTER SYSTEMS - Dependable Programming, Year 1 
TM Teknisk matematik, Year 1 (elective)
TM Teknisk matematik, Year 2 (elective)
TAUTA AUTOMATION AND MECHATRONICS ENGENEERING, Year 4 (elective)

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.

Course specific prerequisites

A basic course in algorithms.

Aim

This course describes some different algorithmic areas that are not normally covered in a basic data structure or algorithms course. The lectures cover discrete algorithms for strings, search, graphs etc. and consider both theoretical subjects like comp-lexity theory, as well as more applied subjects like algorithm libraries. An important part of the course is a project, where it is possible to specialize in a certain area, and get in contact with recent re-search. On the whole, taking this course will give a good insight and overview of algorithmics.

Content

The lectures cover the following topics:
* String algorithms. String matching, string distan-ces, tries, suffix trees.
* Fundamental algorithms/ algorithm libraries. STL, LEDA. Possibly something about other libraries. Balanced search trees and random treaps.
* Data compression. Huffman coding, arithmetic coding, Lempel-Ziv, Burrows-Wheeler transform. Image compression (JPEG).
* Advanced search algorithms. Constraint programming: basic modelling, constraint satisfaction, constraint propagation. Advanced local search: tabu search, simulated annealing, genetic algorithms. Heuristic search A*.
* Graph algorithms. Overview of different kinds of graph problems. Something about network flow and matching. Graph planarity. Graph coloring.
* Complexity theory. Turing machines. Basic theory revisited. Proof that SAT is NP-complete. Examples of transformations.
* Project discussions. The last week is spent discussing the results of the projects.
If time allows we may also briefly consider:
* Parallel algorithms. Different machine models. Different kinds of parallelism and algorithm design techniques. Sorting in parallel.
* Algorithmic geometry. Different problems. Line intersection, convex hull.
In the project you are free to do almost whatever you like, related to algorithms. We have prepared several suggestions, but you are also free to come up with your own. You can work in a group that you choose yourself.
See the course homepage for the most up to date information.

Literature

Collected papers from different sources.

Examination

Passed project report and an individual summarizing report describing the contents of the lectures.


Page manager Published: Thu 03 Nov 2022.