CS 146: Elementary Algorithm Design and Data Abstraction (Advanced Version)

Course Philosophy

CS 146, like CS 145, emphasizes a highly conceptual approach, independent learning, and intellectual challenge for students with good mathematical abilities. In CS 145, this was accomplished by the use of the functional programming language Racket, a modern descendant of one of the earliest programming languages that still survives, namely Lisp.

But a concurrent thread of development, as old and also continuing into the present, involved imperative languages, which historically were not only thinner abstractions over actual machine details, but also offered weaker abstraction mechanisms to programmers. These type of programming languages dominated primarily for performance reasons.

The relevance and accuracy of algorithm design and analysis (for both the functional and imperative paradigms) depends on understanding machine details, at least in part. These details also help explain many current programming practices. In CS 146, we will examine the imperative paradigm, and compare and contrast the way that efficient algorithms and data structures are designed in imperative and functional languages. We'll do this both by using imperative features in Racket and by studying the design of languages such as C which lack functional features. We'll connect the two spheres by discussing how to implement an interpreter for a functional language in an imperative language.

Racket is a laboratory for current research on aspects of functional programming languages, and we will continue to look at interesting topics in this area, perhaps at the cost of some coherency in the flow of material.


Last modified on Monday, 09 December 2013, at 14:11 hours.