Introduction to Graduate Algorithms from Udacity

What's inside

Syllabus

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

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

Dynamic programming: Knapsack, and Chain Matrix Multiplication.

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

Modular Arithmetic: Fast Modular Exponentiation and Multiplicative Inverses.

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

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

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

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

Refresher Lecture about Solving Recurrences.

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

FFT and polynomial multiplication algorithms, and inverse FFT.

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

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

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

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

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

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

Max-flow: Application to Image Segmentation problem.

Max-flow: Edmonds-Karp augmenting path algorithm.

Max-flow: Generalization allowing demand constraints.

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

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

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

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

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

3-SAT Problem is NP-Complete

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

Knapsack and Subset Sum Problems are NP-Complete

Halting Problem is Undecidable

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Develops advanced algorithmic techniques for solving hard computational problems, which is highly relevant in academia and industry

Taught by Eric Vigoda and Arpan Chakraborty, who are recognized for their work in algorithms and computational complexity

Covers a wide range of topics, including dynamic programming, graph algorithms, number theory, and linear programming

Designed to build a strong foundation for students interested in pursuing graduate studies in algorithms or computer science

Provides interactive materials and exercises to enhance understanding

Assumes a basic understanding of algorithms and data structures

Career center

Learners who complete Introduction to Graduate Algorithms will develop knowledge and skills that may be useful to these careers:

Algorithm Engineer

An Algorithm Engineer develops and analyzes algorithms to solve complex computational problems. This course would be highly useful for this role, as it covers advanced techniques for designing algorithms and applying them to hard computational problems. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all essential skills for an Algorithm Engineer.

See salaries and explore the career path for Algorithm Engineer

Machine Learning Engineer

A Machine Learning Engineer develops and deploys machine learning models. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Machine Learning Engineer. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for machine learning.

See salaries and explore the career path for Machine Learning Engineer

Operations Research Analyst

An Operations Research Analyst uses mathematical and analytical techniques to improve the efficiency of organizations. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for an Operations Research Analyst. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for operations research.

See salaries and explore the career path for Operations Research Analyst

Software Engineer

A Software Engineer designs, develops, and maintains software systems. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Software Engineer. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for software development.

See salaries and explore the career path for Software Engineer

Database Administrator

A Database Administrator designs, builds, and maintains databases. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Database Administrator. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for database administration.

See salaries and explore the career path for Database Administrator

Information Security Analyst

An Information Security Analyst protects an organization's computer systems and networks from cyberattacks. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for an Information Security Analyst. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for information security.

See salaries and explore the career path for Information Security Analyst

Data Scientist

A Data Scientist uses data to solve business problems. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Data Scientist. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for data analysis.

See salaries and explore the career path for Data Scientist

Software Architect

A Software Architect designs and develops the overall architecture of a software system. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Software Architect. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for software architecture.

See salaries and explore the career path for Software Architect

Cryptographer

A Cryptographer develops and analyzes cryptographic algorithms to protect information. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Cryptographer. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for cryptography.

See salaries and explore the career path for Cryptographer

Quantitative Analyst

A Quantitative Analyst uses mathematical and statistical models to analyze financial data. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Quantitative Analyst. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for financial analysis.

See salaries and explore the career path for Quantitative Analyst

Computer Scientist

A Computer Scientist researches and develops new computing technologies. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Computer Scientist. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for computer science research.

See salaries and explore the career path for Computer Scientist

Network Engineer

A Network Engineer designs, builds, and maintains computer networks. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Network Engineer. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for network engineering.

See salaries and explore the career path for Network Engineer

Systems Analyst

A Systems Analyst analyzes and designs business systems. This course would be moderately useful for this role, as it covers techniques for designing and analyzing algorithms, which are essential skills for a Systems Analyst. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which are all useful for systems analysis.

See salaries and explore the career path for Systems Analyst

Product Manager

A Product Manager manages the development and launch of new products. This course may be useful for this role, as it covers techniques for designing and analyzing algorithms, which can be useful for product development. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which can all be useful for product management.

See salaries and explore the career path for Product Manager

Business Analyst

A Business Analyst analyzes and solves business problems. This course may be useful for this role, as it covers techniques for designing and analyzing algorithms, which can be useful for solving business problems. The course also provides a strong foundation in dynamic programming, divide-and-conquer algorithms, and graph algorithms, which can all be useful for business analysis.

See salaries and explore the career path for Business Analyst