Catalog Course Search Details

 Department:    CS

 Course #:    302

 Credits:    5

 Variable:     No

 IUs:    5

 CIP:    11.0701

 EPC:    CSACSBS

 REV:    2024

 Course Description  

Introduction to ideas and techniques from discrete mathematics that form the basis of data structures and algorithms used in Computer Science. Learn the fundamentals of graph theory, set theory, relations, enumeration, and recursive structures.

 Prerequisite  

Prerequisite: CS 202 and CS 301.

Contact Hours (based on 11 week quarter)

Lecture: 55

Lab: 0

Other: 0

Systems: 0

Clinical: 0

Intent: Distribution Requirement(s) Status:  

Academic N/A  

Equivalencies At Other Institutions

Learning Outcomes

After completing this course, the student will be able to:

1. Evaluate time and space complexity using industry standard notation (e.g., Big-O).
2. Develop a solution using recursive data structures.
3. Differentiate tree structures with basic operations on a tree structure.
4. Apply set theory using basic operations on a set.
5. Define data structures for implementing a set.
6. Compare and contrast different types of graphs in the context of graph theory.
7. Design algorithms which implement basic operations for use with a graph.
8. Define data structures for implementing the various types of graphs.
9. Examine various methods for calculating or estimating the computational complexity of an algorithm.

General Education Learning Values & Outcomes

Revised August 2008 and affects outlines for 2008 year 1 and later.

Course Contents

1. Trees:
   • Binary trees, binary search trees.
   • Pre-order, in-order, post-order traversal.
   • Generalized trees and Expression trees.
   • Heaps.
   • AVL, Splay, Red-Black trees.
2. Set Theory:
   • Hash table, structure, collision handling.
   • Disjoint set.
3. Graph Theory:
   • Minimal spanning trees.
   • Breadth first traversal and Depth first traversal.
   • Kruskal�s and Prim�s algorithm.
   • Euler and Hamiltonian circuit.