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: C
Department: 37 - COMPUTER SCIENCE AND ENGINEERING


Teaching language: English

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

In programs

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

Examiner:

Docent  Dag Wedelin



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

You must have done the basic course in Algorithms (or equivalent) and have a good background in discrete mathematics. You should be comfortable with a rigorous style of presentation and analysis.

Aim

The goal of the course is to develop advanced techniques in the design and analysis of algorithms. The course will continue in the spirit of the first algorithms course and maintain a rigorous analytical style. It is assumed that you are taking this course because you like the subject and you want to gain a deeper understanding of algorithms, not for a practical guide on how to implement them. Taking this course is also intended to prepare you for further research in the area. A more detailed outline of the topics to be covered can be seen in the tentative schedule of lectures below. Many of the topics are the result of recent research in algorithms: if the first course was about algorithms of the 1970's and 80's, this one is about algorithms of the 1990's and the new millennium! At some points in the course, we will also touch on frontiers of current research.

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. Grading scale: F, 3, 4 or 5.


Page manager Published: Thu 03 Nov 2022.