- Видео 18
- Просмотров 112 282
Algorithms by Sharma Thankachan
Добавлен 3 сен 2020
Lecture on the "Design and Analysis of Algorithms".
2.11 - Integer Sorting Algorithms | Counting Sort and Radix Sort
Counting sort and radix sort are specialized algorithms for sorting integers. Given n integers within the range [0, k-1], counting sort takes O(n+k) time, which is optimal if k = O(n). Radix sort takes O(n + n* (log k)/(log n)) time, which is optimal if k = O(n^c) for any constant c.
Просмотров: 925
Видео
2.8 - Probability Basics | Randomized Algorithms | Hiring Problem | Coupons Collector
Просмотров 1,8 тыс.3 года назад
A quick review of the following topics: random experiment, sample space, event, probability, random variable, indicator random variable, expectation of a random variable, linearity of expectation, Bernoulli trial, Markov's inequality, randomized algorithms (Monte Carlo vs Las Vegas) and probability puzzles (the hiring problem and coupons collector problem).
2.10 - Quick Select | Randomized Algorithms
Просмотров 2,1 тыс.4 года назад
A simple Randomized (Las Vegas) algorithm for expected linear time selection.
2.9 - Quick Sort | Randomized Algorithms (Monte Carlo vs Las Vegas)
Просмотров 2,7 тыс.4 года назад
A simple Randomized (Las Vegas) algorithm for sorting in expected O(n log n) time. This can be converted to a Monte Carlo algorithm with O(n log n) worst case time.
2.7 - Finding the MIN/MAX slope (of lines connecting points in 2D) and its Counting Version
Просмотров 1,4 тыс.4 года назад
Given a set of n points in 2D, we need to compute: (i) the pair of points such that the slope of the line segment connecting them is the MAXIMUM, (ii) the pair of points such that the slope of the line segment connecting them is the MINIMUM, and (iii) count the number of pairs such that the slope of the line segment connecting them is within a given range. All three problems can be solved in O(...
2.6 - Counting Inversions in an Array in O(n log n) time via Divide and Conquer
Просмотров 13 тыс.4 года назад
Given an array A[1,n] of numbers, we need to count the number of inversions. As inversion is a pair of positions (i, j), such that i is smaller than j, but i-th element is larger than j-th element (i.e, the elements are out of order with respect to sorted order). This can be solved in O(n log n) time via a Divide and Conquer algorithm.
2.5 - Closest Pair of Points using Divide and Conquer algorithm in O(n log n) time.
Просмотров 46 тыс.4 года назад
Given a set of n points in 2 dimension, find the pair of points, such that the euclidean distance between them is the minimum. The trivial algorithm takes O(n^2) time, however, we can solve this in O(n log n) time using Divide and Conquer strategy.
2.4 - Integer Multiplication (Karatsuba's Algo) & Matrix Multiplication (Strassen's Algo)
Просмотров 1,6 тыс.4 года назад
Two fundamental algorithms are discussed in this lecture: (i) Karatsuba's algorithm for fast multiplication of two n-digit numbers in time n^{log 3} = O(n^{1.59}), improving the trivial O(n^2) algorithm, and (ii) Strassen's algorithm for fast multiplication of two nXn matrices in time n^{log 7} = O(n^{2.81}), improving the trivial O(n^3) algorithm. Both algorithms are based on the divide and co...
2.3 - Binary search (in 1D and 2D arrays - upper and lower bounds) and Bitonic search
Просмотров 1,6 тыс.4 года назад
Searching in a sorted sequence can be done in O(log n) time via Binary search. A modified binary search can be used to do sorting in a Bitonic sequence (i.e., numbers are first increasing, then decreasing). Finally, given a 2D array of "n" columns and "n" rows, where elements are sorted both column wise and row wise, we can do searching in O(n) time. Additionally, we can prove that O(n) time is...
2.2 - Linear Time Selection (Median of Medians Algorithm)
Просмотров 24 тыс.4 года назад
The selection problem asks to report the kth smallest element in an unsorted array. It is easily solvable in O(n log n) time via sorting and the Median of Medians Algorithm solves this in O(n) time via a clever Divide and Conquer strategy.
2.1 - Lower Bound for (Comparison Based) Sorting
Просмотров 5 тыс.4 года назад
Using a decision tree view, we prove that any comparison-based sorting algorithm must perform Omega(n log n) comparisons, which is the minimum over the heights of all binary trees with n! leaves. Therefore, merge sort runs in optimal time.
2.0 - Sorting Algorithms (Selection, Insertion and Merge Sort) with Analysis
Просмотров 1,7 тыс.4 года назад
Three "COMPARISON BASED" sorting algorithms - Selection Sort, Insertion Sort (time complexity is quadratic), and the optimal O(n log n) time Merge sort, which uses the DIVIDE & CONQUER strategy.
1.5 - Growth of Functions and Asymptotic Notations
Просмотров 2,3 тыс.4 года назад
Big-O, Big-Omega, Small-o, Small-omega, and Theta.
1.4 - Warm-up problem (Maximize your the amount of your drink + Harmonic Series)
Просмотров 8414 года назад
Here is a simple game, where there are given "n" empty cups (with capacity "n" liters). The game is played between two players A and B. For round 1 to n-1, player A gets to 1 liter of drink and is allowed to distribute it across this "n" cups and then player B chooses one cup and empties it. At the last (i.e., nth) step, player B will not participate. Instead, player A will get to choose a cup ...
1.3 - Warm-up Problem (Separate HEAVY and LIGHT coins)
Просмотров 1,1 тыс.4 года назад
You are given "n" coins, where coins are of two types - HEAVY and LIGHT. All HEAVY coins are of the same weight, and all LIGHT coins are of the same weight, but heavy coins are heavier than the light coins. Your task is to separate these coins into two groups - i.e., a group of all LIGHT coins and a group of all HEAVY coins. All coins look the same and the only instrument you have is a traditio...
1.2 - Warm-up problem (Find the Max and the Second Max)
Просмотров 1,1 тыс.4 года назад
1.2 - Warm-up problem (Find the Max and the Second Max)
1.1 - Warm-up problem (Find the Min and the Max)
Просмотров 1,2 тыс.4 года назад
1.1 - Warm-up problem (Find the Min and the Max)
thanks bro
Can anyone explain why the x coordinate was not sorted ?
made it so clear
Absolutely goated explanation
Amazing Explaination Sir!!
Very helpful lectures...Pls continue with more videos!
Congratulations! on 1k Subs
Respect sir! When I looked at the slides I got really really confused. Saved by you!
Excellent video 😊
i cannot understand how you do n steps then say that it takes n^2, i cannot wrap my head around this please clarify. like at 11:22.
"n" step, and kth step takes roughly "k" time. So, total time for steps k = 1,2,3,..n is Big-O of (1+2+3+...+n), which is n(n+1)/2 [arithmetic progression], which can be written as O(n^2).
Thank you sir, finally understood it thanks to you.
why it is 7
its clear in the proof, there are 8 boxes, so if we fix one box for one point, they we have other 7 possible boxes for the other point
@@algorithmsbysharmathankach7521 it should be 4 rather than 7
For correctness of we are comparing points sorted by y axis, what if there are 7 points in the other quadrant more than d distance away and 1 point directly underneath which is super close we missed that point and in end gave inaccurate result
Suppose "p" is the current point and "q" is the other point (which is super close and underneath p) and (p,q) is the closest pair. You are right, this pair wont be captured while doing our procedure at "p", but it will be captured when we do our procedure at "q''.
@@algorithmsbysharmathankach7521 we take a look at next 7 points right and not the ones that are already scanned
@@algorithmsbysharmathankach7521 the points are sorted by y co ordinate and we check with next 7 points not previous ones
Very very well done video, thanks a lot for sharing.
good explanation
fantastic explanation
Amazing
Thanks you, best explanation of this I have seen so far
your explanation is one of the best I have seen thank you so much sir
this is great! thank you! why don't professors explain in a similar manner instead of showing 20 slides for 40 min...
I understand that each box can have at most one point but why do we even need to compare 7 since the distance on the left half or right half region is at most d. Why don't we just compare the points between the two regions?
Yes, we can fix a point (on a side) and just compare it with 4 (instead of 7) points on the other side. But these 4 points can be anyone's among the next 7 points (if we sort with respect to Y). So, we might still need to examine the next 7 points. The answer is yes, we can do a bit of optimization here, but the asymptotic time will be the same.
Hey Sir, your videos are nice. Why your videos not coming up?
this is the exact explanation i was looking for. Very well explained
Thank you, Amazing video !!
Very well explained !!
thank you so much this helped a lot!!!
Excellent Explanation!
Thank you beast
very informative
❤🔥
Well explained.. 👏
holy shit I was looking for an understanding of why its 7 points. you are the most clear an concise. thank you
thank you so much..
I appreciate this. You helped me from suffering of stress about not understanding that recurrence relation and the theorem and its proof🙏
Highly appreciate your explanation!!
Thanks for the videos Sharma! You are a great teacher. Any more videos coming up?
will do :)
After two years, this still helps thanks I see that you are joyful when teaching and I appreciate you doing this.
thank you so much!
love from Israeli programmers!
Great explanation
Can we choose 4 instead of 5?
It will be ugly -- like how we choose the median of 4 numbers? A definition like the mean of 2nd and 3nd number is problematic, since this is the comparison model (meaning u can compare elements, but you may not even get to know the "absolute" value of elements). So, one option is fix either of the 2nd or 3rd element (among 4) as the median. Then the recurrence will look like T(n) = T(n/4)+T(3n/4)+O(n), which is not O(n), but \Theta(n log n). So the answer is NO.
Thank you, this video helped me fully understand!!
great explanation :))
Dhanyawad guru ji
Great video and great explanation too!
Shouldn't the counter at 8 be 4?
I was counting in the other direction --- i.e.,for each number, how many are on its RIGHT side that are smaller.
@@algorithmsbysharmathankach7521 right, I get that. But if we are using the R side as a counter, shouldn't the count change to 4 instead of staying as 3 at digit 8?
@@carlavn2470 didn't get it, can you tell me where exactly (time in the video) is the mistake?
@@algorithmsbysharmathankach7521 at min 17:48
@@carlavn2470 yes, it is 4 (my bad) -- thankyou!
Much needed explanation! 👍
can you pl tell the exercise number in Computational geometry book ?
Thank you! wish i found this video before my algorithms exams...
THANK YOU this is so clear and thorough answered all my questions on this topic with bonus induction too