### Timetable

### 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