Course Overview
Worldclass programming skills require:
 programming language skills for creating programs that work
 data structures and analysis of algorithms for
building correct and efficient programs
 formal systems for managing complexity with formal models
Isn't competence in a programming language enough?
Imagine trying to implement
 a sorting routine, without having studied sorting
algorithms, or having the tools of algorithm analysis to evaluate
your sorting program.
 an efficient search routine, without an understanding of
binary search trees.
 an efficient representation for a dictionary containing millions
of words, with millions of prefixes,
without knowing about tries or search trees.
 insertion and deletion on a list, without using doublelinked lists.
 recursion without a stack.
 programs that manipulate sets of elements, without knowing
how to efficiently implement union and intersection.
Knowing a programming language (at the level
of CSC 171 or a high school AP course) is only the first step
in solving problems on a computer.
Knowledge of data structures and analysis of algorithms
is essential to all of the above problems.
Aren't data structures enough?
Consider how you might implement:
 a database that accepts complex queries like
"find the name and address of all CS majors at UR
that have taken CSC 173 and also received an A in MTH 162."

A travel planner that tries to find the shortest route between any
two cities, given a map of the country with distances.
 a compiler that reads in statements in a highlevel programming,
checks the correctness of each statement, and translates the highlevel
statement into machine code.
 a speech system that takes in spoken words and
creates an unambiguous representation of the meaning of the words.
 a compact digital circuit that computes an arbitrarily complex
mathematical function, using only 1's and 0's as input,
and the boolean operations AND, OR, and NOT.
 an intelligent assistant that, given a set of facts, can reason
about those facts, and prove hypotheses.
 a student program checker that reads in a C program and its input,
and determines whether the program enters an infinite loop on that input.
Programming language skills and knowledge of data structures are necessary
for solving these problems, but not sufficient.
Solving these complex problems in an ad hoc fashion would be a
laborious and errorprone task.
Formal models and systems can provide the tools to help solve
these, and other similar, problems.
What is a formal system?
Formals systems are abstract models of complex phenomena.
 algebra of natural numbers (N,+,,*,/) for modeling word problems
 calculus for modeling continuous physical phenomena
 mathematical functions for modeling program behavior
Good models (or abstractions) of realworld phenomena or problems are useful
because
 models capture important features, and ignore
irrelevant details
 the same model can be applied to a wide variety of problems
 models are robust enough to evolve easily with applications
But are formal systems really practical?
Formal systems are used in
a variety of practical applications, to manage complexity,
facilitate analysis, and provide a framework for optimizations.
 databases: relational algebra
 routing and connectivity: graph theory
 compilers: regular expressions, automata, and formal languages
 speech understanding: formal languages and predicate logic
 circuit design: propositional logic and boolean algebra
 intelligent (deductive reasoning) systems: predicate logic
 undecidability: formal models of computation (e.g. Turing machines)
 heuristic search: genetic algorithms
last modified Jan 18 1996 / Tom LeBlanc / leblanc@cs.rochester.edu