Kaisa_2012_3_photo by Veikko Somerpuro

Enrol
9.12.2019 at 09:00 - 28.4.2020 at 23:59

Timetable

Here is the course’s teaching schedule. Check the description for possible other schedules.

DateTimeLocation
Tue 14.1.2020
12:15 - 14:00
Wed 15.1.2020
14:15 - 16:00
Tue 21.1.2020
12:15 - 14:00
Wed 22.1.2020
14:15 - 16:00
Tue 28.1.2020
12:15 - 14:00
Wed 29.1.2020
14:15 - 16:00
Wed 29.1.2020
16:15 - 18:00
Tue 4.2.2020
12:15 - 14:00
Wed 5.2.2020
14:15 - 16:00
Tue 11.2.2020
12:15 - 14:00
Wed 12.2.2020
14:15 - 16:00
Tue 18.2.2020
12:15 - 14:00
Wed 19.2.2020
14:15 - 16:00
Tue 25.2.2020
12:15 - 14:00
Wed 26.2.2020
14:15 - 16:00
Mon 9.3.2020
12:15 - 14:00
Tue 10.3.2020
10:15 - 12:00
Wed 11.3.2020
12:15 - 14:00
Mon 16.3.2020
12:15 - 14:00
Tue 17.3.2020
10:15 - 12:00
Mon 23.3.2020
12:15 - 14:00
Tue 24.3.2020
10:15 - 12:00
Mon 30.3.2020
12:15 - 14:00
Tue 31.3.2020
10:15 - 12:00
Mon 6.4.2020
12:15 - 14:00
Tue 7.4.2020
10:15 - 12:00
Mon 20.4.2020
12:15 - 14:00
Tue 21.4.2020
10:15 - 12:00
Mon 27.4.2020
12:15 - 14:00
Tue 28.4.2020
10:15 - 12:00

Material

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).

Description

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

Jyrki Kivinen