CIS Logo SVC Logo

   Computing & Information Systems


Schoology Facebook        Search CIS Site      Tutorials

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, push-down 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

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 e-mail 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

Instructor: Br. David Carlson

Maintained by: Br. David Carlson
Last updated: July 05, 2017