This course is intended as an intermediate course to the design and analysis of algorithms for some of the most frequently encountered combinatorial problems. The course aims to provide familiarity with general algorithmic techniques, performance measures, analysis tools and problem areas. In this course, we will focus on developing an understanding of the algorithmic design process: how to identify the algorithmic needs of an application and apply algorithmic design techniques to solve those problems. The students will also learn how to identify problems for which no exact, efficient algorithm is known. More specifically, topics include: Fundamentals (Basic Programming Model, Data Abstraction, Bags, Queues, and Stacks, Analysis of Algorithms), Sorting (Elementary Sorts, Mergesort, Quicksort, Priority Queues, applications), Searching (Symbol Tables, Binary Search Trees, Balanced Search Trees, Hash Tables, applications), Graphs (Undirected Graphs, Directed Graphs, Minimum Spanning Trees, Shortest Paths), Strings (String Sorts, Tries, Substring Search, Regular Expressions, Data Compression), Context (applications). Prerequisites: COSC 2336 and MATH 2413 with a minimum grade of "C"
Spring 2019, Spring 2018, Spring 2017, Fall 2016, Spring 2016