### Spring 2017

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

office phone (915) 747-6951 - Time: Tuesdays and Thursdays 3-4:20 pm, Room CCSB 1.0202
- Details: Syllabus

### Faculty office hours

- The instructor's office hours are Tuesdays and Thursdays 1:30-3 pm and 4:30-5 pm.
- If you want to come during office hours, there is no need to schedule an appointment.
- If you cannot come during the instructor's
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 and programming assignments

### Tests

### Quizzes

### Resources

- 2016 CS 5315 class Web page
- 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
- 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
- Quantum computing: Deutsch-Jozsa algorithm

### Class Notes

- Class Notes taken by Alex Vargas: January 17 and 19,
January 24, January 26,
January 31, February 2,

February 7, February 14, February 16, February 21, February 28, March 2, March 7, March 9, March 21,

March 23, March 28, April 4, April 6, April 11, April 13, April 18, April 20, April 25, May 2 - Class Notes taken by Sumi Dey: January 17 and 19,
January 24, January 26,
January 31, February 2,

February 7, February 14, February 16, February 21, February 28, March 2, March 7, March 9, March 21,

March 23, March 28, April 4, April 6, April 11, April 13, April 18, April 20, April 25, May 2

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