Kaisa_2012_3_photo by Veikko Somerpuro

16.11.2019 at 09:00 - 6.12.2019 at 23:59



Optional course.

Master's Programme in Computer Science is responsible for the course.

The course belongs to the Discrete Algorithms CSM12100 module.

The course is available to students from other degree programmes.

Basic knowledge in algorithms and data structures

Courses in the Discrete Algorithms study module.

Computes empirical entropies for given inputs. Understands entropy concepts.

Simulate coding algorithms such as Huffman, Elias-gamma, and other integer coding algorithms. Proves properties of coding algorithms.

Simulates some compression algorithms such as Lempel-Ziv and the Burrows-Wheeler transform. Proves compression efficiencies for the algorithms.

Gives a high-level explanation of some succinct data structures like rank/select dictionaries, wavelet-trees, and compressed suffix arrays. Understands the principles of the basic succinct data structures and their connections.

Recommended time/stage of studies for completion:

First or second Autumn

Term/teaching period when the course will be offered:

Second period in the Autumn every second year

The course presents the basics of information theory and introduces basic data compression techniques including entropy coding, text compression and succinct data structures.

The course does not follow any textbook.

The following is the current plan for Autumn 2017: teaching methods evolve from year to year.

There will be online lecture material, which is sufficient for independent study. Weekly lectures present the core material with additional explanations and examples.

Students are given exercise problems which require the knowledge and skills described in the learning outcomes. In weekly exercise meetings students present their solutions to the problems and discuss them with a teacher. Model solutions to the problems are provided online to support independent study.

The following is the current plan for Autumn 2019: assessment practices evolve from year to year.

The grading scale is 1...5.

One can earn up to 10 points from exercises and up to 50 points from the course exam, up to 60 points in total. Alternatively, one can earn up to 60 points from a separate exam, offered outside the course's contact teaching periods.

One should obtain 30 points to pass the course with grade 1. Grade 5 is obtained with 50 points out of the maximum 60. A linear scale is applied for other grades.

Deviations from the scheme are possible depending on the difficulty of the exam.

There will be lectures, online lecture notes, study groups, and exercises, or some subcombination of these and possibly other forms of teaching.

Some activity during the course (e.g. in the form of gathering enough exercise points and attending study groups) is required to attend the course exam.

A separate exam can be taken with independent study.