Search


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.

Instructor: Br. David Carlson





Maintained by: Br. David Carlson
Last updated: May 01, 2008
Disclaimer