Course Overview

| CS 100 Home |

Synopsis

An introduction to elementary computer programming concepts. Emphasis is on techniques of problem analysis and the development of algorithms and programs. The subject of the course is programming, not a particular programming language. The principal programming language is Java. A brief introduction to Matlab is included. The course does not presume previous programming experience. Programming assignments are tested and run on PC's.
 

Philosophy

See the article Building Freshman Intuition for Computational Science and Mathematics by C. Van Loan.

 

Topics

Here is a summary of course concepts.

1. Language Concepts

The following language concepts are introduced and used:

2. The design process

Discussions of the design and implementation of programs permeate the course--including going from a vague set of requirements to a specification, designing the program from the specification, and implementing the program based on the design.

3. Style

Good programming style is stressed throughout, including

4. Debugging

Students are given instruction on how to debug a program. The basic tools are either the debugger in the IDE or simple output statements.

5. A model of execution

A model of execution is used that allows the student to execute programs by hand and understand how storage is allocated and used. The model includes execution of method calls, to both non-static and static methods, as well as assignments and references to class variables and fields of instances of classes.

6. Efficiency

Comparison of programs based on space or execution time used is introduced. The tension between time and space is addressed. The concept of the base 2 logarithms is introduced. Basically, the student needs to know only that  log (2**x) = x.

7. Algorithms

The following algorithms are developed. Several approaches exist for this. For example, binary search may be introduced in terms of finding the zero of a continous function as well as in terms of finding a value in an array.

  • Linear search
  • Binary search
  • Selection sort
  • Insertion sort
  • Quicksort
  • Logarithmic exponentiation (compute x**y, given integer y>=0)

8. Graphics and GUIs

Students are presented with programs that use a well-designed GUI; there is a discussion of the GUI and how it is built. The Java abstract window toolkit is briefly explained. Students are not expected to program a GUI, but they will work with at least two programs that incorporate GUIs.

9. Control programs

At least one assignment concerns the notion of a computer controlling various devices. The program is often a simplified simulation of such a system, for example a home heating system or a cruise controller. This program will also be used to introduce students to the notion of different threads of execution.

10. Matlab and C

Three lectures and a homework are devoted to Matlab and two lectures and a homework to the programming language C. The intent of the discussion on C is to show the student the similarities and differences between Java and C. Covered, in brief, are pointers, structs, typedefs, pointers as parameters, arrays, malloc, and the absence of garbage collection.