CpSc 311 Section 01 August 26, 2013 Course Outline

1. 
   Introduction
   
   1. 
      Explain basic terminology
      
      1. 
         Sets
         
      2. 
         Relations
         
      3. 
         Functions
         
      4. 
         Trees
         
      5. 
         Graphs
         
   2. 
      Applicability to computing
      
      1. 
         Functions
         
      2. 
         Relations - Equivalence relations, closures
         
      3. 
         Sets - Finite, countably infinite, uncountably infinite sets
         
      4. 
         Trees
         
   3. 
      Using structure in programs
      
      1. 
         Functions
         
      2. 
         Relations
         
      3. 
         Sets
         
      4. 
         Trees
         
2. 
   Formal Methodology
   
   1. 
      Binary operators
      
   2. 
      Symbolic logic
      
   3. 
      DeMorgan’s laws
      
3. 
   Proof techniques
   
   1. 
      Proof by induction
      
   2. 
      Using proofs to solve problems such as puzzles
      
4. 
   Demonstrate basic counting principles
   
   1. 
      Diagonalization
      
   2. 
      pigeonhole principle
      
5. 
   Relate the ideas of mathematical induction to recursion
   
6. 
   Computing and analysis (3 hours)
   
   1. 
      permutations of a set
      
   2. 
      combinations of a set
      
   3. 
      evaluate the run-time performance of alternative algorithms
      
7. 
   Probabilities (3 hours)
   
   1. 
      Discrete probabilities
      
   2. 
      Distributions
      
   3. 
      Monte Carlo method
      
8. 
   Apply the tools of probability to solve problems
   
   1. 
      the average case analysis of algorithms
      
   2. 
      hashing
      
9. 
   Computational Complexity
   
   1. 
      Asymptotic analysis of bounds
      
   2. 
      Big-O, little-O
      
   3. 
      Worst-case
      
   4. 
      Best Case
      
   5. 
      Average case
      
   6. 
      Time-Space trade-offs
      
   7. 
      Recurrence relations
      
10. 
    Introduction to Graphs and Trees
    
    1. 
       Binary Search Tree
       
    2. 
       Spanning Trees
       
    3. 
       Shortest Path
       
    4. 
       Undirected graphs
       
    5. 
       Directed graphs
       
11. 
    Graphs
    
    1. 
       Cycles
       
    2. 
       Traversability
       
    3. 
       Connectedness
       
    4. 
       Distance
       
12. 
    Traversal methods
    
    1. 
       Demonstrate and implement tree traversals
       
    2. 
       Demonstrate and implement graph traversals
       
13. 
    Model problems in computing
    
    1. 
       Graphs
       
    2. 
       trees
       
    3. 
       Markov chains
       
14. 
    Data structures and algorithms for graphs and trees
    
    1. 
       Enumeration
       
    2. 
       practical instantiation
       
    3. 
       Producing a random graph, tree, and table
       

Computer Science Department

COURSE: CpSc 311 - Discrete of Computational Structures

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 run-time performance of alternative algorithms.

5. Model problems in computing using graphs, trees and Markov chains.