Expectations: Student Background

When a student signs up for a course, that student essentially acknowledges that he or she is comfortable with the prerequisite material, however and wherever that comfort level has been achieved. In addition, students will be expected to:

Somewhat more specifically, students are expected to have the background described in what follows.

Expected Mathematical Knowledge

Mathematical prerequisites for computer programming generally require that you have achieved a certain level of "mathematical maturity". If you have taken one or more calculus courses, that will usually be the case, though this does not mean that much calculus is a necessary prerequisite for many computer science courses.

But, in particular, you are expected to have a reasonable familiarity with the following concepts and topics:

  1. The real number line, integers, real numbers, and interval notation (by which we mean expressions like [a, b] or (a, b), for example)
  2. Elementary set notation and concepts (set, subset, union, intersection, complement)
  3. Arithmetic and, in particular, modular arithmetic
  4. Simplifying and evaluating expressions, and manipulating and solving both equations and inequalities
  5. The standard elementary mathematical functions--—polynomial, logarithmic, and exponential in particular—--including their general properties (domain, range, graph, asymptotes, intercepts, inverse function where applicable, and so on)
  6. Elementary counting methods with simple permutations and combinations, and factorial notation
  7. Simple sequences and their sums (arithmetic and geometric, for example)
  8. Some experience with mathematical proofs, including mathematical induction
  9. The basic ideas of limit, derivative and integral

Expected Problem Solving Knowledge and Ability

Your prior mathematical and programming experiences will necessarily have provided you with some specific techniques, as well as some general approaches, for solving problems. It is important to distinguish between these two. Using the relevant formula for finding the roots of a quadratic equation is one example of a specific technique, and the following section lists a number of specific algorithmic techniques that you should know. But there are quite a number of more generic strategies for dealing with the many different kinds of problems you are likely to encounter and have to solve, and you should be ready, willing and able to apply any or all of the following pieces of advice as needed:
  1. Never attempt to solve a problem until you know what it is, so you must always check the problem specification (or description) very carefully.
  2. Always be concerned first with what needs to be done, and only second with how to do it.
  3. Look for well-known solutions that already exist. In other words, the first rule of problem solving is to find a solution that already exists, if you can, and use that. (This should not, however, be taken as an endorsement of plagiarism!)
  4. Get an overview (think of it as getting a "gut feeling" for the problem as well as an intellectual understanding of it) and then choose a good way to represent the problem and/or its constituent parts. Remember that a good notation will help you to think clearly about the problem, while a poor notation can inhibit you from thinking clearly.
  5. Try to break up a large problem into smaller problems, and try to exploit whatever similarity among those problems that you can identify. (There are several ways to do this, and you will learn more about these as time goes on.)
  6. If you need to define something yourself, make sure it's well-defined, which means that it is defined in such a way that it cannot be confused with something it is not. At the same time, try not to read more into any definition (including one of your own) than is really there.
  7. Don't be afraid or ashamed to employ "brute force" as a first try. Sometimes that's all you need, or all you can find. Other times, it's an excellent way to begin your journey to a more elegant solution.
  8. Try not to confuse
    1. The truly difficult with the merely subtle or obscure
    2. Conventions with rules
    3. Matters of substance with matters of style
    4. An algorithm with a "heuristic" or "rule of thumb"
    5. Useless information with redundant information

Expected Contents of Your Personal Algorithm Toolkit

You must have in the algorithm toolkit that you carry about with you at all times a good knowledge of several fundamental algorithms, which you are able to implement in various situations more or less at the drop of a hat. These include the following:
  1. Reading a known or unknown number of values from a stream
  2. Exchanging the values of two variables
  3. Finding the maximum, minimum or other special value in a sequence of values of known or unknown length
  4. Linear search in an array
  5. Binary search in an array
  6. At least one sorting algorithm that uses an array to hold the data

Expected Programming Language Knowledge

You must have a good grasp of the basic syntax and semantics of either C++ or Java, and preferably the one being used for the course in which you are currently enrolled. Your instructor will be putting some effort into getting everyone on the same page with whatever language is being used.

You must also, of course, develop the ability to read and understand "good" code in the language of choice, i.e., code that is correct and well formatted. Although you will need to be able to trace in a formal way any particular code segment, especially if it contains a bug which you are trying to track down, you should also be able to get a good overall sense of what the code does without resorting to a trace, if the code is in fact well written and you do in fact have the ability to which we refer here.

Expected Program Development Skills

You must already have, or quickly acquire, the ability to write "good" code, in the programming language of the course. This means code that is not only correct, but that is formatted in a consistent and readable style. In this connection, you should have by now a good sense of what it means to use a "programming style" in a particular language, and at this point you should have developed a coding style of your own in whatever language you have been using.

Whatever style you have developed is not necessarily the style you will be using in this course, by the way, since for simplicity and consistency we will all be using a set of common programming style conventions. Doing this appears to be more difficult for most students that it might appear to be at first glance, so be prepared for a period of adjustment. Fighting it, however, will be counterproductive.

It is perhaps worth pointing out that there is some evidence to suggest that those who have the most difficulty adapting to a new style never had an old one.

You must have some ability to develop from scratch a program of moderate size, at least in the academic sense (several hundred lines, possibly even one or two thousand lines). That is, you should be able to carry out all the steps necessary to proceed from the original problem to the final program that solves the problem (or, more formally, to the program which is an implementation of a solution to the problem). This ability goes well beyond the knowledge of syntax and semantics and programming style, which are necessary but far from sufficient for one to be a good software developer.

You are expected to know what is meant by top-down design and step-wise refinement and be able to apply this approach to program development (to the implementation part of the process using stubs and drivers, as well as to the design part of the process). You must be able to apply the approach to the development of a single function as well as to groups of functions working together to accomplish a particular task and to the program as a whole. You must understand what is meant by the principle of information hiding, and be able to apply this principle as you design each function and its interface.

You are also expected to be able to write intelligible pseudocode to describe each of your algorithms before actually coding it, and to use structure diagrams to give a pictorial representation of program structure.

These notions are central to the procedural approach to program development, but also have their place within the object-based and object-oriented methodologies, to which we will devote at least some attention as the course proceeds.

The classic procedural (structured) approach to program development is often regarded as comprised of the following phases: