Data Structure And Algorithms In Python — 1

Everyone of us has heard about Data Structure and Algorithms. Now lets try to understand, what is Data Structure and Algorithm.

We will cover multiple blogs on the same going forward.

A Data Structure is basically a named location that is used in order to store or retrieve data. Whereas an Algorithm is a collection of steps that is used in order to solve a particular problem. And in order to write efficient and optimized computer problems it is important to have a good knowledge of Data Structures and Algorithms (DSA).

Algorithm: how to systematically perform a task:- In simple words, Write down sequence of steps for a “Recipe”, or program.

Today We will cover very basic example of GCD program in python.

GCD: The greatest common divisor of two or more numbers is the greatest common factor number that divides them, exactly. It is also called the highest common factor (HCF).

Example, the greatest common factor of 25 and 10 is 5, since both the numbers can be divided by 5.

Some points to be remember before creating this function in Python

1. Computing gcd(m,n)
2. Create two lists of factors of m and n respectively.
3. Report the largest number that appears on both lists.
4. Factors of m and n must be between “1 and m” and “1 and n” respectively.
5. Test each number in this range
6. For m — If it divides m without a remainder, add it to list of
   factors.
7. For n — If it divides m without a remainder, add it to list of
   factors

Example : —

Computing gcd(14,63)

list of factors for both numbers

Now we have list of common factors for both 14 and 63 — There are 2 common factors of 14 and 63, that are 1 and 7. Therefore, the greatest common factor of 14 and 63 is 7.

Steps while creating an algorithm for gcd(m,n): —

1. Use fm, fn for list of factors of m, n, respectively.
2. For each i from 1 to m, add i to fm if i divides m.
3. For each j from 1 to n, add j to fn if j divides n.
4. Use cf for list of common factors.
5. For each f in fm, add f to cf if f also appears in fn.
6. Return largest (rightmost) value in cf

Some points to note: —

1. Use names to remember intermediate values
   → e.g., m, n, fm, fn, cf, i, j, f
2. Values can be single items or collections
   → m, n, i, j, f are single numbers
   → fm, fn, cf are lists of numbers
3. Assign values to names
   → Explicitly, fn = [], and implicitly, for f in cf:
4. Update them, fn.append(i)
5. Program is a sequence of steps
6. Some steps are repeated
   → Do the same thing for each item in a list
7. Some steps are executed conditionally
   → Do something if a value meets some requirement

Thank you for reading. Links to other blogs: —

Hessian Matrix
First order and Second order — Calculus
Statistical Inference 2 — Hypothesis Testing
Statistical Inference
Central Limit Theorem — Statistics
10 alternatives for Cloud based Jupyter notebook!!