Subject Matter

This course is intended to follow CSC 171, which most of you took last semester. For the first six weeks or so, we'll re-visit many of the programming techniques we learned last semester, only in Java rather than Scheme. Then we'll go on with more advanced techniques: some that we didn't have time for last semester, and some that don't make sense in Scheme but are terribly useful in Java. Throughout the semester, we'll focus on the paired concepts of algorithm and data structure.

algorithm

A specification of how to accomplish a particular task. Many books use the example of a recipe in a cookbook, which specifies how to convert raw materials (eggs, flour, etc.) into a desired end product (a batch of cookies); other examples would be the procedure you go through to start your car, or to multiply two large numbers together, or the quadratic formula. Most books also define an algorithm as a sequence of operations, but the notion of sequence is not essential: the quadratic formula, for example, doesn't look like a sequence of operations at first glance, and in fact it can be evaluated in several different orders with no impact whatsoever on the result.

An algorithm is not quite the same thing as a program, although every program has one or more algorithms at its heart. An algorithm is more or less independent of the language in which it is expressed: one can write essentially the same algorithm in Java, Pascal, C++, Visual Basic, and Scheme, although they will all look cosmetically different (with different sequences of semicolons, commas, braces, keywords, etc).

data structure

A specification of how to represent a particular kind of information in a computer. Most languages provide several ``primitive'' data types, e.g. integers, characters, and perhaps strings, functions, etc. But if the information you need to manipulate isn't exactly one of those kinds of information, you need to figure out how to represent it. For example, last semester we defined a structure posn to represent an ordered pair of numbers, wrapped up together as a single object; and we defined more complex, self-referential data structures like lists, binary trees, and so on.

Data structures and algorithms are usually mentioned in the same breath, because if you come up with a wonderful data structure to hold information, you still need to supply algorithms for accessing and manipulating the information. Furthermore, as we saw last semester, frequently the ``shape'' of a method corresponds to the ``shape'' of the data on which it operates, so it makes sense to design a data structure and algorithms for it simultaneously.

This principle is put into practice in the methodology of programming called ``Object-Oriented Programming'', or OOP for short. In an object-oriented program, not only are the data structure and its algorithms designed simultaneously, but the program code to describe them is tightly interwoven. You'll see what this means as the semester goes on.