NotesFAQContact Us
Collection
Advanced
Search Tips
Peer reviewed Peer reviewed
PDF on ERIC Download full text
ERIC Number: EJ1064321
Record Type: Journal
Publication Date: 2011
Pages: 8
Abstractor: As Provided
Reference Count: 12
ISBN: N/A
ISSN: ISSN-1648-5831
A Didactic Analysis of Functional Queues
Rinderknecht, Christian
Informatics in Education, v10 n1 p65-72 2011
When first introduced to the analysis of algorithms, students are taught how to assess the best and worst cases, whereas the mean and amortized costs are considered advanced topics, usually saved for graduates. When presenting the latter, aggregate analysis is explained first because it is the most intuitive kind of amortized analysis, often involving enumerative combinatorics. We show how the aggregate analysis of functional queues can be carried out accurately and graphically, without combinatorics nor analytical tools like asymptotics, hence making it amenable to undergraduates. Our presentation is independent of any programming language.
Vilnius University Institute of Mathematics and Informatics, Lithuanian Academy of Sciences. Akademjos str. 4, Vilnius LT 08663 Lithuania. Tel: +37-5-21-09300; Fax: +37-5-27-29209; e-mail: info@mii.vu.lt; Web site: http://www.mii.lt/informatics_in_education/
Publication Type: Journal Articles; Tests/Questionnaires; Reports - Descriptive
Education Level: Higher Education; Postsecondary Education
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A