CS 302 - Advanced Data Structures and File Processing

Description:
Sequential, random access and indexed file organizations; B-trees; external searching and sorting; I/O buffering. Course will be offered every year. Course will not have an established scheduling pattern.

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/23/20

Anticipated Course Offering Terms and Locations:
Fall Locations: Ellensburg Winter Locations: Ellensburg Spring Locations: Ellensburg