CS 5315/6315: Theory of Computation

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: He will then send a reply email, usually confirming that he is available at this time, and he will place the meeting with you on his schedule.

Homeworks and programming assignments

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

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