CS 171 Home Page
Discrete Structures II
Spring 2018
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 traveling salesperson problem,
finding and comparing 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 Course Schedule
 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
 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 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
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
 See Schoology and, for part of the course, Webwork.

Exams
 First Exam:
 Wed, Feb 14
 Covers all that we have done thus far in the course: divisibility, modular arithmetic, the extended Euclidean algorithm,
solving congruences, RSA encryption, grammars, regular expressions, finite state machines, language recognition,
pushdown automata, parsing, Turing machines, computability, Turing's thesis, Church's thesis, and the
general halting problem. Does not cover complexity theory.
 Openbook, open notes exam. You may bring anything on paper that you wish.
 Bring a good hand calculator as it is likely to be needed on some of the questions.
Calculators may not be shared by students.
 Cell phones and pagers should be turned off and put away.
 No laptops or other computers may be used.
 Second Exam:
 Wed, Mar 28
 Covers what we have done since the first exam. This includes Prolog, its connection to logic, resolution,
unification, proofs of program correctness, infinite sets and what they tell us about computable and incomputable
functions.
 Openbook, open notes exam. You may bring anything on paper that you wish.
 You may use a hand calculator if you wish, but it is probably not of much use with this type of material.
Calculators may not be shared by students.
 Cell phones and pagers should be turned off and put away.
 No laptops or other computers may be used.
 Final Exam:
 Mon, May 7, 4:00 pm  6:00 pm

