0

(

ratings

)

1

students

Created by:

Profile Photo

Last updated:

September 25, 2023

Duration:

Unlimited Duration

FREE

This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration

Description

ECS 122A: Algorithm Design and Analysis (Fall 2010, UC Davis). Taught by Professor Dan Gusfield,

this course introduces fundamental techniques and viewpoints for the design and the analysis of efficient computer algorithms, and studies important specific algorithms. The course relies heavily on mathematics and mathematical thinking in two ways: first as a way of proving properties about particular algorithms such as termination, and correctness; and second, as a way of establishing bounds on the worst case (or average case) use of some resource, usually time, by a specific algorithm. The course covers some randomized algorithms as well as deterministic algorithms.

Course Curriculum

  • Lecture 01 – Introduction to the Course and Algorithm Complexity Unlimited
  • Lecture 02 – Big-Oh, Omega and Theta Notation Unlimited
  • Lecture 03 – Time Analysis of Mergesort Unlimited
  • Lecture 04 – A More Complex Recurrence Relation and Counting Inversions Unlimited
  • Lecture 05 – Counting Inversions; Fast Integer Multiplication Unlimited
  • Lecture 06 – Fast Integer Multiplication, Randomized Selection and Median Finding Unlimited
  • Lecture 07 – More on Randomized Selection and Median Finding Unlimited
  • Lecture 08 – Expected Number of Comparisons in Randomized Select Unlimited
  • Lecture 09 – Greedy Algorithms: Picking Largest Set of Non-Overlapping Intervals Unlimited
  • Lecture 9A – Greedy Algorithms: The Classroom Scheduling Problem Unlimited
  • Lecture 10 – Dijkstra’s Shortest Path Algorithm Unlimited
  • Lecture 11 – Start of Minimum Spanning Tree Problem Unlimited
  • Lecture 12 – Correctness of Kruskal’s Algorithm Unlimited
  • Lecture 13 – Recursive Programming and Memoization Unlimited
  • Lecture 14 – Intro to Dynamic Programming, Weighted Interval Problems Unlimited
  • Lecture 14 – Intro to Dynamic Programming, Weighted Interval Problems Unlimited
  • Lecture 15 – Intro to the RNA Folding Problem and Recurrences Unlimited
  • Lecture 16 – Dynamic Programming for RNA Folding Unlimited
  • Lecture 17 – Dynamic Programming for Shortest Path Problem Unlimited
  • Lecture 18 – Floyd-Warshall Algorithm for All-pairs Shortest Path Unlimited
  • Lecture 19 – The Unique-Decipherability Problem Unlimited
  • Lecture 20 – Unique-Decipherability – Graph Algorithm and Proof of Correctness Unlimited
  • Lecture 21 – Linear-time Pattern Matching, Z-values and Z-algorithm Unlimited
  • Lecture 22 – Finish of Linear-time Pattern Matching Unlimited
  • Lecture 23 – Introduction to Approximation Algorithms Unlimited
  • Lecture 24 – Introduction to P and NP Unlimited
  • Lecture 25 – An Intuitive View of NP Unlimited
  • Lecture 26 – Formal Definition of P and NP Unlimited
  • Lecture 27 – Major Theorems of NP-completeness Unlimited
  • Lecture 28 – Coping with NP-completeness Unlimited

About the instructor

5 5

Instructor Rating

6

Reviews

4637

Courses

24151

Students

Profile Photo
OpenCoursa
We are an educational and skills marketplace to accommodate the needs of skills enhancement and free equal education across the globe to the millions. We are bringing courses and trainings every single day for our users. We welcome everyone woth all ages, all background to learn. There is so much available to learn and deliver to the people.