CIS 262, Spring 2020

Additional Useful References:

Automata and Computability, Dexter Kozen, Springer

Introduction to the Theory of Computation, Michael Sipser, Second Edition, 2005, Thompson Course Technology

Theory of Computation, Derick Wood, Wiley

Mathematical Theory of Computation, Zohar Manna, McGraw Hill

An Introduction to the General Theory of Algorithms, M. Machtey and P. Young, Elsevier North-Holland

Introduction to Formal Language Theory, M. Harrison, Addison Wesley

The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Martin Davis, Raven Press

Theory of Recursive Functions and Effective Computability, Hartley Rogers, MIT Press

Introduction to Metamathematics, Stephen Kleene, North-Holland

Computability and Unsolvability, Martin Davis, McGraw-Hill

Enumerability, Decidability, Computability, Hans Hermes, Springer-Verlag

Computational Complexity, A Modern Approach, Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009

Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 2000

Computational Complexity, Christos Papadimitriou, Addison Wesley

Google's PageRank and Beyond: The Science of Search Engine Rankings, Langville and Meyer, Princeton University Press, 2012

Some Historical and Leading Figures

The MacTutor History of Mathematics archive

The Mathematics Genealogy Project

Recent Paper Relevant to the Course Material

• Deterministic Finite Automata with Recursive Calls and DPDA's (pdf)
  With Salvatore La Torre and Supratik Mukhopadyay
  March 2003.

• Old Homework from CIS 262 (now CIS160), on the pairing functions J, K, L
  (pdf)

• Faster Algorithms for Frobenius Numbers
  D. Beihoffer, J. Hendry, A. Nijenhuis, S. Wagon (pdf)

• The Frobenius Coin Problem. Upper Bounds on the Frobenius Number
  J. Gallier (pdf)

• Hidden Markov Models, in Speech and Language Processing, by Jurafsky and Martin (pdf)

• A Revealing Introduction to Hidden Markov Models, by Mark Stamp (pdf)

• A Tutorial on Hidden Markov Models and
  Selected Applications in Speech Rcognition, by L. Rabiner (pdf)

• HMM: Viterbi algorithm: a toy example (to predict DNA coding) (pdf)

• Slides by Bjorn Poonen (UPenn Rademacher Lecture 1, Fall 2017;
  Undecidability in Number Theory) (pdf)

• Wines in the area around Beaune (pdf)

Relevant Fun Software

Back to Gallier Homepage

published by:

Jean Gallier