YoVDO

Introduction to Graduate Algorithms

Offered By: Georgia Institute of Technology via Udacity

Tags

Algorithms and Data Structures Courses Linear Programming Courses Algorithm Design Courses Graph Algorithms Courses Randomized Algorithms Courses Dynamic programming Courses NP-completeness Courses Fast Fourier Transform Courses Divide-and-Conquer Courses

Course Description

Overview

This is a graduate-level course in the design and analysis of algorithms. We study techniques for the design of algorithms (such as dynamic programming) and algorithms for fundamental problems (such as fast Fourier transform or FFT).

In addition, we study computational intractability, specifically, the theory of NP-completeness. The main topics covered in the course include: dynamic programming; divide and conquer, including FFT; randomized algorithms, including RSA cryptosystem and hashing using Bloom filters; graph algorithms; max-flow algorithms; linear programming; and NP-completeness.


Syllabus

  • Dynamic Programming
    • Fibonacci Numbers, Longest Increasing Subsequence (LIS), Longest Common Subsequence (LCS),Knapsack, Chain Matrix Multiplication,Shortest Path Algorithms
  • Randomized Algorithms
    • Modular Arithmetic: Fast Modular Exponentiation, Multiplicative Inverses,RSA Cryptosystem: Fermat's Little Theorem, RSA Protocol, Primality Testing,Hashing: Traditional Chain Hashing, Bloom Filters
  • Divide and Conquer
    • Fast Integer Multiplication,Linear-Time Median,Fast Fourier Transform
  • Graph Algorithms
    • Strongly Connected Components, 2-Satisfiability,Minimum Spanning Tree,Markov Chains, PageRank
  • Max-Flow Problems
    • Ford-Fulkerson Algorithm,Max-Flow Min-Cut Theorem, Edmonds-Karp Algorithm,Max-Flow applied to Image Segmentation
  • Linear Programming
    • Simplex Algorithm,Weak and Strong Duality,Max-SAT Approximation
  • NP-Completeness
    • Complexity Classes: P, NP, NP-Complete,NP-Complete Problems: 3-SAT, Independent Set, Clique, Vertex Cover, Knapsack, Subset-Sum,Halting Problem

Taught by

Arpan Chakraborty and Eric Vigoda

Tags

Related Courses

Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera
Unpredictable? Randomness, Chance and Free Will
National University of Singapore via Coursera
Biology Meets Programming: Bioinformatics for Beginners
University of California, San Diego via Coursera
Finding Hidden Messages in DNA (Bioinformatics I)
University of California, San Diego via Coursera
Algorithms for Big Data
Indian Institute of Technology Madras via Swayam