Introduction to Algorithms and Data Structures, Episode 4
Subject : Radix sort revisited.
Text : Read CLRS 8.3—8.4, if you had not read it last week.
Arne Andersson. Stefan Nilsson. Implementing radixsort. Journal of Experimental Algorithmics (JEA). Volume 3, 1998. Article No. 7 Year of Publication: 1998 ISSN:1084-6654. Note that you may need to be on campus to download the pdf from ACM (ITU has an institution wide registration). Feel free to skip section 3 (Adaptive Radix Sort) while reading.
Also note that the paper is accompanied by the source code of the algorithms implemented in C. The code may help you to understand intricacies of the algorithm descriptions (and you get to play with it :)).
All the pseudocode presented in the lecture is available. Please report bugs, if you see any.
Prerequisites : big-O notation, radix sort, counting sourt, bucket sort
Time : Friday, 25 Feb, 9:00–12:00, Room 2A12
Tutorial : 13:00–16:00, Room 3A14
This week's lecture is supplemented by a week assignment called Big Week Assignment 1. You should hand in your solution for Week assignment 1 no later than on 9th March at 13.00. There will be a session devoted to this week assignment during the second part of lecture, on the 20th of September, but start working on it as soon as possible.
No programming assignment this week. Work on the Major Week Assignment 1 instead.
|
|
|
|
last updated 4 Mar, 2005Anna Pagh, Andrzej Wąsowski |