Study Guide 2015-2016

TIE-20106 Data Structures and Algorithms, 5 cr

Person responsible

Terhi Kilamo, Matti Rintala

Lessons

Implementation 1: TIE-20106 2015-01

Study type P1 P2 P3 P4 Summer
Lectures
Excercises
Assignment
Online work




 




 
 2 h/week
 2 h/week
 35 h/per
 1 h/week
+2 h/week
+2 h/week
+35 h/per
+1 h/week




 

Lecture times and places: Thursday 10 - 12 TB111

Requirements

Enough points must be earned from weekly excercises, lectures, lecture essays, online visualization assignments, and programming assignments. Exam.
Completion parts must belong to the same implementation

Learning Outcomes

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

Content

Content Core content Complementary knowledge Specialist knowledge
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 

Instructions for students on how to achieve the learning outcomes

Passed homework assignments and the exam together define the final grade.

Assessment scale:

Numerical evaluation scale (1-5) will be used on the course

Partial passing:

Completion parts must belong to the same implementation

Study material

Type Name Author ISBN URL Additional information Examination material
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   

Additional information about prerequisites
Students are expected to be programming literate.



Correspondence of content

Course Corresponds course  Description 
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  

Last modified 15.01.2016