Course Content and Outcome Guide for CS 250
- Date:
- 25-MAY-2012
- Posted by:
- Gayathridevi Iyer
- Course Number:
- CS 250
- Course Title:
- Discrete Structures I
- Credit Hours:
- 4
- Lecture hours:
- 30
- Lecture/Lab hours:
- 0
- Lab hours:
- 30
- Special Fee:
- $12
Course Description
Introduces discrete structures and computational techniques in the areas of first-order logic, discrete proofs, number theory, sequences, induction, recursion, and set theory. Prerequisite: MTH 111. Audit available.Addendum to Course Description
Intended Outcomes for the course
Upon the successful completion of this course students will be able to:
Formulate, interpret, and apply mathematical concepts especially, techniques for computing sets, graphs and trees, recursive definitions, and discrete probability in real world contexts.
Use analytical problem solving strategies to solve problems using multiple approaches and to interpret the results in practical terms.
Utilize those techniques in discrete mathematics and logic that are used in the study and practice of computer science.
Be successful in subsequent coursework in the mathematical foundation of Computer Science.
Course Activities and Design
Outcome Assessment Strategies
Assessment must include:
1. At least two in-class proctored examinations, one of which may be the final exam, and
2. At least two of the following additional measures, where at least one includes writing:
a) take-home examinations. (group and/or individual)
b) projects. (group and/or individual)
c) quizzes. (group and/or individual)
d) graded homework/worksheets.
E) in-class activities.
F) attendance.
Course Content (Themes, Concepts, Issues and Skills)
Major Topics:
- Describe basic properties of sets, bags, tuples, relations, graphs, trees, and functions.
- Perform traversals of graphs and trees; construct simple functions by composition of known functions; determine whether simple functions are injective, surjective, or bijective; and classify simple functions by rate of growth.
- Describe the concepts of countable and uncountable sets, and apply the diagonalization method to construct elements that are not in certain countable sets.
- Construct inductive definitions for sets, construct grammars for languages (sets of strings), and construct recursive definitions for functions and procedures.
- Determine whether a binary relation is reflexive, symmetric, or transitive and construct closures with respect to these properties.
- Construct a topological sort of a partially ordered set and determine whether a partially ordered set is well-founded.
- Use elementary counting techniques to count simple finite structures that are either ordered or unordered, to count the worst case number of comparisons and, with discrete probability, to count the average number of comparisons for simple decision trees.
- Find closed form solutions for simple recurrences using the techniques of substitution, cancellation, and generating functions.
- Demonstrate standard proof techniques and the technique of inductive proof by writing short informal proofs about simple properties of numbers, sets, and ordered structures.