Design and Analysis of Algorithms

Overview

The study of algorithms is a significant part of the foundation for the discipline of computing. Over the past several decades, research in algorithmic computer science has advanced at a rapid pace its contributions have had a profound impact on almost every area of science and industry. In this graduate-level course, we aim to provide a modern introduction to the study of algorithms that is both broad and deep. The primary goals of the course are: (1) to become proficient in the application of fundamental algorithm design techniques, as well as the main tools used in the analysis of algorithms, (2) to study and analyze different algorithms for many of the most common types of “standard” algorithmic problems, and (3) to improve one’s ability to implement algorithmic ideas in code.

Syllabus

Module 1: Preliminary Concepts and Fundamentals

This module covers how to analyze performance of algorithms, models of computation, basic data structures, algorithm design techniques, and common sorting algorithms. [Workload: 1 Week]

Module 2: Programming Assignment #1

This module asks learners to apply the knowledge gained in Module 1 to a Programming Assignment with 3 parts. [Workload: 1 Week]

Module 3: Randomization

This module covers methods for analyzing expected running time and average-case performance, randomized quicksort and quickselect, examples of randomized algorithms and data structures, and "high probability" bounds. [Workload: 1 Week]

Module 4: Recursion

This module covers techniques for analyzing recursive algorithms ("divide and conquer"), recursive thinking, and examples of recursion in algorithm design. [Workload: 1 Week]

Module 5: Programming Assignment #2

This module asks learners to apply the knowledge gained in previous modules, particularly Module 4, to a Programming Assignment. [Workload: 1 Week]

Module 6: Fundamental Data Structures

This module covers priority queues, binary search trees for representing sets, maps, and sequences, randomized and amortized tree balancing mechanisms, and sweep line methods. [Workload: 1 Week]