CS 171 Home Page
Discrete Structures II
Spring 2016
This course continues the study of discrete mathematics which was begun in CS 170.
The mathematical and theoretical foundations of computer science are emphasized.
Topics to be covered include proofs of program correctness, running time analysis,
computability theory (and Turing machines), complexity theory (including the classes P, NP, etc.),
more on grammars & parsing, pushdown automata,
number theory & encryption, and counting techniques (especially recurrence relations and generating functions).
Important fundamental questions will be answered, such as whether all functions are computable.
Optional topics might be added as time allows, such as
the connection between Prolog and predicate logic (e.g. the resolution
principle). In spite of the emphasis on theory, the goal is to show how this theory is used in practical
applications in computer science. The practical applications that are emphasized include aspects of
the design of parsers and compilers, solving the travelling salesperson problem,
how to find and compare the computational complexity of various algorithms, and how to show that critical software is correct.
The implications for practical computing of unsolvable problems (such as the general halting problem) and problems with bad
computational complexity are also considered.
Further Information
 Documents, homilies, and speeches of Pope Francis
 Poverty, Hunger, and Social Justice in America
In honor of Martin Luther King, Jr.
 Course Syllabus
 Tentative Schedule
 Schedule for Br. David
 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.
 Download
Guidebooks for TI Calculators
 Example Prolog programs
Including tictac.pro.
 Br. David's Traveling Salesperson Problem: Software and Lab webpage.
 AMS Overview of the TSP
 Neil Simonetti's TSP Page

Using Mathematica to Solve a TSP
 RSA.com
 RSA Conference
 AlanTuring.net
 ACM Code of Ethics
 All Elementary Mathematics
See the algebra section
for mathematical induction, sequences, permutations and combinations, etc.
 The Probability Web: Teaching
Resources
This site has lots of links to resources on probability and statistics.
 The Math Forum: Discrete Mathematics
 National Curve Bank
 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 not equal to NP?
 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
Help is Available
Note on Flu
Because of the possibility of the flu affecting us on campus, please practice good hand washing, etc.
If a doctor will prescribe Tamiflu or similar for you, it is said that it reduces the length and the severity of the flu.
If you get the flu, please notify me by phone or email and stay home for 24 hours after the symptoms are over.
Check with me about what you miss. You will not be penalized for missing class in this situtation.
It is better to stay away from class and not spread the flu when you are ill.
Homework and Announcements
