Course Overview

This reading provides a conceptual overview of the content of this course. For details about coursework, grading, and other mechanics, see the course syllabus.

At a high level, this course involves four main components:

Computer science highlights several distinct views of problem solving. Each perspective works extremely well for some types of problems, but not so well for other types of problems.

In computing, we typically start with a problem that we wish to solve. Sometimes a problem is well-developed and nicely articulated (as it usually is in your courses). The type of problem solving we will do in this class is called "imperative problem solving", and it usually assumes that the problem to be solved is well understood and can easily be broken down into smaller problems until we can write a corresponding line of code to instruct the computer or robot to take an action.

In real-life situations, initial work is often required to clarify just what needs to be done, what information a user starts with, and what results would be useful at the end. How we handle those types of situations will be covered in other courses, such as Software Design and Development (CSC 324).

Other types of problems might be well-defined but they do not fit well into the imperative framework, which means that you might require a functional programming approach (CSC 151) or an object-oriented one (CSC 207). Imperative programming is a paradigm that is quite flexible, but if you ever find yourself struggling to solve a problem with this approach, step back and ask yourself if you have the right tool for the job.

Imperative Problem Solving

This course focuses on imperative problem solving—an approach that is particularly useful in many areas, such as mathematics, statistics, science, engineering, computer systems, and computer networks.

Once a problem is clearly articulated, the goal of imperative problem solving is to develop a sequence of steps to solve the given problem. Typically, the problem begins with some information, just as in cooking, a chef starts with initial ingredients. From this starting point, we need to develop a sequence of step-by-step instructions for working with the data, just as a chef follows steps for cutting, blending, cooking ingredients, etc. In computer science, the resulting sequence of steps in called an algorithm, just as in cooking the steps are called a recipe.

When processing or cooking will be long and complex, imperative problem solving or cooking organizes instructions into high-level tasks, just as a recipe might indicate "mix all ingredients" or "heat while adding sugar until a firm consistency is obtained." Although the high-level tasks may suggest steps to be taken, some of these tasks may need to be subdivided into more detailed sub-tasks.

In some cases, both in imperative problem solving and in cooking, some tasks (e.g., printing numbers or separating egg whites from yolks) may be quite common, and we might develop one or more libraries that manage the details for handling those activities.

Imperative Problem Solving and Outline Form

The imperative problem solving approach organizes an overall solution into logical steps. First, the solution articulates one or more main steps. Second, if these steps seem complex, a main step may be subdivided into substeps. Subsequent substeps may be subdivided as needed to provide an overall sequence of detailed steps that specify a solution to the original problem.

Here is an example solution outline, in the top-down, imperative style:

  1. Main step 1
    1. substep 1a
      1. 1ai
      2. 1aii
      3. 1aiii
    2. substep 1b
    3. substep 1c
      1. 1ci
      2. 1cii
  2. Main step 2
    1. substep 2a
      1. 2ai
      2. 2aii
    2. substep 2b
  3. Main step 3
    1. substep 3a
    2. substep 3b
      1. 3bi
      2. 3bii
      3. 3biii
      4. 3biv
    3. substep 3c
    4. substep 3d

You may contrast this with the functional problem-solving paradigm, in which computations are thought of as sequences of transformations realized as nested function calls. For example, in scheme we might write the following. 

(define image-sharpen
  (lambda (image)
    (image-add image
               (image-scale 0.2
                            (image-difference
                             (image-blur 2.0 image )
                             image)))))

By contrast, in an imperative version of this algorithm might be expressed as follows.

  1. Acquire image
  2. Find edges
    1. Blur image
    2. Subtract original image from blurred image
  3. Scale edge image
  4. Add edge image to original image

C Programming

When developing an algorithm or articulating the steps necessary to solve a problem, communication needs to be precise, clear, and unambiguous. If two people read the same description of an algorithm, they should have a common understanding of what to do and in what order. Further, when given starting data, reviewers should be able to apply the algorithm unambiguously to determine whether or not the result was correct. In addition, given two potential algorithms to solve a problem, the description of the algorithms should be sufficiently precise to allow analysis of whether one approach is more efficient or more accurate than another. Altogether, precision of language is essential for the specification of proposed solutions to problems.

Unfortunately, natural language, such as English, is neither precise nor unambiguous. Words may have multiple meanings, and general statements may not provide complete details. Since English or other natural languages are not adequate for technical communications of algorithms, new forms of exposition are essential in articulating algorithms for use in technical areas. Mathematical notation serves this purpose for some quantitative fields, but mathematical notation does not work particularly well for many problems for which we want help from a computer.

The C programming language has evolved over the years as a mechanism for precise communication for describing algorithms developed through imperative problem solving. The original version was developed between 1969 and 1973 by Dennis Ritchie with the intention of supporting research and development efforts at Bell Labs—then the research arm of American Telephone and Telegraph (AT&T). Since that time, C has been refined, expanded, and standardized. The first C Standard was approved in 1978 by the American National Standards Institute (ANSI). Subsequent standard versions have been approved by the International Organization for Standardization (ISO) in 1990, 1999, and 2011.

With international standards in place, programs written in C that work on one machine can often be ported to another machine with little difficulty. Sometimes underlying hardware constraints may limit the movement of programs from one environment to another, but often C programs can be run without change on a wide variety of computers.

Although some extensions of Standard C may be limited to one machine environment or another, this course will emphasize features of Standard C. Programs in this course should work on any computer with access to widely-available libraries.

Characteristics of the C Language

C features strong support for imperative problem solving. It is a natural vehicle for algorithms in science, mathematics, statistics, engineering, computing systems, and computer networks, and is widely used in applications. The language has been adapted for use in machines from small micro-computers to large environments.

Although many details are esoteric, overall C has a relatively simple syntax. In comparison to many modern languages, it is modest in features, yet expressive enough to support a wide range of solutions.

Despite the simplicity of the language, extensive libraries are available to handle many common tasks. Libraries extend simple syntax to provide substantial computing capabilities.

C provides great control and power to programmers. The language provides programmers with direct access to memory and data, with little overhead. Programmers can therefore organize data and refine algorithms for efficiency. However, C assumes programmers know what they are doing and does little error checking. Thus, while processing can be fast, programmers must take responsibility for correctness.

The output from C programs is generally stark and text-based. It doesn't even have native support for colored text! It can create images by directly manipulating the dots (pixels) in an image, but it is a challenging process.

Storage and processing of data within a computer

The C programming language provides a reasonably low-level view of the inner workings of a computer. In order to be effective, programmers must understand how data are organized within a computer and how various types of data are stored. Further, in some contexts, a programmer must explicitly allocate space for the storage of information and free that space when that information is no longer needed.

Whether working directly with C or not, an understanding of data storage and processing can provide insights into effective approaches for using the computer to solve problems. When one knows underlying principles of processing, one can organize subsequent work to take advantage of hardware, while avoiding approaches that may be less efficient or effective. One also may gain appreciation of what can go wrong in programs and how to respond.

Consequence of Data Representation

Parts of the course will examine details of how various types of data are stored within a computer:

Details of the storage of each data type have specific consequences for processing. Without some care, some algorithms may produce incorrect or undesired results in certain circumstances, and the course will examine possible consequences.