CpSc 311 Section 01 August 26, 2013
Course Outline

Introduction

Explain basic terminology

Sets

Relations

Functions

Trees

Graphs

Applicability to computing

Functions

Relations  Equivalence relations, closures

Sets  Finite, countably infinite, uncountably infinite sets

Trees

Using structure in programs

Functions

Relations

Sets

Trees

Formal Methodology

Binary operators

Symbolic logic

DeMorgan’s laws

Proof techniques

Proof by induction

Using proofs to solve problems such as puzzles

Demonstrate basic counting principles

Diagonalization

pigeonhole principle

Relate the ideas of mathematical induction to recursion

Computing and analysis (3 hours)

permutations of a set

combinations of a set

evaluate the runtime performance of alternative algorithms

Probabilities (3 hours)

Discrete probabilities

Distributions

Monte Carlo method

Apply the tools of probability to solve problems

the average case analysis of algorithms

hashing

Computational Complexity

Asymptotic analysis of bounds

BigO, littleO

Worstcase

Best Case

Average case

TimeSpace tradeoffs

Recurrence relations

Introduction to Graphs and Trees

Binary Search Tree

Spanning Trees

Shortest Path

Undirected graphs

Directed graphs

Graphs

Cycles

Traversability

Connectedness

Distance

Traversal methods

Demonstrate and implement tree traversals

Demonstrate and implement graph traversals

Model problems in computing

Graphs

trees

Markov chains

Data structures and algorithms for graphs and trees

Enumeration

practical instantiation

Producing a random graph, tree, and table
Computer Science Department
Course Competency Plan
COURSE: CpSc 311  Discrete of Computational Structures
Catalog Description: Introduces computational implementations of the mathematical structures most frequently used in computing including sets, equivalence relations, functions, graphs, trees and standard logic. Also introduces automata, formal languages, countability, decidability and computational complexity, Markov and stochastic processes. The course will stress traditional programming and mathematical approaches to these structures such as the use of recursion, elementary data structures, and proof techniques to instantiate, parse, traverse, demonstrate correctness, or use these computational objects. (Prereq: CpSc140, Math 120)
Course Outcomes: This course and its outcomes support the Information Technology Learning Outcome of Problem Solving and Critical Thinking (PS&CT) . This Information Technology Learning Outcomes is tied directly to the University Wide Outcome of Critical Thinking and Problem Solving.
Program Objectives Assessed in CpSc 427
Degree

Program Objective

Assessed Course Objective

IT

I.a. Apply programming and system management techniques to address information technology problems

1. Build programs and prove theorems concerning fundamental structures of discrete mathematics.

Additional Course Objectives include:
The student will be able to:
1. Define basic computational terms and perform computational operations associated with sets, functions, relations, trees, and graphs.
2.Apply formal methods of symbolic logic and proof techniques used to solve traditional computing problems.
3.Apply the tools of probability to solve problems.
4. Evaluate the runtime performance of alternative algorithms.
5. Model problems in computing using graphs, trees and Markov chains.
6. Relate graphs and trees to data structures, algorithms and counting.
Share with your friends: 