CS 302 - Discrete Structures II

Credits: 5
Variable Credit Course: No

Lecture Hours: 55
Lab Hours: 0
Worksite/Clinical Hours: 0
Other Hours (LIA/Internships): 0

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: CS 202 and CS 301 both with a grade of C or higher. Admission to BSCS program and Dept. Chair permission.
Meets FQE Requirement: No
Integrative Experience Requirement: No

Student Learning Outcomes

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

Course Contents

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

Instructional Units: 5