CS 5315: Theory of Computation

Spring 2014

  • Instructor: Vladik Kreinovich, email vladik@utep.edu, office phone (915) 747-6951
  • Time: 4:30-5:50 pm, Mondays and Wednesdays, Room CCSB 1.0204
  • Details: Syllabus

Faculty office hours

  • M 4-4:30 pm, W 3:30-4:30 pm, W 6-6:30 pm, or by appointment.

Quizzes

Resources

  • 2013 CS 5315 class Web page
  • website from 2009 which contains class notes
  • 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
  • Vladik Kreinovich, Anatoly Lakeyev, Jiri Rohn, and Patrick 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", University of Texas at El Paso, Department of Computer Science, Technical Report UTEP-CS-13-34, 2013. 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
  • Vladik Kreinovich, "Designing, Understanding, and Analyzing Unconventional Computation", Presentation at the Understanding Unconventional Computation Workshop, Stanford, California, March 23-24, 2010. pdf file
  • Dara Morgenstein and Vladik 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

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