|
| Udgave: |
Efterår 2012 NAT |
| Point: |
7,5 |
| Blokstruktur: |
1. blok |
| Skemagruppe: |
C |
| Fagområde: |
dat |
| Institutter: |
Datalogisk Institut |
| Studieordning: |
Datalogi Kandidat |
| Uddannelsesdel: |
Kandidat niveau |
| Kontaktpersoner: |
Jyrki Katajainen |
| Andre undervisere: |
Rasmus Fonseca |
| Skema- oplysninger: |
 Vis skema for kurset
Samlet oversigt over tid og sted for alle kurser inden for Lektionsplan for Det Naturvidenskabelige Fakultet Efterår 2012 NAT |
| Formål: |
The purpose of this course is to build a bridge between the theory and practice in the area of data structures. One is supposed to learn to transform theoretical designs into efficient programs. |
| Indhold: |
In the first part of the course, the teachers present some theoretical results on data structures and data-structuring techniques. In the second part of the course, the students will apply the theory in practice and implement some advanced components to a program library.
We cover the basic material on advanced data structures skipped in our earlier courses (B-trees, Fibonacci heaps, van Emde Boas trees). This year we will put a special focus on: 1) data structures that are used in data-compression systems (Huffman coding, arithmetic coding) and 2) compact data structures that can be used efficiently without decompression (in-place data structures, succinct data structures, data structures for memory-constrained algorithms). |
| Målbeskrivelse: |
After the course the student should be able to
1) describe data structures and operations on them using a pseudo-code;
2) use fluently the concepts found in the literature on advanced data structures;
3) design data structures for different models of computation, including the standard random-access machine;
4) analyse the theoretical performance characteristics of data structures designed by himself and others;
5) implement advanced data structures using a concrete programming language;
6) explain the technical details of a modern program library on data structures and algorithms. |
| Lærebøger: |
Reading material expected to include: Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd Edition, The MIT Press (2009); Moffat and Turpin, Compression and Coding Algorithms, Kluwer Academic Publishers (2002); Sayood, Introduction to Data Compression, 3rd Edition, Morgan Kaufmann Publishers (2006); plus articles and extracts from other relevant books. |
| Tilmelding: |
Via KUnet from May 15th to June 1st. |
| Faglige forudsætninger: |
A course on Algorithms and data structures; knowledge of C++ programming language |
| Eksamensform: |
Course elements: active participation, 4 assignments, presentation, 2-weeks project, and written test. Submission in Absalon. Continuous evaluation: In the final grade the weight of the course elements is as follows: assignments 25%, participation and presentation 20%, project 25%, and final 4 hours written test 30%. Internal grading: according to the 7-step scale.
Re-exam: Grading is based on the same course elements; selected course elements can be reused or remade completely.
|
| Eksamen: |
Løbende evaluering.
|
| Kursus hjemmeside: |
 |
| Pensum: |
To be announced by the end of the fourth week of the teaching period
|
| Undervisnings- sprog: |
Kun engelsk
|
| Sidst redigeret: |
5/11-2012 |