Syllabus for |
|
| 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, |
Contact examiner |
In programs
DCMAS MSc PROGR IN DEPENDABLE COMPUTER SYSTEMS - Dependable Programming, Year 1
DCMAS MSc PROGR IN DEPENDABLE COMPUTER SYSTEMS - Dependable Architectures, Year 1 (elective)
TM Teknisk matematik, Year 2 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING - Algorithms, Year 4 (compulsory)
TTFYA ENGINEERING PHYSICS, Year 4 (elective)
TAUTA AUTOMATION AND MECHATRONICS ENGENEERING, Year 4 (elective)
TITEA SOFTWARE ENGINEERING, Year 4 (elective)
TITEA SOFTWARE ENGINEERING, Year 3 (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.