Introduction to Graduate Algorithms

www.udacity.com/course/introduction-to-graduate-algorithms--ud401

 

 

gt-algorithms.com/

 

 

Intro to Grad Algorithms

Lecture videos and notes
Georgia Tech CS6515 Intro to Grad Algorithms

Lecture videos:

• Open access link (note, quizzes don’t work there)
• Udacity (need a free Udacity account)

Old course page:  Spring ’18

---

 1

Dynamic Programming

• Fibonacci Numbers
• Longest Increasing Subsequence (LIS)
• Longest Common Subsequence (LCS)
• Knapsack
• Chain Matrix Multiplication
• Shortest Path Algorithms

LESSON 2

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

LESSON 3

Divide and Conquer

• Fast Integer Multiplication
• Linear-Time Median
• Fast Fourier Transform

LESSON 4

Graph Algorithms

• Strongly Connected Components
• 2-Satisfiability
• Minimum Spanning Tree
• Markov Chains
• PageRank

LESSON 5

Max-Flow Problems

• Ford-Fulkerson Algorithm
• Max-Flow Min-Cut Theorem
• Edmonds-Karp Algorithm
• Max-Flow applied to Image Segmentation

LESSON 6

Linear Programming

• Simplex Algorithm
• Weak and Strong Duality
• Max-SAT Approximation

LESSON 7

NP-Completeness

• Complexity Classes: P
• NP
• NP-Complete
• NP-Complete Problems: 3-SAT
• Independent Set
• Clique
• Vertex Cover
• Knapsack
• Subset-Sum
• Halting Problem

 

 

레슨 1

동적 프로그래밍

• 피보나치 수
• LIS (Longest Increasing Subsequence)
• 가장 긴 공통 하위 시퀀스 (LCS)
• 배낭
• 연쇄 행렬 곱셈
• 최단 경로 알고리즘

제 2과

무작위 알고리즘

• 모듈 식 산술 : 빠른 모듈 식 지수
• 곱셈 역
• RSA Cryptosystem : Fermat의 작은 정리
• RSA 프로토콜
• 소수 테스트
• 해싱 : 전통적인 체인 해싱
• 블룸 필터

제 3과

분할 및 정복

• 빠른 정수 곱셈
• 선형 시간 중앙값
• 고속 푸리에 변환

제 4과

그래프 알고리즘

• 강력하게 연결된 구성 요소
• 2- 만족
• 최소 스패닝 트리
• 마르코프 체인
• 페이지 랭크

제 5과

Max-Flow 문제

• Ford-Fulkerson 알고리즘
• Max-Flow Min-Cut 정리
• Edmonds-Karp 알고리즘
• 이미지 분할에 적용된 Max-Flow

제 6과

선형 프로그래밍

• 단순 알고리즘
• 약하고 강한 이중성
• Max-SAT 근사치

제 7과

NP- 완전성

• 복잡성 등급 : P
• NP
• NP- 완료
• NP- 완전한 문제 : 3-SAT
• 독립 세트
• 도당
• 정점 커버
• 배낭
• 부분 집합 합계
• 중단 문제

---

LESSON 1

Introduction to Graduate Algorithms

Overview of main topics covered, course webpage available at: https://gt-algorithms.com

VIEW LESSON

 

100% VIEWED

SHRINK CARD

1. Continue

    

LESSON 2

DP1: FIB, LIS, LCS

Dynamic programming: Toy problem (Fibonacci numbers), Longest Increasing Subsequence (LIS), and Longest Common Subsequence (LCS).

CONTINUE

 

3%

1 hour left

1. Start

    

LESSON 3

DP2: Knapsack, Chain Multiply

Dynamic programming: Knapsack, and Chain Matrix Multiplication.

START

 

NOT STARTED

53 minutes

1. Start

    

LESSON 4

DP3: Shortest Paths

Dynamic programming algorithms for solving various shortest path problems on graphs.

START

 

NOT STARTED

47 minutes

1. Start

    

LESSON 5

RA1: Modular Arithmetic

Modular Arithmetic: Fast Modular Exponentiation and Multiplicative Inverses.

START

 

NOT STARTED

35 minutes

1. Start

    

LESSON 6

RA2: RSA

RSA Cryptosystem: Fermat's Little Theorem, RSA Protocol, and Primality Testing.

START

 

NOT STARTED

1 hour 9 minutes

1. Start

    

LESSON 7

RA3: Bloom Filters

Lecture about Hashing: Toy problem of Balls into Bins, Traditional Chain Hashing, and Bloom Filters.

START

 

NOT STARTED

47 minutes

1. Start

    

LESSON 8

DC1: Fast Integer Multiplication

Faster Divide-and-Conquer Algorithm for Multiplying Large Integers.

START

 

NOT STARTED

30 minutes

1. Start

    

LESSON 9

DC2: Linear-Time Median

Linear-time Divide-and-Conquer Algorithm for Finding the Median from an unsorted list.

START

 

NOT STARTED

30 minutes

1. Start

    

LESSON 10

 

DC3: Solving Recurrences

Refresher Lecture about Solving Recurrences.

START

 

NOT STARTED

15 minutes

1. Start

    

LESSON 11

DC4: FFT - Part 1

High-level approach for polynomial multiplication and FFT (Fast Fourier Transform). Primer on complex numbers, including complex roots of unity.

START

 

NOT STARTED

32 minutes

1. Start

    

LESSON 12

DC5: FFT - Part 2

FFT and polynomial multiplication algorithms, and inverse FFT.

START

 

NOT STARTED

32 minutes

1. Start

    

LESSON 13

GR1: Strongly Connected Components

Connectivity: Connected components of undirected graphs, Topological sorting of a DAG, and strongly connected components of general directed graphs.

START

 

NOT STARTED

50 minutes

1. Start

    

LESSON 14

GR2: 2-Satisfiability

Polynomial-time algorithm for 2-SAT, using the SCC algorithm.

START

 

NOT STARTED

30 minutes

1. Start

    

LESSON 15

GR3: Minimum Spanning Tree

Minimum Spanning Tree (MST): Cut Property for MST's, and Kruskal's MST algorithm.

START

 

NOT STARTED

36 minutes

1. Start

    

LESSON 16

GR4: Markov Chains and PageRank

Introduction to Markov Chains, and an exposition of the PageRank algorithm.

START

 

NOT STARTED

54 minutes

1. Start

    

LESSON 17

MF1: Ford-Fulkerson Algorithm

Max-flow: Problem statement, residual network, and Ford-Fulkerson algorithm.

START

 

NOT STARTED

40 minutes

1. Start

    

LESSON 18

MF2: Max-Flow Min-Cut

Max-Flow Min-Cut Theorem: Statement and Proof, and proof of correctness of Ford-Fulkerson and Edmonds-Karp augmenting path algorithms.

START

 

NOT STARTED

40 minutes

1. Start

    

LESSON 19

MF3: Image Segmentation

Max-flow: Application to Image Segmentation problem.

START

 

NOT STARTED

30 minutes

1. Start

    

LESSON 20

MF4: Edmonds-Karp Algorithm

Max-flow: Edmonds-Karp augmenting path algorithm.

START

 

NOT STARTED

40 minutes

1. Start

    

LESSON 21

MF5: Max-Flow Generalization

Max-flow: Generalization allowing demand constraints.

START

 

NOT STARTED

30 minutes

1. Start

    

LESSON 22

LP1: Linear Programming

Linear Programming: Basics, Standard Form, and Simplex Algorithm Overview

START

 

NOT STARTED

1 hour

1. Start

    

LESSON 23

LP2: Geometry

Geometry of Linear Programs: Feasible Region, Infeasible LP's, and Unbounded LP's.

START

 

NOT STARTED

30 minutes

1. Start

    

LESSON 24

LP3: Duality

Dual of a Linear Program; Converting an LP problem to its Dual; Weak and Strong Duality.

START

 

NOT STARTED

30 minutes

1. Start

    

LESSON 25

LP4: Max-SAT Approximation

Maximum Satisfiability Problem; Approximate Solutions; Integer Programming; Calculus.

START

 

NOT STARTED

1 hour

1. Start

    

LESSON 26

NP1: Definitions

NP: Definition of a Search Problem and Computational Complexity Classes P and NP; Proving a Problem is in NP; Reductions; and the notion of NP-Completeness

START

 

NOT STARTED

1 hour

1. Start

    

LESSON 27

NP2: 3SAT

3-SAT Problem is NP-Complete

START

 

NOT STARTED

45 minutes

1. Start

    

LESSON 28

NP3: Graph Problems

NP-Completeness of Graph Problems: Independent Sets, Clique, and Vertex Cover

START

 

NOT STARTED

45 minutes

1. Start

    

LESSON 29

NP4: Knapsack

Knapsack and Subset Sum Problems are NP-Complete

START

 

NOT STARTED

30 minutes

1. Start

    

LESSON 30

NP5: Halting Problem

Halting Problem is Undecidable

START

 

NOT STARTED

30 minutes