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:
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”.
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.
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
- 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
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:
- knowledge of at least one imperative programming language,
preferably Java, C, or C++
- understanding of fundamental data structures (lists, stacks, queues,
trees, hash tables)
- basic algorithm analysis techniques (Big-O analysis)
- 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