Algorithms Design and Analysis

Catalog description

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).