CPS208

Programming Methodology

R. A. Wagner

D336 LSRC

660-6536

raw@cs.duke.edu

 

Prerequisites

CPS 100
 

Synopsis of course content

This course on Programming Methodology includes 3 broad areas of study:

 

  1. Designing or selecting algorithms appropriate for the assigned problem;
    1. I plan to require 3 or 4 “hard” programming problems, to be solved without the use of the internet.  These problems are likely to be “borderline NP-hard”, that is, problems which are probably NP-hard, but have not been proven so.  The idea is to attack them anyway – but how?
  2. Producing maintainable, correct, fast code for the selected algorithms;
    1. Even languages that are designed to force programmers to produce “well-designed” code allow programs that contain bugs.  Commercial code often contains annoying coding errors, often subtle ones, which reveal themselves only after many days of work on a large project.  What are some overall sources of these errors?  Can good practices eliminate them, or minimize their number?
  3. Debugging programs, either produced using “correct-by-design” methods, or by others, using possibly unstructured, bug-prone methods.
    1. Two aspects of this problem are important— Choosing and simplifying a revealing test case or cases, and fixing the problem.  One must use logic to choose demanding test cases, but simplify the resulting test to one which is short enough for debugging tools, such as GDB, to operate on successfully.  Fixing the problem, using GDB, or some other debugging approach (such as embedding DEBUG print statements in the code) is an art in itself, made more interesting by the advent of hardware tools, like “hardware watch points”, that allow the debugger to run code at full speed, until that code tries to store into (or access) some specific byte in memory.

 

The course text is a starting-point for these topics, but I intend to use my own experiences, and class discussions to augment its material.

The preferred language for programs in this course is “C”.  I would like to compare “C” in its ability to assist in writing correct programs with other languages, however, so background in languages like C++, Java, and possibly Python, Perl, and SML would be helpful.

Textbook(s)

Programming Pearls, Bentley, Jon.

OnLine Documents

Introductory Problem
Look for assignments here

Assignments

Several computer programs, and papers explaining those programs
 

Exams and Homework

Several computer programs (homework).  One or more programs supplied by me for you to debug.  Lateness of 3% per calendar day late is charged on programs, and they are not accepted more than 7 days late.
 

Grade to be based on 

Programs, papers, class discussion, and possibly a final.