CPSC 8400 Design and Analysis of Algorithms

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!

Grab it

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: 2 Weeks]

Module 2: 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.5 Weeks]

Module 3: Recursion

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

Module 4: 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.5 Weeks]

Module 5: Fundamental Data Structures, Continued

This module covers multi-dimensional search structures, amortization, memory-conscious structures (B-trees), and skip lists. [Workload: 2 Weeks]

Module 6: Hashing

This module covers hash tables and distributed hash tables, universal hashing, polynomial hashing of large objects, and applications of hashing across different computing subfields. [Workload: 1.5 Weeks]

Module 7: Discrete Optimization

This module covers greedy algorithms, dynamic programming, heuristics based on iterative refinement, multi-scale methods, pruned exhaustive search, and hard problems and approximation algorithms. [Workload: 2 Weeks]

Module 8: Graph Algorithms

This module covers gradient descent and Newton's method, stochastic gradient descent, gradient-free methods, continuous relaxations of discrete problems, convexity, optimization with constraints, and common types of optimization problems. [Workload: 1.5 Weeks]