### Spring 2020

- Instructor: Vladik Kreinovich, email vladik@utep.edu,
office CCSB 3.0404,

office phone (915) 747-6951 - Class time: Tuesdays and Thursdays 1:30-2:50 pm, location CCSB 1.0702.
- Details: Syllabus

### Faculty office hours

- The
instructor's office hours are:
- Tuesdays 8:30-9 am and 10:30-12:30 pm,
- Thursdays 8:30-9 am, 10:30-12 pm, 1-1:30 pm,
- or by appointment.

- If you want to come during the scheduled office hours, there is no need to schedule an appointment.
- If you cannot come during the instructor's
scheduled office hours, please schedule an appointment in the
following way:
- use the instructor's appointments page http://www.cs.utep.edu/vladik/appointments.html to find the time when the instructor is not busy (i.e., when he has no other appointments), and
- send him an email, to vladik@utep.edu, indicating the day and time that you would like to meet.

### Homeworks

### Tests

### Quizzes

### Resources

- 2019 CS 5315 class Web page
- 2017 CS 5315 class Web page; this page contains class notes
- Definitions used in the course
- Main results covered in the course
- Why Theory of Computation is important?
- website from 2009 which contains class notes
- Notes on primitive recursive functions
- O. Kosheleva and V. Kreinovich, "Towards Making Theory of Computation Course More Understandable and Relevant: Recursive Functions, For-Loops, and While-Loops", Presentation at the Sun Conference on Teaching and Learning, El Paso, Texas, March 10-11, 2011. pdf file
- V. Kreinovich and O. Kosheleva, "Towards Making Theory of Computation Course More Understandable and Relevant: Recursive Functions, For-Loops, and While-Loops", Proceedings of the 5th International Conference "Mathematics Education: Theory and Practice" MATHEDU'2015, Kazan, Russia, November 27-28, 2015, pp. 17-19. pdf file
- Vladik Kreinovich and Olga Kosheleva, "A Turing Machine Is Just a Finite Automaton with Two Stacks: A Comment on Teaching Theory of Computation", Proceedings of the 8th International Scientific-Practical Conference "Mathematical Education in Schools and Universities: Innovations in the Information Space" MATHEDU'2018, Kazan, Russia, October 17-21, 2018. pdf file
- V. Kreinovich, A. Lakeyev, J. Rohn, and P. Kahl, "The notions of feasibility and NP-hardness: brief introduction", Chapter 2 from "Computational complexity and feasibility of data processing and interval computations", Kluwer, Dordrecht, 1997. pdf file
- O. Kosheleva and V. Kreinovich, "Space-Time Assumptions Behind NP-Hardness of Propositional Satisfiability", Mathematical Structures and Modelling, 2014, Vol. 29, pp. 13-30. pdf file
- O. Kosheleva and V. Kreinovich, "NP-Hardness Proofs With Realistic Computers Instead of Turing Machines: Towards Making Theory of Computation Course More Understandable and Relevant", Presentation at the Sun Conference on Teaching and Learning, El Paso, Texas, March 10-11, 2011. pdf file
- V. Kreinovich, "Designing, Understanding, and Analyzing Unconventional Computation", Presentation at the Understanding Unconventional Computation Workshop, Stanford, California, March 23-24, 2010. pdf file
- V. Kreinovich, "Designing, Understanding, and Analyzing Unconventional Computation: The Important Role of Logic and Constructive Mathematics", Applied Mathematical Sciences, 2012, Vol. 6, No. 13, pp. 629-644. pdf file
- D. Morgenstein and V. Kreinovich, "Which algorithms are feasible and which are not depends on the geometry of space-time", Geombinatorics, 1995, Vol. 4, No. 3, pp. 80-97. pdf file
- M. Koshelev and V. Kreinovich, "Towards Computers of Generation Omega - Non-Equilibrium Thermodynamics, Granularity, and Acausal Processes: A Brief Survey", Proceedings of the International Conference on Intelligent Systems and Semiotics (ISAS'97), National Institute of Standards and Technology Publ., Gaithersburg, MD, 1997, pp. 383-388. pdf file
- O. Kosheleva and V. Kreinovich, "How to Introduce Technical Details of Quantum Computing in a Theory of Computation Class: Using the Basic Case of the Deutsch-Jozsa Algorithm", International Journal of Computing and Optimization, 2016, Vol. 3, No. 1, pp. 83-91. pdf file
- Olga Kosheleva and Vladik Kreinovich, "A Natural Feasible Algorithm That Checks Satisfiability of 2-CNF Formulas and, if the Formula Is Satisfiable, Finds a Satisfying Vector", Proceedings of International Forum in Mathematics Education, Kazan, Russia, October 18-22, 2017, Vol. 2, pp. 186-188. pdf file

### Logistics of April-May classes:

### Materials for April-May classes:

- April 2: Sections 2 and 3 of the handout Space-Time Assumptions Behind NP-Hardness of Propositional Satisfiability and the handout NP-hardness proofs ...
- April 7: lectures 31. 3-SAT Is NP-Complete, 32. 3-Coloring Is NP-Complete, 33. Clique Problem Is NP-Complete, and 34. Subset Sum Is NP-Complete
- April 9: lecture 35. Interval Computations Is NP-Hard
- April 14: lecture 36. Parallel Computations and Section 2 of the handout Which algorithms are feasible ...
- April 16: lectures 38. Probabilistic Algorithms, 39. Greedy Algorithms for Solving NP-Complete Problems, and the handout A Natural Feasible Algorithm That Checks Satisfiability of 2-CNF Formulas
- April 21: handout How to Introduce Technical Details of Quantum Computing ...
- April 23: lecture 42. Polynomial Hierarchy
- April 28: handouts Designing, Understanding, and Analyzing Unconventional Computation, Designing, Understanding, and Analyzing Unconventional Computation ..., Which Algorithms Are Feasible ..., and Towards Computers of Generation Omega ...
- May 5: lecture Kolmogorov Complexity

Department of Computer Science | The University of Texas at El Paso