CSC 173, Fall 2006

CSC 173 is the third course in the pre-major sequence for Computer Science, following CSC 171 (Computer Programming) and CSC 172 (Data Structures). The course serves two principal purposes:

1. It introduces students to formal systems of importance in computer science, and explains their usefulness for “real world” computation. In this sense, the course might well be subtitled “Computer Science is not (just) programming”.
2. It makes the transition from Java on personal computers to C on Unix. Most of the department's upper-level courses use C or C++, and while Java is of large (and increasing) commercial importance, “industrial strength” programming of large systems is likely to continue to be be done in C and C++. Given time constraints, we will focus on C, rather than C++, as the transition language this term.

We will study several formal systems such as:

Relations and relational algebra—

These allow us to reason about data in tabular form. They form the foundation of all modern database systems.

Finite automata and regular expressions—

These allow us to reason about systems with a finite number of states. Among other things, they underlie communication protocols and the first stage of compilation.

Context-free grammars and parsers—

These allow us to reason about languages with recursive structure. In particular, they form the backbone of most compilers and command interpreters.

Graphs— These allow us to model all sorts of relationships among objects, and to compute properties of those relationships. One can easily fill a whole semester with graph theory; we'll look at some interesting aspects that haven't been covered recently in Math 150 or CSC 172.

Propositional logic—

This allows us to reason about complicated combinations of conditions, such as those that arise in the design of digital circuits.

Predicate logic—

This extends the reach of propositional logic to consider conditions with arguments. It underlies systems for natural language understanding and programming in languages such as Prolog and SQL.

Queueing theory—

This allows us to model the behavior of computer systems in a tractable manner.

There are four conceptual prerequisites for CSC 173:

1. knowledge of at least one imperative programming language, preferably Java, C, or C++
2. understanding of fundamental data structures (lists, stacks, queues, trees, hash tables)
3. basic algorithm analysis techniques (Big-O analysis)
4. programming maturity