See all results for
    1. Year of MOOC-based Degrees: A Review of MOOC Stats and Trends in 2018
    2. Are MOOCs Going to Disappear? 4 Challenges to Overcome
    3. The Definitive List of Courses for Learning About the United Nations Sustainable Development Goals
    See more
    1. Sign in
    2. Register

    Get started with custom lists to organize and share courses.

    Sign up

    Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

    Introduction to Graduate Algorithms

    Georgia Institute of Technology via Udacity

    Go to class

    Taken this course? Share your experience with other students. Write review

    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.



    Why Take This Course?

    The design and analysis of algorithms form an essential basis for computer science. This course is useful for those who want to pursue advanced studies in computer science, as well as those who want to work as a software engineer.

    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

    algorithms algorithms core

    Help Center

    Most commonly asked questions about Udacity Udacity

    Browse More Udacity Articles

    Highest Rated Courses

    Browse More Algorithms and Data Structures courses

    Reviews for Udacity's Introduction to Graduate Algorithms
    Based on 0 reviews

    • 5 star 0%
    • 4 star 0%
    • 3 star 0%
    • 2 star 0%
    • 1 star 0%

    Did you take this course? Share your experience with other students.

    Write a review

    Class Central

    Get personalized course recommendations, track subjects and courses with reminders, and more.

    Sign up for free

    Never stop learning Never Stop Learning!

    Get personalized course recommendations, track subjects and courses with reminders, and more.

    Sign up for free