CS 236 - Discrete Structures
| Summary | Introduction to grammars and parsing; predicate and propositional logic; proof techniques; sets, functions, relations, relational data model; graphs and graph algorithms. | ||
|---|---|---|---|
| Prerequisites | CS 235 | ||
| Credits | 3 | ||
| Return to Course Listing | |||
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.
Purpose
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.
Objectives
At the end of this course, students should be able to:
- Use mathematics in the context of computer science. (In particular, you will be able to use the discrete structures of mathematics in support of computer programming, and you will be able to articulate how computer science concepts are formalized in the discrete structures of mathematics.)
- Write better programs by using discrete mathematical structures as the basis for many common programming problems (e.g., grammars for parsing, predicate calculus for logic programming, sets and algebras for relational databases, graphs and topological sorting for automating optimization).
- Demonstrate ability to build large programs by writing and integrating code from a diverse spectrum of program components
Topics
- 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)