Summary
Keywords
Full Transcript
The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second). ------------ TIME STAMP ----------------------- PROGRAMMING CHALLENGES 0:00:00 Welcome 0:03:21 Solving the Sum of Two Digits Programming Challenge (screencast) 0:09:52 Solving the Maximum pairwise product Programming challenge Improving the naive solution, testing, debugging 0:23:30 Stress Test -Implementation 0:31:53 Strees Test -Find the Test and Debug 0:39:42 Strees Test -More Testing,Submit and Pass! ALGORITHMIC WARM-UP 0:48:28 Why Study Algorithms 0:55:51 Coming Up 0:58:51 Problem Overview 1:02:12 Naive Algorithm 1:07:48 Efficient Algorithm 1:11:45 Problem Overview and Naive Algorithm 1:15:48 Efficient Algorithm 1:21:38 Computing Runtimes 1:31:43 Asymptotic NOtation 1:38:37 Big-O Notation 1:45:36 Using Big-O 1:55:45 Course Overview GREEDY ALGORITHMS 2:05:51 Largest Number 2:08:34 Car Fueling 2:16:02 Car Fueling - Implementation and Analysis 2:25:17 Main Ingredients of Greedy Algorithms 2:27:57 Celebration Party Problem 2:34:55 Efficient Algorithms for Grouping Children 2:40:21 Analysis and Implementation of the Efficient Algorithm 2:45:46 Long HIke 2:52:24 Fractional Knapsack -Implementation, Analysis and Optimization 2:59:08 Review of Greedy Algorithm DIVIDE-AND-CONQUER 3:01:55 Intro 3:05:19 Linear Search 3:12:39 Binary Search 3:19:49 Binary Search Runtime 3:28:09 Problem Overview and Naive Solution 3:34:31 Naive Divide and Conquer Algorithm 3:41:40 Faster Divide and Conquer Algorithm 3:48:21 What is the master Theorem 3:53:17 Proof of the Master Theorem 4:03:02 Problem Overview 4:05:47 Selection Sort 4:13:56 Merge Sort 4:24:49 Lower Bound for Comparison Based Sorting 4:36:59 Non-Comparison Based Sorting Algorithms 4:44:42 Overview 4:46:52 Algorithm 4:55:59 Random Pivot 5:09:03 Running Time Analysis (optional) 5:24:36 Equal Elements 5:31:07 Final Remarks DYNAMIC PROGRAMMING 1 5:39:20 Change Problem 5:49:32 The Alignment Game 5:58:12 Computing Edit Distance 6:04:49 Reconstructing an Optimal Alignment DYNAMIC PROGRAMMING 2 6:09:44 Problem Overview 6:15:37 Knapsack with Repetitions 6:25:56 Knapsack without Repetitions 6:44:45 Final Remarks 6:52:25 Problem Overview 6:59:27 Subproblems 7:06:24 Algorithm 7:18:27 Reconstructing a Solution ⭐ Important Notes ⭐ ⌨️ This course is created in collaboration with University of California #algorithms #datastructures #tools
Continue this lesson in the app
Install CourseHive on Android or iOS to keep learning while you move.
