CS 5010: Module 12
Module Overview
In this module, we will examine how efficiency is related to programming style, programming languages, and how programming languages are implemented.
These matters are largely unrelated to algorithmic complexity, so they are seldom discussed in courses on algorithms and data structures. Programmers often form opinions based on what they have heard from other programmers or have read on the World-Wide Web, which are not particularly reliable sources. As it turns out, much of the conventional wisdom concerning programming style and efficiency is misleading or, in some cases, quite wrong.
Readings
No required readings.
Resources
- Examples for Module 12
- Brian W Kernighan and Christopher J Van Wyk. Timing trials, or the trials of timing: experiments with scripting and user-interface languages. Software—Practice & Experience, 28(8), 10 July 1998, pages 819-843.
- William D Clinger. Proper tail recursion and space efficiency. Proceedings of the 1998 ACM Conference on Programming Language Design and Implementation, June 1998, pages 174-185.
- William D Clinger, Anne H Hartheimer, and Eric M Ost. Implementation strategies for first-class continuations. Journal of Higher Order and Symbolic Computation, 12(1), 1999, pages 7-45.
- Benjamin Zorn. The measured cost of conservative garbage collection. Software—Practice & Experience, 23(7), July 1993, pages 733-756.
- Mitchell Wand and William D Clinger. Set constraints for destructive array update optimization. Proceedings of the IEEE International Conference on Computer Languages, April 1998, pages 184-193.
Examples will be added soon.
Lessons
The material of this module will be covered by lecture, demonstrations, and a problem set. Online lessons will be added below as time permits.
- Lesson 12.1: Efficiency and Other Myths
- Lesson 12.2: Recursion vs Iteration
- Lesson 12.3: Stack Overflow vs Heap Overflow (to appear)
- Lesson 12.4: Garbage Collection vs Explicit Deallocation
- Lesson 12.5: Aggregate Update Problem (to appear)
- Lesson 12.6: Compiler Optimization and Why It Matters
Problem Set
Problem Set 12 was assigned on Monday, 10 April.