Opening of the academic year

Event type: 
Other event
Event time: 
06.09.2013 - 13:00 - 15:30
Place: 
Exactum, Linus Torvalds Auditorium B123, ground floor
Description: 

We would like to welcome you to the opening of the Computer Science Department’s new academic year on Friday 6 September!

PROGRAMME:

At 13:00

Welcoming words from Esko Ukkonen, head of the department

Lecture by Professor Bengt Aspvall: "Sorting Algorithms As Special Cases Of A Priority Queue Sort" *

Place: Exactum/ Linus Torvalds auditorium, ground floor

At 14:00 >

NOTE: Refreshments at Exactum roof terrace, 4 floor

We hope to see you there!

* Sorting Algorithms As Special Cases Of A Priority Queue Sort

We revisit the main sorting algorithms in a novel way. Our approach offers a review and exercise after the algorithms have been taught to students. It is done in a way that emphasizes relationships between the sorting algorithms, and shows how considering abstraction and extreme cases can lead to the generation of new algorithms.

A number of authors (including textbook authors) have noted particular relationships between algorithms, such as an uneven split in merge sort being equivalent to insertion sort. We use a flexible priority queue, the d-heap, to derive three common sorting algorithms. We combine this with using a binary search tree as a priority queue, plus prior observations in the literature, to show strong relationships between the main sorting algorithms that appear in textbooks.

Using this approach students are able to revisit a number of algorithms and data structures and explore elegant relationships between them. This approach can also lead to exercises and exam questions that go beyond desk-checking to evaluate students’ understanding of these algorithms.(based on Bell & Aspvall, SIGCSE 2011)

06.09.2013 - 12:14 Pauliina M J Pajunen
15.05.2013 - 13:55 Pauliina M J Pajunen