### CS250 Symbolic Computation (Fall 2003)

#### Course Prerequisites: CS142 Introduction to Computer Science II

### Course Contact Information

**Instructor**: Christino
Tamon

**Lectures**: MWF 8am SC 362

**Office hours**: MW 9-11am F
9-10 SC 373

**Contact**: SC 373, tino@clarkson.edu

**Text:** *Max Hailperin, Barbara Kaiser, Karl Knight*, **Concrete Abstractions**, Brooks/Cole (1999).

### Topical Outline

This 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 Outcomes

The 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
of programs.
- Exposure to higher-order procedures and the many abstractions that they
provide.

### Requirements and Policies

Although 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
matters.

### Grading scheme

- Final exam: 40%
- Midterm exam: 20% (date: November 5th)
- Assignments and Quizzes: 40%

### Schedule of Topics

- 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,
factorial, exponentiation,
Fibonacci sequence.

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
on functions.
- 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.

Related (relevant) sections from the text:
- 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
RSA homework.
- Chapter 5 Higher-order Procedures (except for 5.2): "functions" as
first-class objects.
- 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
Computer Graphics.

### Lab Exercises

The 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.