Course Overview

World-class 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 double-linked 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 high-level programming, checks the correctness of each statement, and translates the high-level 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 error-prone 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 real-world 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