CS 302 - Advanced Data Structures and File Processing

Description:
Introduction to non-linear data structures (balanced search trees, priority queues, graphs, maps, sets, hashing data structures), their Java implementations as abstract data types, and basic algorithms (sorting, greedy, graph algorithms).

Prerequisites:
Prerequisites: Academic Writing I and Academic Writing II and CS 110 and CS 111 and CS 301; MATH 172 or MATH 173, with a grade of C or higher in all courses.

Credits: (4)

Learner Outcomes:
Upon successful completion of this course, the student will be able to:

Demonstrate the correct use and application of non-linear data structures: trees, search trees, balanced trees (AVL trees, red-black trees), heaps, priority queues, hashing, maps, sets, matrices, and graphs
Design and apply binary search trees, balanced search trees and heaps as generic classes
Demonstrate the priority queues, heaps and heapsort using PriorityQueue and TreeIterator classes
Demonstrate and examine asymptotic analysis performance of the following sorting algorithms: insertion sort, selection sort, heapsort, bubble sort, mergesort, quicksort, tree sort, topological sorting; implement sorting algorithms using the Comparator interface.
Discuss, analyze and apply hashing, hash tables, hashing by chaining, the uniform hashing assumption
Discuss, analyze and apply Prim (minimum spanning tree), Dijkstra (shortest path)
Formulate graph data structures using the BreadthFirstIterator and DepthFirstIterator classes

Learner Outcomes Approval Date:
1/22/21

Anticipated Course Offering Terms and Locations:
Fall Locations: EllensburgWinter Locations: EllensburgSpring Locations: Ellensburg