CIS Department > Br. David Carlson

CS 171 Home Page

Discrete Structures II

Spring 2008

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 anaylsis, computability theory (using Turing machines and the like), complexity theory, grammars & parsing, and counting techniques (especially recurrence relations and generating functions). 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, practical applications are also brought out (such as the use of this theory in creating parsers and compilers).

Further Information

Course Syllabus
Tentative Schedule
Parser Freeware and Examples
Dr. Botsko's Mathematica web page
Famous Problems and Proofs
mathworld.wolfram.com
Contains a wealth of resources.
functions.wolfram.com
Provides information on many well-known and lesser-known functions.
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.
Textbook web site
The textbook student center 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.
Onno Waalewijn's TSP Software
The TSP at Princeton
TSPBIB Home Page
Neil Simonetti's TSP Page
Using Mathematica to Solve a TSP
AlanTuring.net
The Math(ematica) Behind Numb3rs (the TV show)

Examples and Class Materials

Instructor: Br. David Carlson