You must be logged in to take this course → LOGIN | REGISTER NOW
What are the limits of computation? Are there problems that cannot be solved by computer? Which problems can solve quickly and efficiently and which problems cannot be solved quickly? The [course_title] course answers all these questions and shows you power and limitations of algorithms.
You will learn the nuts and bolts of algorithms that help you to create tools that make the computer smarter, faster and safer.
Upon completion, you will gain a solid understanding of the tools and techniques for dealing with the real-world problems.
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 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: Georgia Institute of Technology and Georgia Tech Online Master of Science in Computer Science
Course Curriculum
| Languages & Countability | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Algorithms L12 | 00:01:00 | ||
| Functions – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Rules of the Game – Georgia Tech – Computability, Complexity, Theory: Computability | 00:03:00 | ||
| Operations on Languages | 00:04:00 | ||
| Countability – Georgia Tech – Computability, Complexity, Theory: Computability | 00:03:00 | ||
| Countability 2 – Georgia Tech – Computability, Complexity, Theory: Computability | 00:04:00 | ||
| Languages Are Uncountable – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Consequences – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Conclusion – Georgia Tech – Computability, Complexity, Theory: Computability (1) | 00:01:00 | ||
| Turing Machines | |||
| Motivation – Georgia Tech – Computability, Complexity, Theory: Computability | 00:01:00 | ||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Computability – L2 | 00:04:00 | ||
| Notation – Georgia Tech – Computability, Complexity, Theory: Computability | 00:03:00 | ||
| Testing Oddness | 00:02:00 | ||
| Configuration Sequences – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| The Value of Practice – Georgia Tech – Computability, Complexity, Theory: Computability | 00:01:00 | ||
| Equality Testing – Georgia Tech – Computability, Complexity, Theory: Computability | 00:04:00 | ||
| Language Deciders – Georgia Tech – Computability, Complexity, Theory: Computability | 00:01:00 | ||
| Turing Machines Conclusion – Georgia Tech – Computability, Complexity, Theory: Computability – L2 | 00:01:00 | ||
| Church-Turing Thesis | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Computability L3 | 00:02:00 | ||
| Simulating Machines – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Multitape Turing Machines – Georgia Tech – Computability, Complexity, Theory: Computability | 00:01:00 | ||
| Duplicate the Input – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Multitape SingleTape Equivalence – Georgia Tech – Computability, Complexity, Theory: Computability | 00:03:00 | ||
| RAM Model – Georgia Tech – Computability, Complexity, Theory: Computability | 00:04:00 | ||
| Equivalence of RAM and Turing Machines – GT – Computability, Complexity, Theory: Computability | 00:03:00 | ||
| Conclusion – L3 | 00:01:00 | ||
| Universality | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Computability L-4 | 00:01:00 | ||
| Encoding a Turing Machine – Georgia Tech – Computability, Complexity, Theory: Computability | 00:04:00 | ||
| Building a Universal Turing Machine | 00:02:00 | ||
| Abstraction – Georgia Tech – Computability, Complexity, Theory: Computability | 00:01:00 | ||
| Language Recognizers | 00:03:00 | ||
| Recognizability and Decidability – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Alternating Machines – Georgia Tech – Computability, Complexity, Theory: Computability | 00:01:00 | ||
| Dovetailing – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Universality Conclusion – Georgia Tech – Computability, Complexity, Theory: Computability – L4 | 00:01:00 | ||
| Undecidability | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Computability L5 | 00:01:00 | ||
| Diagonalization – Georgia Tech – Computability, Complexity, Theory: Computability | 00:04:00 | ||
| An Undecidable Language – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Mapping Reductions – Georgia Tech – Computability, Complexity, Theory: Computability | 00:01:00 | ||
| Some Trivial Reductions – Georgia Tech – Computability, Complexity, Theory: Computability | 00:01:00 | ||
| Reductions and (Un)decidability – Georgia Tech – Computability, Complexity, Theory: Computability | 00:03:00 | ||
| A Simple Reduction – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| The Halting Problem – Georgia Tech – Computability, Complexity, Theory: Computability | 00:03:00 | ||
| Filtering – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Rice’s Theorem – Georgia Tech – Computability, Complexity, Theory: Computability L5 | 00:04:00 | ||
| Conclusion – Georgia Tech – Computability, Complexity, Theory: Computability – L5 | 00:01:00 | ||
| P and NP | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Complexity – L6 | 00:01:00 | ||
| Friends or Enemies – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:01:00 | ||
| P and NP – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Delicacy of Tractability – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:03:00 | ||
| Running Time Analysis – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Asymptotic Analysis – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| The Class P – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Problems and Encodings – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Nondeterministic TMs – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:03:00 | ||
| Composite Numbers – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:03:00 | ||
| The Class NP – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:01:00 | ||
| NP Equals Verifiability Intuition – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:01:00 | ||
| P and NP Conclusion – Georgia Tech – Computability, Complexity, Theory: Complexity – L6 | 00:01:00 | ||
| NP - Completeness | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Complexity – L7 | 00:01:00 | ||
| The Hardest Problems in NP – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:03:00 | ||
| Polynomial Reductions Part 2 – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:01:00 | ||
| Independent Set – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Vertex Cover – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Vertex Cover = Ind Set – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| NP Completeness – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| CNF Satisfiability – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Cook Levin – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| The Variables – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Configuration Clauses – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Transition Clauses Cont – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:01:00 | ||
| Transition Clauses Cont – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:01:00 | ||
| Cook Levin Summary – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:04:00 | ||
| Conclusion – Georgia Tech – Computability, Complexity, Theory: Complexity – L7 | 00:02:00 | ||
| NPC Problems | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Complexity L8 | 00:01:00 | ||
| Basic Problems – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:01:00 | ||
| Strategy and Warm up – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Transforming One Clause – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:04:00 | ||
| CNF SAT – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| 3CNF INDSET – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:01:00 | ||
| Proof that 3CNF INDSET – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Subset Sum – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| 3 CNF Subset Sum – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:03:00 | ||
| Proof that 3CNF SUBSET SUM – GT – Computability, Complexity, Theory: Complexity | 00:01:00 | ||
| NPC Conclusion – Georgia Tech – Computability, Complexity, Theory: Complexity | 00:02:00 | ||
| Dynamic Programming | |||
| Intro to Algorithms – Georgia Tech – Computability, Complexity, Theory: Algorithms 14 | 00:02:00 | ||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Algorithms – L9 | 00:01:00 | ||
| Lesson Plan – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Optimal Similar Substructure – GT- Computability, Complexity, Theory: Algorithms | 00:04:00 | ||
| Prefix Substructure – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Sequence Alignment Algorithm – GT – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Sequence Alignment Summary – GT – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Chain Matrix Multiplication – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Subchain Substructure – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| CMM Algorithm – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| CMM Summary – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| All Pairs Shortest Path – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Shortest Path Substructure – GT – Computability, Complexity, Theory: Algorithms | 00:04:00 | ||
| The Floyd-Warshall Algorithm – GT – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| All Pairs Summary – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Transitive Closure – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Dynamic Programming Conclusion – GT – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| FFT | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Algorithms L10 | 00:01:00 | ||
| Prerequisites – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Convolution – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Representations of Polynomials – GT – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Multiplying Polynomials – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Multiplying Polynomials Continued – GT – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Divide and Conquer Inspiration – GT – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Roots of Unity – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:05:00 | ||
| FFT Example – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| FFT Algorithm – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Butterfly Network – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Recap of Progress – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Vandermonde at Roots of Unity – GT – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Inverse FFT – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| FTT Conclusion – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Maximum Flow | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Algorithms L11 | 00:02:00 | ||
| Lesson Plan – Georgia Tech – Computability, Complexity, Theory: Algorithms 00 | 00:01:00 | ||
| Flow Networks – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Tricks of the Trade – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Residual Networks – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Augmentations – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| The Ford-Fulkerson Algorithm – GT – Computability, Complexity, Theory: Algorithms | 00:04:00 | ||
| Flows and Cuts – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Flows and Cuts – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Cut Basics – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Cut Capacity – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Cut Capacity Continued – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| The Max-Flow Min-Cut Theorem -GT – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Better Augumentations – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Scaling Algorithm – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Analysis of Scaling – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:04:00 | ||
| The Edmonds-Karp Algorithm – GT – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Analysis of Edmonds-Karp – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:00:00 | ||
| Dinic’s Algorithm – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Analysis of Dinic’s Algorithm – GT – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Maximum Flow Conclusion – Georgia Tech – Computability, Complexity, Theory: Algorithms – L 11 | 00:01:00 | ||
| BP Matching | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Algorithms L12 | 00:01:00 | ||
| Bipartite Graphs – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Matching – Georgia Tech – Computability, Complexity, Theory: Algorithms L12 | 00:01:00 | ||
| Reduction to Max Flow – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Reduction Correctness – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Deeper Understanding – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Augmenting Paths – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:04:00 | ||
| Vertex Cover – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Max Matching Min Vertex Cover – GT – Computability, Complexity, Theory: Algorithms | 00:04:00 | ||
| The Frobenius-Hall Theorem – GT – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Toward a Better Algorithm – GT – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| The Hopcroft-Karp Algorithm – GT – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Shortest Augmenting Paths – GT – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Analysis of a Phase – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Number of Phases – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| BP Matching Conclusion – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Linear Programming | |||
| Introduction – Georgia Tech – Computability, Complexity, Theory: Algorithms L-13 | 00:01:00 | ||
| Preliminaries – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| HS Linear Programming – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:05:00 | ||
| To n Dimensions – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:02:00 | ||
| Favored Forms – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Basic Solutions and Feasibility – GT – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Fundamental Theorem of LP – GT – Computability, Complexity, Theory: Algorithms | 00:05:00 | ||
| Simplex Equations – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Simplex Summary – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:01:00 | ||
| Simplex Example – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:03:00 | ||
| Simplex Correctness – Georgia Tech – Computability, Complexity, Theory: Algorithms | 00:04:00 | ||
| Getting Started – Georgia Tech – Computability, Complexity, Theory: Algorithms L-13 | 00:01:00 | ||
| Conclusion L-13 | 00:02:00 | ||
| Duality | |||
| Intro to Algorithms – Georgia Tech – Computability, Complexity, Theory: Algorithms 14 | 00:02:00 | ||
| Dual Programs – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Duality Theorem – Georgia Tech – Computability, Complexity, Theory: Computability | 00:03:00 | ||
| Duality of Max Matching – Georgia Tech – Computability, Complexity, Theory: Computability | 00:03:00 | ||
| Duality of Max Flow – Georgia Tech – Computability, Complexity, Theory: Computability | 00:02:00 | ||
| Duality Conclusion – Georgia Tech – Computability, Complexity, Theory: Computability | 00:01:00 | ||
| Approximation Algorithms | |||
| Introduction – L 15 | 00:01:00 | ||
| An Approximation for Min Vertex Cover | 00:03:00 | ||
| Lower Bounding the Optimum | 00:01:00 | ||
| Optimization | 00:02:00 | ||
| Approximation Algorithms | 00:01:00 | ||
| An FPTAS for Subset Sum | 00:02:00 | ||
| Traveling Salesman Problem | 00:02:00 | ||
| Hardness of Approximation for TSP | 00:02:00 | ||
| Summary – L15 | 00:01:00 | ||
| Metric TSP | 00:02:00 | ||
| Correctness of Factor 2 TSP Approx | 00:02:00 | ||
| Conclusion – L15 | 00:01:00 | ||
| Randomized Algorithms | |||
| Introduction – L16 | 00:01:00 | ||
| Verifying Polynomial Identities | 00:02:00 | ||
| Discrete Probability Spaces | 00:03:00 | ||
| Repeated Trials | 00:04:00 | ||
| Independence and Conditional Probability | 00:02:00 | ||
| Monte Carlo and Las Vegas | 00:03:00 | ||
| Random Variables 123 | 00:01:00 | ||
| Expectation | 00:02:00 | ||
| Quicksort | 00:03:00 | ||
| Analysis of Quicksort | 00:04:00 | ||
| A Minimum Cut Algorithm | 00:02:00 | ||
| Analysis of Min Cut | 00:04:00 | ||
| Max 3 SAT | 00:02:00 | ||
| Approx Max 3 SAT | 00:04:00 | ||
| PCP Theorem | 00:04:00 | ||
| Conclusion – L16 | 00:01:00 | ||
| Assessment | |||
| Submit Your Assignment | 00:00:00 | ||
| Certification | 00:00:00 | ||
Course Reviews
No Reviews found for this course.
Related Courses
6 STUDENTS ENROLLED
