SAINT MARY'S UNIVERSITY
Department of Mathematics and Computing Science
CSC 3465 | Object-Oriented Programming | CSC 3465

Presumed Student Background

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 to employ, or ashamed of employing, "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, or guidelines, 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 and Data Structures 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. Searching via linear search or binary search in an array or vector, and searching in a hash table
  5. Sorting via various algorithms of different time complexities, depending on the application
  6. Choosing to use a vector, stack, queue, priority queue, set or multiset, map or multimap, or tree, as appropriate
  7. Using recursive data structures and recursive algorithms at a reasonable comfort level

Expected Programming Language Knowledge

You must have a good grasp of the basic syntax, semantics and program structure of some programming language other than Java. Preferably that language is C++, since that would mean in all likelihood you know at least something about classes and objects, and perhaps even something about inheritance and polymorphism. You should also be familiar with the use of programming language libaries, such as the C++ Standard Library, which includes its Standard Template Library.

Expected Program Development Skills

You must have some ability to write good code. This means code that is not only correct, but that is formatted in a consistent and readable style. In this connection, you must be able to follow any required set of rules, conventions and guidelines of a particular programming style.

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 some attention as the course proceeds.

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