Transcripts
1. Introduction: Hello everyone. Welcome to this class on
most fundamental algorithms. This class will give you
hands-on lessons for implementing some of the most basic algorithms from scratch. If you are new to programming or an experienced programmer, this class will be helpful. This will give you an
opportunity to go back to the basics and revisit how the nuts and
bolts of some of the most fundamental
algorithms fit together. I teach using very simple
language, no jargon. First, the logic is
explained on paper, and then the program
is developed from scratch using the tool PyCharm. You'll need a computer
with internet connection. And to software's
Anaconda and PyCharm. Please take heel bone length for the installation process. You should be ready
to write and execute program within
PyCharm environment. Before starting this course. At the end, you will master these basic algorithms and new programmers will develop an appetite for
more programming. What follows after this
is for lessons on some of the most basic algorithms and tell implementation
from scratch. Listen to has some simple
manipulation as a warm-up. Lesson 3.4 are on binary
search and edit partitioning, very basic algorithms
as you know. Finally, on less than five, we have a class project on implementation of Quicksort
algorithm from scratch. That's all about it. Looking forward to
seeing you all there.
2. Array - a simple introduction: Hello everyone. In this lesson, we will learn about a
very basic data type that can store multiple
objects together. This is called an array. An array is a set of objects stored side-by-side
in computer memory. In our discussion, we will take integer numbers as objects. Let's take an example. Is an array containing
the numbers 289214 minus six in Python. And array is also
called the list. Elements are placed
side-by-side in memory. Position of each array
element is known as index. Index starts at zero. That means the index of
the first element is zero. Index of the second
element is one, index of the third element
is two, and so on. In this way, index of the last element is one less than the total
length of the array. So in the given array, there are five elements
and the indices are 01234. Let's see how we can
access each element of a given array and print
the numbers. In Python. Print function is
used for printing. Print function can
print the entire added together in one
call to this function. That means the print function knows the internal
structure of the array. To access each
element of the array, we need to traverse the
array using a for loop. This for-loop prints each
element of the array. The next for loop goes
through each index of the array and prints the
value at that index. This for loop goes
through each index and the corresponding
values simultaneously and prints both of them. I suggest you to find out more
about these two functions, range and enumerate, as they are very handy
in writing a loop. Next, we'll implement
an algorithm to calculate the running sum
of an array of integers. So what is running sum? Sum for element of
an array is the sum of all elements from zero to Pi. So after summing, we get the upper valley as the running sum of
the original array. Running sum for the first
element is the element itself. Running sum for
the second element is the sum of first
two elements. Running sum for the
third element is the sum of three
elements and so on. We like the steps
in simple language and try to visualize how the algorithm
executes step-by-step. Let's try to visualize
this algorithm. Start with a pointer p at
the second element of a. So we have a pointer p. Let's make it point to the
second element which is a. So here p is a pointer, that means it holds the value of the index of the second
element, which is one. So currently P is equal to one. Now, we need to
replace the value at p by the sum of its value
and the previous value. That means we replace eight by eight plus
two, which is ten. Then we move one step forward
and do the same thing. That means replace 91 by 91 plus ten, which is 101. Now, we move one step forward. It plays the value for by the
sum of 4.101, which is 105. And we continue the same way. So move B by one step forward and replace the
current value which is minus six by minus six plus
105, which is 99. And we have reached
the end of the array. So the algorithm stops here. This way, we can find the running sum of a
given array of numbers. Note that we have not created any new LEA to
find this running sum, we have replaced
each array element by their corresponding
running some. Next, we'll try to
reverse that given any, that means given an array, say 289214 minus six, we will reverse the order of
the elements in that array. So after reversing, the array
will become minus 6492182. Let's select algorithm
in plain language. So we first set two pointers at the first and last elements
of the array, CPS and PE. So we have PAs and PE. Then we need to swap
values of P, S&P, and then move forward by one step and PE
backward by one step. That means we move P, S&P towards each other
by one step each. And we need to do this
one step movement of each and swapping the corresponding values
till they cross each other. Let's do this step-by-step and try to see what is
happening actually. So we have P, S&P at the two extreme ends. We need to swap their values. That means we need to swap the positions of
two and minus six. So we bring to here, bring minus six here to here. Then we move VS by one step forward and PE by
one step backward. And again swap their values. We move beers and b0. Now they are pointing
to the same location. So sobbing has no effect. Basically. We we can stop here or if we want
to go on step four, once the father I can do this this and since now they have
crossed each other. We stop. This way. We can reverse the elements of the array using two pointers. I hope you'll get the idea
behind these algorithms. In this lesson, we
tried to visualize the states of some of the
very basic algorithms. We haven't written
any Python code yet. In the next lesson,
we will write and execute some real code
in Python environment. So that's all for this lesson.
3. Array Partition Algorithm: Hello everyone. In this lesson, we'll learn about partitioning. So what is Ellie partitioning? Let's explain with an example. Let's take an LEA with
the following numbers. That is 387-272-1402
partition this array, we need to first choose a
special number called pivot, which is one of the numbers
present in the array. Say, we choose four
as the pivot number. We need to rearrange the
numbers in the array. So that after rearranging all the numbers to
the left of pivot, or less than or equal
to the pivot value. And all the numbers
to the right of the pivot are greater than
or equal to the pivot value. If we take for SDP vert, then a possible solution could
be as shown on the screen. The solution is 032-14-7078. Note that numbers to the left of the pivot for less
than equal to four. Numbers to the right of
four, equal to four. The left subarray and the legs are not necessarily
sorted by themselves. Also note that if we had
sorted the entire array, then after partitioning,
the position, the pivot gets same as the position that it would get after sorting
the entire array. Extract to develop an algorithm to partition this given LA. Let's go through the
algorithm step-by-step. First, we need to place the pivot in the first
location of this array. Then we need to
take two pointers, P1 and P2, and make them point to the first
two elements respectively. So p1 points to the first element and v2
points to the second element. Then we need to move P2 one step at a time
till the end of this LA. And while moving this, at each step, we need to do something
called checked and swap. So what do we need
to do as follows? At each position of P2, we need to check if the value at p2 is less than or
equal to the pivot. If no, then do nothing. But if yes, then we need to increment the
other pointer p1 by one step and then swap
the values of P1 and P2 will stop when P2 reaches
the end of the array. Let's carry out the steps. So currently P2 is at position two and
its value is eight. So P2 is not less
than b worked for. So both be due by one step. So 77 is again not less
than equal to four. So we move P2 by one step. Now, two is less
than the pivot for. So we need to do
this sub step here. So what do we need to do now
is to move p1 by one step forward and then swap the values of P1 and P2. Then again move P2 by one step. And again, we see
that the value at P2, which is on, is less
than or equal to four. So we need to again
do this swap step, which is first morph
P1 by one step. And then swap the
values of P1 and P2. Again move P2 by one step. And again, we observe
that the value at P2, which is three, is less
than or equal to four. So we again move p1 by one
step and then do the swap. More 321 step. And we see that zero is again
less than equal to four. So we move one by one step
and then do the swap. At this point, P2 is at
the end of this array. So the loop over P2 has ended. Now, as the last step, we need to swap the first
location of the array, which is pivot value with p1. This will put the pivot at
its correct sorted location. And now we see that all the numbers to the left of pivot or less than
equal to four. And all the numbers
to the right of pivot greater than equal
to the pivot value for. This is a valid
partition of the array. I hope this helped
to visualizing the internal steps when
learning the algorithm. Next, we'll go through
the Python code for this partition algorithm. Here's a Python function
called partition, which takes an input called a, which is Danny, and partitions it with
respect to a pivot. And this assumes that the pivot is located at the first
position of this array. Let's go through this
algorithm line by line. First to initialize
the two pointers, p1 and p2 to 0.1 respectively. Then we set the pivot by reading the first location of the
array that is a zero. Then, as we mentioned earlier, we like to look over P2. So P2 moves from its current location till
the end of the array. The end of the array is
denoted by length of array. Then the next if statement, we implement the logic
that we discussed earlier. That is, if a of p2 is
less than equal to pivot, then we move p1 and then swap
the values of P1 and P2. This line AFP one
comma f p2 is equal to a f B2 comma f of p1 is the Python expression
for swapping two values. Here the values are
a of P1 and P2. So this is a very
intuitive syntax. And then outset
this if statement, we keep moving P2, well, one step in each
iteration of this while loop. And when they come out of
the while loop, that is, that means when P2 reaches
the end of the array, we then again swap
is zero and a of P1. This is to bring the pivot
from its current location, which is the beginning
of the array, to its final location. And that's all for this lesson.
4. Array Partition Python Program: Hello everyone. In this lesson, we will run the Python program for
array partitioning. Here we have the partition function
that have seen already. Also there is a main function
which creates a list called my list and calls the partition function
with my list as input. Let's run the program
in debug mode. Let's put a breakpoint in the
main function and run it. So we are at the breakpoint. And let's first create
the list, my list. Please keep an eye on these
variables section and you can see the values of the variables. And then enter the
partition function. First initialize p1 and
p2, the two pointers. And then set the pivot, which we assume that the first element
of the input array. So here the pivot is four. Let's enter the loop over P2. So P2 moves from its current location to
the end of the array. First, if P2 is eight, which is not less than
equal to the period four. So we move past the if statement and go to the next
iteration of the loop. Now, if P2 is equal to 77, which is not less than
equal to the pivot. So we move to the
next iteration. Now, if P2 is two, which is less than equal
to the pivot four. So we go inside
the if statement, increment beyond by
u1 and do the swap. We go to the next iteration. Now AF P2 is on. So again enter the if
statement and do the swap. In the next iteration
of P2 is three, which is less than
equal to pivot four. So again, we enter the if
statement and do the swap. In the next iteration. If B2 is zero, which is less than
equal to p, What for? So we enter the if statement
and do the swap again. And now P2 has reached
the end of the array. So we come out of
the while loop. And then we do the final swap, the pivot value, which is at
the first location with b1. And that completes
the algorithm. Not at the variables section. You can see the current
state of the mind list. And it has been partitioned. So all the numbers to the left of four or less
than equal to four, and all the numbers to the right of four or greater
than equal to four. So if I have to explain the whole algorithm in
a very plain language, it would be like this. There are two
pointers, p1 and p2. What do they really do? B1 maintains a boundary
between the two partitions. The left partition, which is from the beginning
of the array till p1, is the set of numbers which are less than equal to
the pivot value. And the numbers to
the right of P1 are the numbers that are greater than equal
to the pivot value. So how does p1 and
p2 achieve this? B2 explodes each new
number of the array. And if that newly
explored number is less than equal
to the pivot value, then B1 extends
the left boundary and that new number is moved
into the left partition. By swapping. This way, the left partition always contains values less
than equal to the pivot. And the right partition contains values that are greater than equal
to the pivot value. Note that the right partition starts after T1 and
extends till P2. I suggest that you step through this program in your Python
programming environment. So that internal steps
become very clear to you. And that's all for this lesson.
5. Binary Search Algorithm: Hello everyone. In this lesson, we'll learn about binary search. So what is binary search? Here? We are given a sorted
array of integer numbers, and we're also given
another single integer x, we need to find the location
of x in this sorted array a. If x is not present in a, then we can return minus one. Let's take an example. We are given the sorted array a, which is, you can see that
sorted in increasing order. And we're also given
another number x. We need to find
the location of x. If x is present in a, otherwise we need to
return minus one. So here we can see that
seven is present in the LEA. And the location of
seven is index four. That means the fifth place. So we need to return four. In this case. If the value of x is, then we can see that nine is
not present in the given a. So the binary search
should return minus one. Let's try to visualize the
binary search algorithm. We're given the sorted array, which is sorted in
increasing order. And we need to search for
a given number X in a. Here, the value of x is seven, so we need to search for seven. In a first, note
that we can traverse the entire array one element
at a time and look for x. This will take n steps, where n is the total number
of elements in the array. If the array is too long, then the time required for searching in this manner
will also be very long. So this is not an efficient way. If the array were not sorted, then we will have
to do this way. But right now the
array is sorted. So we need to use that property to speed up our algorithm. Let's write the algorithm
in simple language. First, we need to set two points at the start
and end of the array. Let's say the LPS
and p. We said P is at the start
and p at the end. Next, we find the
midpoint of P S&P. That means we find P S plus p all divided by two
and rounded below. So this is called the midpoint. Note that this is
left biased made. That means safe P S is
two and p is three. Then mate is two plus 3/2. And this division is
an integer division. So the result is two. Middle point of 2.3 is two, middle points of 23.4 is three. Middle point of 234.5 is three. That's why it is called
left biased made. Let's calculate the
mid of current P S&P. P S is zero and P is
70 plus seven by two, which is 3.5. Rounded. Hello is three equals three. So mid is placed at index three. Now, we are looking for x. So we compare the
value at me with x. If x is equal to mate than you have found
the location of x, and we return the value of meat. If not, then x is either to the right of meat
or to the left of meat. If x is greater than meat, then x is to the right of meat. And in that case, we can skirt what
is to the left of meat so we can discard the entire subarray,
the liftoff meet. This way, we can reduce the
search space very quickly. So in each iteration, half the total array
can be discarded. And that makes this
binary search very fast. Now, x is greater than three. So we move PS. Meet plus one. That means the just to the
right of the previous made. Now we know whatever is left to the left of peers
can be discarded. We have reduced our
search space by half. Now. Again, calculate me. So currently PACs four and p is seven. So the meat of 4.7 is 5.5. Rounded below is five. So let's meet at five. Now the value of value at
meat is 88 is not equal to x. And we see that now
x is less than mate. So we move B to make minus one. Now, in the next iteration, again, we calculate mid. So you will see since PAs
and PE have the same value, the value of meat will
also be the same. So again, we'll point
to the same location. Now. X is equal to meet found x. And we returned, made. This way. We can find the location
of x in the sorted data. Now let's take another example where x is not
present in the LA, say x equal to nine. Again, we start with
PAS at the start. And at the end. The mid points to the midpoint. We compare the value at, which is three
with x, x is nine. So x must be to
the right of meat. So we move VS to meet plus one. And again, we calculate,
which is here. We compare value x with x. The value of x is nine, so nine is greater than eight. So x must be the light of meat. So we move PAs to mid plus one. Now we calculate meet again, which is, which
will be same as bs. We compare x with Nate and we find that x is less
than meat now. So we move B to mid minus one. And at this stage, notice that P S&P
cross each other. So we stop and return minus one. That means X in this case is not present in
this sorted array. Let's look at the Python code for the binary search function. The function takes
two arguments. The first one is the array, is an array of integers
sorted in increasing order. And x is another integer. We need to find the
location of x within a. And if x is not present, then we return minus one. Let's go through the
function line by line. First we initialize P, S&P, the start and end pointers. So p is, is initialized to zero, or the index of the
leftmost location. And PE is equal to
length of a minus one. That is the index of
the rightmost location. Then we start the
while loop with the condition P S is
less than equal to p. That means we continue
with the while loop. The two pointers do
not cross each other. First, we calculate mate, which as we explained before, is the left biased meet. And then we check if x
is equal to a of mid. That means a value estimate. If a of mid is equal to x, then we have found x and return the location
which is made. If not, then,
depending on whether x is greater than a or x
is less than a half made, we discard half of the array. So if x is greater
than a of mid, we discard the left half of the array and the value itself. That means we set
to mid plus one. If x is less than m it. Then we discard the
right part of the array and we set p to mid minus one. And then again, we calculate mate with this updated
locations of P S&P. And we repeat this way. So in each iteration, we discard half of the array. So in the end, two
things can happen. Either X is found
and in that case, we return the corresponding
location of X or X is not found. And P, S&P cross each other. And we come out of
this while loop and return minus
one. In that case. I hope you get the basic idea how this binary search
algorithm works. That's all for this lesson.
6. Binary Search Python Program: Hello everyone. In this lesson, you learn the Python program
for binary search. Here is the binary
search function, which you have already seen. Also, we have written a main function which
calls the binary search. So let's put a breakpoint in the main function and run it. So we are at the breakpoint. So first, we create an array which is already
sorted. As you can see. Please keep an eye on the
variable section where you can see the current
values of the variables. We define x to seven. And then we call binary search function
with a and x as inputs. We want to find the
location of X in a. So let's enter the
binary search function. First, P, S&P. The start and end pointers initialized to 0.7 respectively, as you'll see in the
variable section. Then we enter the while loop with the condition P
is less than equal to p. Then we calculate mid
value of media is three. And then we check whether x
is equal to or less than, equal or less than or
greater than meat. Note that when we
compare x with meat, what we really mean is the
value at point a of mid, if it is equal to meet it and
we have already found it, and the function returns. But if not, then it resets. Either p is RPE depending on whether x is greater
than or less than. Let's see. So here the value
of x is seven as we know, and a of mid is three. So x is not equal to x
is greater than a half. So we reset the pointer
ps to make plus one. This step, discard half of that. So go up to the next iteration. With the new values of P S&P. The new value of P, S
is four and p is seven. So we are now looking
at the sub array, starting at fault location and up to this certain location, we calculate meet again. The value of meat is now
five is equal to eight. So currently is
less than a of mid. So it comes here. And now we set p0
to mid minus one. Now look at the
variables section P, BE and PAs have the same
value, which is four. So the point to the same
location in the array. We calculate mid. Mid
is also for obviously. So now x is equal to f meet. And we return mid, which is the value four. So we have returned from the binary search function
and the result is four. That means X is present at index four of the sorted array. Let's change X, 7-9. And then again step
through this program. We have the same LEA, which is already sorted. We set x to nine and then
enter the binary search. So P, S&P are initialized. Start the loop. The value of meat
initially is three. So x is not equal to
x is greater than m, It is a bs plus one. And continue to the
next iteration. And now MIT is five. So AF made is not equal
to x, is less than x. So we reset now
ps to make gloves on and go to the next iteration. Calculate meet
again, which is six. So AF made his decision now, which is not equal to x. No, x is less than a of mid. Certainly come here and
do a reset p minus one. Now, notice that the value of P, S is six and the
value of B is five. That means P, S&P have
crossed each other. Here, the while loop breaks
and we return minus one. So you will see the
result is minus one. In this case, the value of x is not found in
the sorted array, so it returns minus one. I suggest you step through
this binary search function in your Python development
environment so that you get familiar
with the internal steps. And call this function with different sorted arrays
having different lengths. And thus get familiar with the internal working
of this algorithm. That's all for this lesson.
Suman Datta, just a coder
