# TIE-20106 Data Structures and Algorithms, 5 cr

Matti Rintala

#### Opetus

 Toteutuskerta Periodi Vastuuhenkilö Suoritusvaatimukset TIE-20106 2018-01 3 - 4 Matti Rintala The course grade is formed from points, which are earned from weekly excercises, lectures, lecture essays, online visualization assignments, and programming assignments. A minimum number of points have to be earned from each part. In addition to this, students have to pass the exam.

#### Osaamistavoitteet

After completing the course, the student knows the commonly used algorithm design techniques. The student can implement basic data structures independently, and knows how to apply related algorithms to them. The student is able to analyze the asymptotic complexity of simple programs and knows how to use library implementations to build more complex data structures.

#### Sisältö

 Sisältö Ydinsisältö Täydentävä tietämys Erityistietämys 1. Asymptotic efficiency and complexity notations. Understanding the logarithmic complexity of divide and conquer algorithms More advanced complexity analysis 2. Sorting algorithms. The difference between quadratic and O(NlogN) sorting. Different algorithms 3. Lists, hash tables and the binary search tree Red-Black tree similar data structures not as widely used 4. Programming languages' library implementations. Choosing the best alternative. Using the suitable data structure. 5. Graphs. The basic idea of graph algorithms. Breadth first search, depth first search, Dijkstra's algorithm. Other graph algorithms: Prim and Kruskal and A*. 6. Algorithm design techniques: brute force, divide and conquer, transform and concuer, randomization Greed Dynamic programming

#### Oppimateriaali

 Tyyppi Nimi Tekijä ISBN URL Lisätiedot Tenttimateriaali Book Introduction to Algorithms Cormen, Leiserson, Rivest, Stein 9780262033848 No Book Introduction to the Desing & Analysis of Algorithms. 2nd ed. Anany Levitin 0321358287 No Lecture slides Utilization of Data Structures Yes

#### Esitietovaatimukset

 Opintojakso P/S Selite TIE-02207 Programming 2: Basics Mandatory TIE-02408 Programming 3: Techniques Advisable

Tietoa esitietovaatimuksista
Students are expected to be programming literate. Programming knowledge on C++ is required (level of knowledge should be comparable to course Basic course on Programming).

#### Vastaavuudet

 Opintojakso Vastaa opintojaksoa Selite TIE-20106 Data Structures and Algorithms, 5 cr TIE-20100 Data Structures and Algorithms, 5 cr TIE-20106 Data Structures and Algorithms, 5 cr OHJ-2016 Utilization of Data Structures, 5 cr

 Päivittäjä: Rintala Matti, 28.03.2018