CSC 173, Fall 2001

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:

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.

Many students will have seen some of this material in previous courses in discrete mathematics, data structures, mathematical logic, or AI. We will review this material quickly, spending the bulk of our time on the rest of the syllabus. As time allows, we may cover material not found in the text. Possibiities include queuing theory, lambda calculus, and genetic algorithms.


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

All of these prerequisites are satisfied by taking CSC 172: Data Structures. If you are unsure of your background, contact the professor.

Back to the course home page

Last Change: 29 August 2001 / Michael Scott's email address