CS 251: Detailed Syllabus

The course plans to follow the syllabus outlined below. Changes, adjustments, and additions may be made during the semester.

Introduction and review of fundamentals

• Fundamental data structures for collections of objects: bags, queues, stacks, and linked lists
• Fundamental proof techniques:  direct, indirect, mathematical induction

Fundamental analysis tools

• Analyzing running times
• Asympotic analysis (best case, average case, worst case)
• Recursion

Searching and sorting

• Searching
• Sorting algorithms to use with caution
• Mergesort and Quicksort
• Radix Sort

Heaps

• Heaps as a priority queue
• Heapsort 

Trees

• Representations
• Traversals
• Computation on trees 

Symbol tables

• Common operations and different implementations
• Binary search trees

Balanced search trees

• 2-3 trees
• Red-black trees

Hash tables

• Hash functions
• Seperate chaining and linear probling and their performance and limitations

Introduction to graphs

• Represenations
• Traversal algorithms for undirected and directed graphs and their applications 
• Special graphs: trees and dags
• Minimum spanning trees and shortest paths 

Strings

• Sorting stings
• Tries 
• Compression
• Huffman codes