Lecture notes for CS 173, Thurs, Sep. 1, 2005 How many declared (provisional) majors? intended majors? others? How many freshmen/sophomores/juniors/seniors? How many actually took 172? Who knows Java/C/C++? ======================== Administrivia Instructor sandhya@cs Office hours: by appointment, but don't be afraid to drop by TAs: Web site www.cs.rochester.edu/u/sandhya/csc173/ Newsgroup: ur.cs173 Resources Computers CSUG machines remote access encouraged; learn to use X stick around at end of class for an account textbook lecture notes on-line Grading 20% midterm 20% final 50% projects (tentatively: 6) late policy; Academic honesty 10% homeworks/quizzes Course attendance and participation PLEASE PARTICIPATE IN CLASS ask questions interrupt me if I go too fast or too slow if you're confused, so are the people around you ======================== CLAIM: World-class programming skills require: * programming language skills for creating programs that work * abstractions, 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 * recursion without a stack. * a sorting routine, without knowing the difference between the n^2, n lg n, and linear algorithms. * an efficient search routine or dictionary, without knowing about balanced search trees, binary search, or hashing. * insertion and deletion on a list, without using double links. * shortest paths in a graph, without knowing Dijkstra's or Floyd's algorithms. 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? *** Note: What is the difference between an abstract data type and a data structure? *** Consider how you might implement: * a database that accepts -- and efficiently answers -- 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 compiler that reads in statements in a high-level programming language, 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 expert system that assists a physician in the diagnosis of disease based on exhibited symptoms. * 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? Formal systems are abstract models of complex phenomena. Outside CS: * algebra of natural numbers (N,+,-,*,/) for HS "word problems" * calculus and differential equations to model continuous physical phenomena (e.g. motion of the planets) * linear algebra for systems of linear inequalities (e.g. to minimize manufacturing or transportation costs) * probability and statistics to model games, population dynamics, quantum physics 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 * mathematical tools can be applied to formal systems to prove useful theorems or generate working code -------- But are formal systems really practical? You bet! Formal systems are used in a variety of practical CS applications, to manage complexity, facilitate analysis, and provide a framework for optimizations. In CS: * databases: relational algebra * communication protocols: finite automata * routing and connectivity: graph theory * security, fault tolerance, and concurrent systems: temporal logic, petri nets, queueing theory, adversary arguments, number theory * compilers: regular expressions, context-free grammars, automata, data flow analysis, systems of affine functions and convex sets, denotational semantics * circuit design: propositional logic, boolean algebra, and computational geometry * speech understanding and reasoning: formal languages and predicate logic * undecidability: formal models of computation (e.g. Turing machines and lambda calculus) * heuristic search: genetic algorithms Subjects to be covered Relations and relational algebra C and Unix Finite automata and regular expressions CFGs and parsing propositional logic predicate logic Queueing theory??