Discipline: Computer Science
CIS-Computer Information Systems
 Degree Credit  [X]
Non Credit  [ ]
Nondegree Credit  [ ]
Comm Service  [ ]
 

Riverside Community College District
Integrated Course Outline of Record

Computer Science 7


College: R_X_ M___ N_X_
CSC-7: Discrete Structures
Same as: CIS- 7
 Lecture Hours: 54
Lab Hours: 18
Units: 3.00
 
COURSE DESCRIPTION
Prerequisite(s): CSC 5: Programming Concepts and Methodology I: C++ or CIS 5: Programming Concepts and Methodology I:C++
This course is an introduction to the discrete structures used in Computer Science with an emphasis on their applications. Topics covered include: Functions, Relations and Set; Basic Logic; Proof Techniques; Basics of Counting; Graphs and Trees; and Discrete Probability. 54 hours lecture and 18 hours laboratory.(TBA option)
 
SHORT DESCRIPTION FOR CLASS SCHEDULE
Introduction to discrete structures for Computer Science Majors. (Same as CIS-7)
 
ENTRY SKILLS
Before entering the course, students will be able to:
  1. Summarize the evolution of programming languages illustrating how this history has led to the paradigms available today.
    • CSC 5 - Describe the software development life-cycle
    • CSC 5 - Explain what an algorithm is and its importance in computer programming.

  2. Discuss the importance of algorithms in the problem-solving process. Identify the necessary properties of good algorithms.
    • CSC 5 - Demonstrate different forms of binding, visibility, scoping, and lifetime management.
    • CSC 5 - Describe the principles of structured programming and be able to design, implement and test structured programs.

  3. Identify the information input requirements, synthesize the algorithmic steps needed to transform the data input into the required output information, and organize the output format to facilitate user communication.
    • CSC 5 - Apply the principles of logical and programming concepts to develop solutions for gaming, business, scientific and mathematical problems.
    • CSC 5 - Use pseudocode, flowcharts, and a programming language to implement, test, and debug algorithms for solving problems.  Identify the information requirements, synthesize the algorithmic steps needed to transform the data input into the required output information, and organize the output format to facilitate user communication.

  4. Create computer programs in C++ using the principles of structured programming. Analyze and explain the behavior of simple programs involving the fundamental programming constructs. Modify and expand programs that use standard conditional and iterative control structures and functions. Design, implement, test, and debug programs that use fundamental programming constructs. Choose appropriate conditional constructs. Apply techniques of structured decomposition.
    • CSC 5 - Create computer programs using the principles of structured programming and demonstrate the use of an IDE with appropriate libraries.  Design, implement, test, and debug programs that use fundamental programming constructs:  basic computation, simple I/O, standard conditional and iterative structures, and functions.
STUDENT LEARNING OUTCOMES
 Upon successful completion of the course, students should be able to:

Describe how formal tools of symbolic logic are used to model real-life situations, including those arising in computing contexts such as program correctness, database queries, and algorithms.

  1. Critical Thinking - Integrate knowledge across a range of contexts
  2. Critical Thinking - Generalize appropriately from specific contexts
  3. Critical Thinking - Construct sound arguments and evaluate arguments of others

Relate the ideas of mathematical induction to recursion and recursively defined structures.

  1. Breadth of Knowledge - Use the symbols and vocabulary of mathematics to solve problems and communicate the results
  2. Critical Thinking - Generalize appropriately from specific contexts
  3. Information Skills - Locate, evaluate and use information effectively

Analyze a problem to create relevant recurrence equations.

  1. Critical Thinking - Analyze and solve complex problems across a range of academic and everyday contexts

Demonstrate different traversal methods of trees and graphs.

  1. Information Skills - Demonstrate computer literacy
  2. Critical Thinking - Integrate knowledge across a range of contexts

Apply the binomial theorem to independent events and Bayes' theorem to dependent events.

  1. Communication Skills - Write with precision and clarity to express complex thought
  2. Breadth of Knowledge - Use the symbols and vocabulary of mathematics to solve problems and communicate the results
 
COURSE CONTENT
  1. Functions, Relations and Sets
    1. Functions (surjections, injections, inverses, composition)
    2. Relations (reflexivity, symmetry, transitivity, equivalence relations)
    3. Sets (Venn diagrams, complements, Cartesian products, power sets)
    4. Pigeonhole principles
    5. Cardinality and countability
  2. Basic Logic
    1. Propositional logic
    2. Logical connectives
    3. Truth tables
    4. Normal forms (conjunctive and disjunctive)
    5. Validity
    6. Predicate logic
    7. Universal and existential quantification
    8. Modus ponens and modus tollens
    9. Limitations of predicate logic
  3. Proof Techniques
    1. Notions of implication, converse, inverse, contrapositive, negation, and contradiction
    2. The structure of mathematical proofs
    3. Direct proofs
    4. Proof by counterexample
    5. Proof by contradiction
    6. Mathematical induction
    7. Strong induction
    8. Recursive mathematical definitions
    9. Well orderings
  4. Basics of Counting
    1. Counting arguments
    2. Sum and product rule
    3. Inclusion-exclusion principle
    4. Arithmetic and geometric progressions
    5. Fibonacci numbers
    6. The pigeonhole principle
    7. Permutations and combinations
    8. Basic definitions
    9. Pascal’s identity
    10. The binomial theorem
    11. Solving recurrence relations
    12. Common examples
    13. The Master theorem
  5. Graphs and Trees
    1. Trees
    2. Undirected graphs
    3. Directed graphs
    4. Spanning trees/forests
    5. Traversal strategies
  6. Discrete Probability
    1. Finite probability space, probability measure, events
    2. Conditional probability, independence, Bayes’ theorem
    3. Integer random variables, expectation
    4. Law of large numbers
 
METHODS OF INSTRUCTION
 Methods of instruction used to achieve student learning outcomes may include, but are not limited to:

  • Class lectures, discussions, and demonstrations of formal logic, proofs, recursion, analysis of algorithms, sets, combinatorics, probability theory, number theory, relations, functions, matrices, graphs, trees, and Boolean algebra.
  • Drills and pattern practices utilizing hand-outs and/or computer-based tools in order to assist the students in mastering the techniques involved in applying the discrete mathematical principles and techniques to the solution of applications related the topics mentioned above.
  • Provision and employment of a variety of learning resources such as videos, slides, audio tapes, computer-based tools, manipulatives, and worksheets in order to address multiple learning styles and to reinforce material.
  • Pair and small group activities, discussions, and exercises in order to promote mathematics discovery and enhance problem solving skills.
 
METHODS OF EVALUATION
 Students will be evaluated for progress in and/or mastery of learning outcomes by methods of evaluation which may include, but are not limited to:

  • Computer programs designed to demonstrate the acquisition of an understanding of formal logic, proofs, recursion, analysis of algorithms, sets, combinatorics, probability theory, number theory, relations, functions, matrices, graphs, trees, and Boolean algebra.
  • Quizzes/examinations designed to measure students’ degree of mastery of the mathematical theories that forms the foundation of computer science.
  • Collaborative projects designed to demonstrate successful understanding and application of the mathematical theories that forms the foundation of computer science.
  • Computer Laboratory assignments/projects designed to clarify students’ individual understanding of formal logic, proofs, recursion, analysis of algorithms, sets, combinatorics, probability theory, number theory, relations, functions, matrices, graphs, trees, and Boolean algebra strengths and areas of improvement related to these skills.
  • Final examination designed to evaluate students’ overall achievement of course objectives discrete mathematics.
SAMPLE ASSIGNMENTS

Outside-of-Class Reading Assignments
  • Read and understand college level texts concerning recursion, algorithms, combinatorics, number theory, matrices, graphs and trees as applies to Computer Science.

Outside-of-Class Writing Assignments
  • There will be several assignments where the student demonstrates with computer code a thorough understanding of the formal logic of computer science.  These algorithms/code will cover proofs, recursion, combinatorics, relations, functions, graphs, trees, Boolean algebra and modeling.

Other Outside-of-Class Assignments
  • The outside of class assignments will be the completions of algorithms/code development started in class after the topics are presented. 
 
COURSE MATERIALS
 All materials used in this course will be periodically reviewed to ensure that they are appropriate for college level instruction. Possible texts include:

  • Gersting, J.. Mathematical Structures for Computer Science. 6th ed. Freeman, 2011.
  • Lipschutz, S., Lipson, M.. Schaum's Outline Discrete Mathematics. 3rd ed. Schaum, 2009.
  • Rosen, K.. Discrete Mathematics and It's Application. 7th ed. McGraw-Hill, 2011.
01/22/2013
4726