| Instructor Christopher Sikorski (MEB 3418) | Office Hours: Wednesday, 2~4 PM |
| Class Time T/H, 14:00-15:20 | Class Room: WEB L112 |
| TA: Qin Liu (Qin.Liu@utah.edu) |
Office Hours: Friday 10:00~12:00, 1:00~3:00 |
Prerequisite
- Discrete structures, basic automata/ theory courses, linear algebra / calculus or graduate standing
Syllabus
- The syllabus for the course can be obtained here, pdf .
Description
- A brief survey of discrete mathematical concepts relevant to Computer Science, like sets, relations, functions, graphs and combinatorics. Finite state machines ( finite automata, pushdown automata, Turing machines ), regular languages, context free languages and grammars generating them. Comparison of discrete and real number models of computation, computational complexity, P and NP problems in discrete and real number models of computation; real number model with oracle calls, information based complexity, tractability of problems in discrete and real number models of computation.
Details
- In this offering the basic discrete models of computation like finite automata, pushdown automata and Turing machines are investigated. They are compared to the real number model with oracle calls ( and floating point implementation ). The prerequisites indicate required familiarity with discrete mathematical concepts and basic automata theory. Some mathematical background including calculus, linear algebra and functional analysis will be useful. This course is theoretical in nature and therefore involves proofs of crucial theorems characterizing properties of languages, finite state machines as well as crucial notions of computation in real number model and basic notions of information based complexity.
Texts
- The course will rely on the texts: Elements of the Theory of Computation, by H.Lewis and Ch. Papadimitrious, Prentice Hall, 1981, and Selected Topics in Approximation and Computation, by M.Kowalski, K. Sikorski and F. Stenger, Oxford Press, 1996, as well as on instructor notes. Other classical texts devoted to the complexity theory and theoretical computer science include: Kozen, Automata and Computability; Sipser, Introduction to the Theory of Computation; Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages, and Computation; Papadimitrious, Computational Complexity; Traub, Wasilkowski, Woznikaowski, Information Based Complexity; Traub, Woznikaowski, A General Theory of Optimal Algorithms; Sikorski, Optimal Solution of Nonlinear Equations; Blum, Cucker, Shub, Smale, Complexity and Real Computation, and Novak, Wozniakowski, Tractability of Multivariate Problems Vol I and II.
Lecture Form
- Lectures will be presented with the aid of overhead transparencies.
Lecture Slides
- Lectures slides could be obtained from here
- Lecture, Set 1, pdf
- Lecture, Set 2, pdf
- Lecture, Set 3, pdf
- Lecture, Set 4, pdf
- Lecture, Set 5, pdf
- Lecture, Set 6, pdf
Assignments
- Homework , Set 1, pdf