You must be logged in to take this course → LOGIN | REGISTER NOW

The algorithm is the set of rules that are followed by calculations and processes by computers. Learning how to design and analyze algorithms will put you in an advantage for your professional growth and development.

This **[course_title]** will introduce you the teaching techniques focusing on the design and analysis of efficient algorithm with emphasis on the methods of application. You will be provided with information on dynamic programming, complexity, etc. here.

**Assessment**

This course does not involve any written exams. Students need to answer 5 assignment questions to complete the course, the answers will be in the form of written work in pdf or word. Students can write the answers in their own time. Each answer needs to be 200 words (1 Page). Once the answers are submitted, the tutor will check and assess the work.

**Certification**

Edukite courses are free to study. To successfully complete a course you must submit all the assignment of the course as part of the assessment. Upon successful completion of a course, you can choose to make your achievement formal by obtaining your Certificate at a cost of £49.

Having an Official Edukite Certification is a great way to celebrate and share your success. You can:

- Add the certificate to your CV or resume and brighten up your career
- Show it to prove your success

Course Credit: MIT

### Course Curriculum

TWO MOTIVATING APPLICATIONS | |||

Application: Internet Routing | 00:11:00 | ||

Application: Sequence Alignment | 00:09:00 | ||

INTRODUCTION TO GREEDY ALGORITHMS | |||

Introduction to Greedy Algorithms | 00:13:00 | ||

Application: Optimal Caching | 00:11:00 | ||

A SCHEDULING APPLICATION | |||

Problem Definition | 00:06:00 | ||

A Greedy Algorithm | 00:13:00 | ||

Correctness Proof – Part I | 00:07:00 | ||

Correctness Proof – Part II | 00:05:00 | ||

Handling Ties [Advanced – Optional] | 00:07:00 | ||

PRIM'S MINIMUM SPANNING TREE ALGORITHM | |||

MST Problem Definition | 00:11:00 | ||

Prim’s MST Algorithm | 00:07:00 | ||

Correctness Proof | 00:16:00 | ||

Correctness Proof II | 00:08:00 | ||

Proof of Cut Property [Advanced – Optional] | 00:12:00 | ||

Fast Implementation I | 00:15:00 | ||

Fast Implementation II | 00:10:00 | ||

KRUSKAL'S MINIMUM SPANNING TREE ALGORITHM | |||

Kruskal’s MST Algorithm | 00:08:00 | ||

Correctness of Kruskal’s Algorithm | 00:10:00 | ||

Implementing Kruskal’s Algorithm via Union-Find | 00:10:00 | ||

Implementing Kruskal’s Algorithm via Union-Find II | 00:14:00 | ||

MSTs: State-of-the-Art and Open Questions [Advanced – Optional] | 00:09:00 | ||

CLUSTERING | |||

Application to Clustering | 00:11:00 | ||

Correctness of Clustering Algorithm | 00:10:00 | ||

ADVANCED UNION-FIND | |||

Lazy Unions [Advanced – Optional] | 00:10:00 | ||

Union-by-Rank [Advanced – Optional] | 00:12:00 | ||

Analysis of Union-by-Rank [Advanced – Optional] | 00:15:00 | ||

Path Compression [Advanced – Optional] | 00:15:00 | ||

Path Compression: The Hopcroft-Ullman Analysis I [Advanced – Optional] | 00:10:00 | ||

Path Compression: The Hopcroft-Ullman Analysis II [Advanced – Optional] | 00:12:00 | ||

The Ackermann Function [Advanced – Optional] | 00:16:00 | ||

Path Compression: Tarjan’s Analysis I [Advanced – Optional] | 00:14:00 | ||

Path Compression: Tarjan’s Analysis II [Advanced – Optional] | 00:14:00 | ||

HUFFMAN CODES | |||

Introduction and Motivation | 00:09:00 | ||

Problem Definition | 00:10:00 | ||

A Greedy Algorithm | 00:17:00 | ||

A More Complex Example | 00:04:00 | ||

Correctness Proof I | 00:10:00 | ||

Correctness Proof II | 00:13:00 | ||

INTRODUCTION TO DYNAMIC PROGRAMMING | |||

Introduction: Weighted Independent Sets in Path Graphs | 00:08:00 | ||

WIS in Path Graphs: A Linear-Time Algorithm | 00:10:00 | ||

WIS in Path Graphs: A Reconstruction Algorithm | 00:07:00 | ||

Principles of Dynamic Programming | 00:08:00 | ||

THE KNAPSACK PROBLEM | |||

The Knapsack Problem | 00:10:00 | ||

A Dynamic Programming Algorithm | 00:10:00 | ||

Example [Review – Optional] | 00:13:00 | ||

SEQUENCE ALIGNMENT | |||

Optimal Substructure | 00:14:00 | ||

A Dynamic Programming Algorithm | 00:12:00 | ||

OPTIMAL BINARY SEARCH TREES | |||

Problem Definition | 00:13:00 | ||

Optimal Substructure | 00:10:00 | ||

Proof of Optimal Substructure | 00:07:00 | ||

A Dynamic Programming Algorithm | 00:10:00 | ||

A Dynamic Programming Algorithm II | 00:10:00 | ||

THE BELLMAN-FORD ALGORITHM | |||

Single-Source Shortest Paths, Revisited | 00:11:00 | ||

Optimal Substructure | 00:11:00 | ||

The Basic Algorithm I | 00:09:00 | ||

The Basic Algorithm II | 00:11:00 | ||

Detecting Negative Cycles | 00:09:00 | ||

A Space Optimization | 00:13:00 | ||

Internet Routing I [Optional] | 00:12:00 | ||

Internet Routing II | 00:07:00 | ||

ALL-PAIRS SHORTEST PATHS | |||

Problem Definition | 00:07:00 | ||

Optimal Substructure | 00:12:00 | ||

The Floyd-Warshall Algorithm | 00:14:00 | ||

A Reweighting Technique | 00:14:00 | ||

Johnson’s Algorithm | 00:11:00 | ||

Johnson’s Algorithm II | 00:12:00 | ||

NP-COMPLETE PROBLEMS | |||

Polynomial-Time Solvable Problems | 00:15:00 | ||

Reductions and Completeness | 00:14:00 | ||

Definition and Interpretation of NP-Completeness I | 00:11:00 | ||

Definition and Interpretation of NP-Completeness II | 00:08:00 | ||

The P vs. NP Question | 00:09:00 | ||

Algorithmic Approaches to NP-Complete Problems | 00:13:00 | ||

FASTER EXACT ALGORITHMS FOR NP-COMPLETE PROBLEMS | |||

The Vertex Cover Problem | 00:09:00 | ||

Smarter Search for Vertex I | 00:10:00 | ||

Smarter Search for Vertex Cover II | 00:08:00 | ||

The Traveling Salesman Problem | 00:15:00 | ||

A Dynamic Programming Algorithm for TSP | 00:12:00 | ||

APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS | |||

A Greedy Knapsack Heuristic | 00:14:00 | ||

Analysis of a Greedy Knapsack Heuristic I | 00:07:00 | ||

Analysis of a Greedy Knapsack Heuristic II | 00:10:00 | ||

A Dynamic Programming Heuristic for Knapsack | 00:12:00 | ||

Knapsack via Dynamic Programming, Revisited | 00:11:00 | ||

Analysis of Dynamic Programming Heuristic | 00:15:00 | ||

LOCAL SEARCH ALGORITHMS | |||

The Maximum Cut Problem I | 00:09:00 | ||

The Maximum Cut Problem II | 00:09:00 | ||

Principles of Local Search I | 00:09:00 | ||

Principles of Local Search II | 00:11:00 | ||

The 2-SAT Problem | 00:15:00 | ||

Random Walks on a Line | 00:16:00 | ||

Analysis of Papadimitriou’s Algorithm | 00:15:00 | ||

THE WIDER WORLD OF ALGORITHMS | |||

Stable Matching [Optional] | 00:15:00 | ||

Matchings, Flows, and Braess’s Paradox [Optional] | 00:14:00 | ||

Linear Programming and Beyond [Optional] | 00:12:00 | ||

Epilogue | 00:01:00 | ||

Assessment | |||

Submit Your Assignment | 00:00:00 | ||

Certification | 00:00:00 |

### Course Reviews

No Reviews found for this course.

**5 STUDENTS ENROLLED**