All material will be added to the Moodle pages of the course (link above) during the course.
The course follows the Finnish language book Tietorakenteet ja Algorithmit by Antti Laaksonen.
The lecture notes (in English) contain all relevant information, so reading the book is not required.
The English book Introduction to algorithms by Cormen et al. covers most of the course topics (and much more) and is available as an ebook in the university library (link in Moodle).
Bachelor's Programme in Science
Compulsory in the study track in Computer and Data Science, optional for others
Basic Studies in Computer and Data Science (BSCS1000)
Course is available to students from other degree programmes
Introduction to Programming and Advanced Course in Programming and at least one course of university-level mathematics, or equivalent skill
The skill acquired during the course may be further developed in Data Structures and Algorithms Lab
After completing the course, the student
- is able to apply the basic techniques covered in the course in designing algorithms and implementing them in Java
- is able to analyse the time and space complexity of an algorithm using big-O notation and justify the correctness of an algorithm using, for example, a loop invariant
- has detailed knowledge of different implementations of a dictionary data type
- is able to implement the most important sorting algorithms and knows their time complexities
- is familiar with the basic concepts related to graphs; is able to implement the most important algorithms related to shortest paths and spanning trees
- applies the basic concepts covered in the course (e.g., dictionary, graph, sorting) as building blocks in solving more complicated computational problems; is able to pick a suitable algorithm for an application based on, e.g., time complexity.
Spring of year one for the study track of Computer Science and Data Science; optional in other study tracks
The contents of the course will be updated as needed. Central topics include
- basic techniques in designing and analysing algorithms: recursion, invariant, big-O notation, time complexity of iterative and recursive algorithms
- sorting: insertion sort, merge sort, quicksort
- basic data structures: stack, queue, list
- dictionary structures: hash table, search tree
- graphs: basic concepts, shortest paths, spanning trees.
The course consists of lectures, exercise sessions and examinations. The exercises can be solved independently, in small groups or in a session instructed by a teacher. Some of the exercises may involve computer programming. Attendance in exercise sessions may be compulsory if that is appropriate due to the chosen teaching method.
Alternatively, the course may be completed by taking a separate examination, in which case the written examination is the only component in passing the course.
The course is based on material developed at the Department of Computer Science. For additional reading, the textbook Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms is recommended.
The student familiarises himself or herself to the topic by attending lectures, studying independently the textbook and other course material and finding additional material for example on the Internet. The student's understanding is strengthened by solving exercises of varying form and difficulty, which is supported by guided exercise sessions.
Both homework exercises and written examinations contribute to the grade. The examinations have the greatest weight, but completing a given percentage of homework may be required.
The grading scale is 1-5.
- offered every Spring, whole semester (periods III-IV)
- may be offered also at other times, for example as guided self study