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
Examples and Class Materials
Homework
Tests
- Final Exam:
- Wed, May 7, 11:00 am - 1:00 pm
- Open book, open notes exam. You will need your book and handouts to answer
many of the problems.
- Topics: generating functions (used to solve recurrences), proofs of program correctness,
infinite sets (and what this tells us about computable functions), Prolog and its connection
to predicate logic.
- You may use a calculator (though it is probably not helpful with these particular topics).
Calculators may not be shared during the exam.
Cell phones, laptops, and other devices may not be used.
|
|
Maintained by: Br. David Carlson
Last updated: May 01, 2008
Disclaimer
|
|
