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, NP-complete, and NP hard), grammars and parsing, push-down 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 Shroeder-Bernstein 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, self-assessment
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 NP-complete, 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
| 
Search CIS Site
Tutorials