CS 26 - Discrete Structures for Computer Science

Description

Introduction to the essential discrete structures used in Computer Science, with emphasis on their applications. Includes elementary formal logic and set theory, elementary combinatorics, recursive programming and algorithm analysis, Boolean Algebra, digital logic, combinatorial circuits, circuit design and minimization, and computer arithmetic.

Prerequisites

Completion of CS 10 or equivalent experience.

Course Outcomes

  1. Convert between decimal, hexadecimal and binary representation of numbers.
  2. Convert negative decimal numbers to two's compliment binary form.
  3. Analyze sets for complement, union and intersection.
  4. Construct Venn diagrams to illustrate set relationships and operations.
  5. Evaluate sets for reflexivity, symmetry, and transitivity.
  6. Analyze inputs and outputs for the creation of functions.
  7. Identify problems appropriately solved with recursive functions.
  8. Write recursive functions.
  9. Convert floating point notation to standard decimal and binary.
  10. Recognize digital logic gates and their representation in graphical, algebraic, and truth table form.
  11. Convert Boolean functions between algebraic expressions, truth tables and circuit diagrams.
  12. Convert an English-language statement of compound propositions (including and, or, not, and quantifiers) to a symbolic form.
  13. Design and construct combinational circuits from verbal descriptions.
  14. Manipulate circuits through the application of DeMorgan's Theorem.
  15. Minimize circuits by creating Karnaugh Maps.
  16. Create regular expressions for sets of strings.
  17. Create a finite-state automaton from a verbally described set of strings.

Faculty

Barry Brown

Availability

This course is offered every semester in a traditional classroom setting.