CS250 Symbolic Computation (Fall 2003)
Course Prerequisites: CS142 Introduction to Computer Science II
Course Contact InformationInstructor: Christino
Lectures: MWF 8am SC 362
Office hours: MW 9-11am F
9-10 SC 373
Contact: SC 373, email@example.com
Text: Max Hailperin, Barbara Kaiser, Karl Knight, Concrete Abstractions, Brooks/Cole (1999).
Topical OutlineThis course is a study of functional programming. In
previous introductory courses, a particular type of programming paradigm called
the imperative or procedural programming was studied. These two paradigms differ
in the way computation is viewed. The imperative paradigm treats computation as
operations performed on state variables; the functional paradigm treats
computation as functions operating on values. Some benefits of the
functional approach, among others, are the clean and direct approach to program
design without introducing unnecessary side-effects. Typical well-written
functional programs are easier to understand, simpler to debug, and have a
simple proof of correctness. Most functional programming languages are
interpreted (instead of compiled) and strongly supports symbolic computation (as
opposed to numerical). Recursion and higher-order functions will play an
important role in exploring symbolic computation through functional programming.
Other topics include streams (infinite list structure) and generic procedures.
This course uses the programming language Scheme, a dialect of Lisp, as the main
example of a functional programming language.
Objectives and OutcomesThe objective of this course is to introduce
students to the functional paradigm of progrmaming with some emphasis on
symbolic computation, its implications and applications, and the beautiful types
of abstractions that they provide.
The specific outcomes of this course include:
- Proficiency in programming with the interpreted programming language
Scheme in a UNIX-based environment.
- Developed good habits and skills in defensive programming.
- Familiarity with advanced uses of recursive reasoning for designing
program and data abstractions and its impact on the efficiency and correctness
- Exposure to higher-order procedures and the many abstractions that they
Requirements and PoliciesAlthough attendance is not mandatory, students
are responsible for all course materials covered in lectures and any quizzes
given during class periods. Students that need to make up missing course work
must provide the required Clarkson official exempt form. All students must
submit their own work; the exchange of ideas are encouraged but ultimately the
submitted work must be the student's own. Please refer to the Clarkson
University Regulations for more guidelines on academic integrity and related
- Final exam: 40%
- Midterm exam: 20% (date: November 5th)
- Assignments and Quizzes: 40%
Schedule of Topics
Related (relevant) sections from the text:
- Functional paradigm of programming versus procedural,
object-oriented and logical.
- Chapter 2: Basics of Scheme: S-expressions, variables and
numbers, DEFINE, LAMBDA, IF, COND. Scribe notes.
- Chapters 2-4: Types of recursions: simple/pure, tail,
fast (logarithmic), double (tree).
Some examples: addition, multiplication,
Examples of recursions on numbers and their
digits: prelude to lists. See the second lab for more information.
- Correctness: inductive proofs vs invariant-based proofs
for recursive vs iterative procedures.
- Chapter 5: Functions as first-class objects.
Passing functions as inputs and as outputs.
An example using the composition operation
- Chapter 7: Lists and their recursive manipulations:
digits, CAR/CDR, CONS, map, filter and accumulation. Some notes on lists.
- Generic procedures: sorting.
- Data abstractions: using functions and others. Objects.
- Streams and continuations.
- Chapter 2 Recursion (except for 2.4).
- Chapter 3 Iteration: tail recursive functions.
- Chapter 4 (except for 4.3): 4.2 covers modular arithmetic relevant to the
- Chapter 5 Higher-order Procedures (except for 5.2): "functions" as
- Chapter 6 Compound Data and Data Abstraction (game-playing example).
- Chapter 7 Lists: 7.6 is similar to the Skit homework.
- Chapter 9 Generic Operations: message passing style of OOP; 9.4 deals with
Lab ExercisesThe MIT Scheme
interpreter is installed on our UNIX system (crux.clarkson.edu). Follow the
above link, for more information and documentation about the MIT Scheme
interpreter. For an alternative version, there is DrScheme.