CS 171 Home Page
Inntroduction to Computability
Spring 2024
This course emphasizes the mathematical and theoretical foundations of computer science.
The primary topics are computability theory and Turing machines, complexity theory
(including the classes P, NP, NPcomplete, and NP hard), grammars and parsing, pushdown automata,
and running time analysis (especially using recurrence relations and generating functions).
Important fundamental questions will be answered, such as whether all functions are computable
and the existence of unsolvable problems. Also included is an introduction to proofs of program
correctness and some running time analysis for algorithms to solve the traveling salesperson problem.
Further Information
 Course Syllabus
 Documents, homilies, and speeches of Pope Francis
 Poverty, Hunger, and Social Justice in America
In honor of Martin Luther King, Jr.
 Parser Freeware and Examples
 Wolfram Mathematica Documentation Center
 Wolfram Learning Center
 Wolfram MathWorld
 Wolfram Functions
 Wolfram Library
 Wolfram Demonstrations
 The ShroederBernstein Theorem
 Education web site by Texas Instruments
Includes manuals and tutorials for many TI calculators and links to math web sites.
 Example Prolog programs
Including tictac.pro.
 Br. David's Traveling Salesperson Problem: Software and Lab webpage.
 AMS Overview of the TSP

Using Mathematica to Solve a TSP
 RSA.com
 RSA Conference
 Britannica: Alan Turing
 AlanTuring.net
 Overlooked No More: Alan Turing
 The ACM Code of Ethics and Professional Conduct
See especially section 1.6 on privacy issues.
 Textbook
web site
Provides guides to writing proofs and common mistakes
in discrete mathematics, links to external Web sites, extra examples, selfassessment
on some key topics, and interactive demonstrations of important algorithms.
 Example proofs
 The status of the
P versus NP Problem
 P versus NP problem
 LearnSAT is a satisfiability solver for propositional logic formulas.
Although the SAT problem is NPcomplete, this and other SAT solvers are said to perform well.
 Godel's Incompleteness Theorems
 The probabilistic checkable proofs theorem is one of the big
developments in recent years in the area of complexity theory.
 In recent years, the concept of continuous programs has been developed. See, for example, the article
Proving
Programs Continuous or Continuity
and Robustness of Programs

Examples and Class Materials
Homework and Announcements
