Overview

Course Overview

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:

Variables of type integer, boolean, float, string
Assignment statement
Conditional statement
Loops (while and for)
Procedures and functions (methods in Java); recursion is introduced briefly but is not discussed in depth
Scope of variables
One-dimensional and two-dimensional arrays
Classes and objects

Variables that contain (a reference to) an instance of a class
Constructor methods
Inheritance
Static variables and methods

Simple I/O

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

Specifying a program or procedure before designing and coding it.
Maintaining a correct specification if the program or procedure body is changed.
Defining variables precisely before writing code that uses them.
Using (informal) loop invariants to help understand loops.
Use of indentation to make structure apparent.
Use of abstraction. Judicious writing high-level statements (in English) to describe sections of code.
Interlacing code development and debugging as opposed to writing a complete program and then debugging.
Writing code for reuse.

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.