Study Guide

Objective

The student knows and can apply the primary data structures and algorithms. The student can compare their efficiency and complexity.

Content

- Algorithmic complexity and evaluation of the performance of algorithms: the Big O notation.
- The primary data structures and their implementations: arrays, linked lists, stacks, queues, graphs, binary trees.
- The primary algorithms and their implementations: recursion, searching and sorting.

Location and time

Computer labs at Rantavitikka Campus in spring term 2023.

Materials

Lecture materials, examples, exercises and assignments in Moodle workspace and/or OneDrive.

Course book:
Carrano F. & Henry T. 2018. Data Structures and Abstractions with Java. 5th Edition. Pearson

Recommended reading:
Goodrich M. T. & al. 2014. Data Structures and Algorithms in Java: International Student Version. 6th Edition. Wiley
Weiss M. 2012. Data Structures and Algorithm Analysis in Java: International Edition. 3rd Edition. Pearson Education

Teaching methods

Lectures and exercises 36 h, assignment and self-supervised work 99 h.

Exam schedules

No pre-defined dates. Contact the teacher for re-examinations.

Completion alternatives

Examination that may include programming tasks.

Further information

Pre-requisite: good command of at least one imperative programming language such as C/C++, C#, Python or Java. Prior knowledge of object-oriented programming is an advantage, but not required.

An introduction to some fundamental data structures of computer science: lists, stacks, queues, binary trees, and their accompanying algorithms. Principles of algorithmic analysis. The difference between recursion and iteration. In addition, there will be a brief intro / discussion of object-oriented programming in Java, if needed.

Evaluation scale

H-5

Assessment criteria, satisfactory (1)

The student can compare the complexity of algorithms and apply some basic data structures and algorithms.

Assessment criteria, good (3)

The student can compare the complexity of algorithms and apply a variety of data structures and algorithms. The student is familiar with the internal implementation of the most common data structures and algorithms.

Assessment criteria, excellent (5)

The student can evaluate the complexity of algorithms and apply a wide variety of data structures and algorithms. The students is familiar with the internal implementation of the primary data structures and algorithms. The student can choose the most effective data structures and algorithms for a given task.

Assessment methods and criteria

A large programming assignment written in Java or C#. Extra points may be given of submitting the class exercises in time.

Assessment criteria, fail (0)

The student cannot apply the basic techniques covered in the course in designing algorithms and implementing them in Java. The student cannot analyse the time and space complexity of an algorithm.

Assessment criteria, satisfactory (1-2)

The student is able to apply the basic techniques covered in the course in designing algorithms and implementing them in Java. The student can analyse the time and space complexity of an algorithm using the Big-O notation.

Assessment criteria, good (3-4)

The student has detailed knowledge of different implementations of common data structures and algorithms. The student is able to implement the most important sorting algorithms and knows their time complexities.

Assessment criteria, excellent (5)

The student can use a variety of data structures as building blocks in solving more complicated computational problems. The student is able to pick a suitable algorithm for an application based on, e.g. time complexity.