Section # | Semester | Instructor | Website | Description |
---|---|---|---|---|

1 | Fall 2017 | Christophe Giraud-Carrier | https://learningsuite.byu.edu/view/G-Xm8Mu-TH8C.html | |

2 | Fall 2017 | Scott Woodfield | https://wiki.cs.byu.edu/cs-236/start | |

3 | Fall 2017 | Scott Woodfield | https://wiki.cs.byu.edu/cs-236/start | |

4 | Fall 2017 | Scott Woodfield | https://wiki.cs.byu.edu/cs-236/start |

Submitted by web master on Sat, 04/27/2013 - 9:35am

Discrete Structures

3

C++

Introduction to grammars and parsing; predicate and propositional logic; proof techniques; sets, functions, relations, relational data model; graphs and graph algorithms.

This document is not a syllabus. Instead, for ALL offerings of this course, this document states the purpose, expected objectives, and topics for the course. Faculty members teaching this course should adhere to these objectives and topics. Students taking this course can expect to achieve the objectives and cover the topics specified, and faculty members teaching follow-on courses can expect students to have been appropriately exposed to the prerequisite material as stated. The “hours” for topics listed below reflect the approximate number of 50-minute class periods (or equivalent) devoted to each topic.

CS 236 teaches fundamental ideas in discrete mathematics and their application to computer science. The course is a blend of basic theoretical concepts in computer science and a hands-on application of those ideas.

At the end of this course, students should be able to:

- Understand and be conversant with basic discrete mathematical structures (finite state machines, regular expressions, grammars, propositional calculus, proof techniques, predicate calculus, sets, relations, functions, graphs).
- Write complex programs by using mathematical concepts as the basis for solving programming problems (finite state machines for lexical analysis; grammars for parsing; propositional and predicate calculus for logic programming; sets and algebras for relational databases; algebras, graphs, and topological sorting for optimizing datalog query processing).
- Incrementally build sophisticated programs by a systematic design process based on discrete mathematics.
- Design a solution for a programming problem and justify the design as one that is maintainable and extendable by other programmers who understand and are conversant with discrete mathematical structures.

- Grammars, languages, and parsing (6 hours)
- Propositional logic (5 hours)
- Proofs and proof techniques (3 hours)
- Predicate calculus (6 hours)
- Sets, relations, and functions (6 hours)
- Relational and deductive databases (4 hours)
- Graphs and graph algorithms (8 hours)