abdullaharean/design-and-analysis-of-algorithm-data-structure

Data structure and algorithms are two of the most important aspects of computer science. Data structures allow us to organize and store data, while algorithms allow us to process that data in a meaningful way.

Design-and-Analysis-of-Algorithm

Data Type :

A data type is something that defines a domain of allowed values and the operations that can be performed on those values.
For example in C language, the int data type can take values in range and operations that can be performed are addition, subtraction, multiplication, division and all those stuff which can be done with numbers in mathematics.
Similarly, there are many other data types like float, double, String, char, boolean, etc.
These data types are built-in data types also known as primitive data types and the values and operations for them are pre-defined in the programming language.
If an application needs to use a data type other than the primitive data types of language, then it is the programmer’s responsibility to specify the values and operations for that data type and implement it. For example, there is no built-in type dates in c, and if we need to process dates, we have to define and implement a data type for a date.

Abstract Data Types (ADT) :

An abstract data type is a mathematical model or concept that defines a data type logically. It specifies a set of data and collection of operations that can be performed on that data.
The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations.
These process of hiding details is also known as Abstraction.
For example, consider Stack ADT
Stack: A stack contains elements of the same type arranged in sequential order and following operations can be performed on the stack.
Stack data structure

1. Initialize() : Initialize the stack to be empty.
   
2. Push(): Insert an element at one end of the stack called top.
   
3. Pop(): Remove and return the element at the top of the stack, if it is not empty.
   
4. Peek(): Return the element at the top of the stack without removing it, if the stack is not empty.
   
5. Size(): Return the number of elements in the stack (i.e size of the stack).
   
6. isEmpty(): Return true if the stack is empty, otherwise return false.
   
7. isFull(): Return true if no more elements can be pushed or added, otherwise return false.
   

Data Structures :

Now, here comes the Data Structures. So what really it is?
Data Structure is a programming construct used to implement an ADT.
It is the physical implementation of ADT. All operations specified in ADT are implemented through functions in the physical implementation. A data structure that is implementing an ADT consists of a collection of variables for storing the data specified in the ADT and the algorithms for implementing the operations specified in ADT.
ADT is the logical view of data and the operations to manipulate the data while Data Structure is the actual representation of data and the algorithms to manipulate the data.

What are the Advantages of Data Structures?

1. Efficiency: Proper choice of data structures make programs efficient in terms of time and space. For Example, suppose we have some data and we need to organize it properly and perform the search operation. If we organize our data in an array, then we will have to search sequentially element by element. If the item to be searched is present at last then we will have to visit all the elements before reaching that element. So the use of array is not very efficient here. There is a better data structure which makes the search process efficient like an ordered array, Binary Search Tree or Hash Table. Different data Structure gives different efficiency.
   
2. Reusability: Data Structures are reusable, i.e, once we have implemented a particular data structure we can use it in any other place or requirement. Implementation of data structure can be compiled into libraries which can be used by different clients.
   
3. Abstraction: Data Structure provides the level of abstraction and hides the detail of how things are working behind the screen. For example, In Stack push() insert the element at top and pop() removes an element from the top. How this insertion and removing is working is hidden from the user. Now, in the next section, we will cover the types of data structure, it’s importance and some brief overview of different data structures.
   

Algorithm

Derived from the name of the mathematician Muhammed ibn-Musa Al-Khowarizmi, an algorithm is a solution to a problem that meets the following criteria.

1. A list of instructions, procedures, or formula that solves a problem.
   
2. Can be proven.
   
3. Something that always finishes and works.
   

How algorithms are used

Today, algorithms are used billions of times every day for a variety of tasks. Below are a few of the different ways algorithms are used.

1. There are many sort algorithms that sort data.
   
2. Algorithms help control traffic lights.
   
3. Computers use algorithms to convert data (e.g., converting decimal into binary).
   
4. Google's search uses the PageRank algorithm to sort searched results.
   
5. Encryption to encrypt and decrypt information and keep data safe is an algorithm.
   
6. GPS uses graph search algorithms to find the best route to a destination.
   
7. Smartphones, Wi-Fi, and wireless communication use algorithms to communicate.
   
8. E-mail spam detection uses algorithms to filter out bad e-mails.
   
9. Data compression for getting information faster (e.g., YouTube video) use algorithms.
   

When was the first algorithm?

Because a cooking recipe could be considered an algorithm, the first algorithm could go back as far as written language. However, many find Euclid's algorithm for finding the greatest common divisor to be the first algorithm. This algorithm was first described in 300 B.C.
Ada Lovelace is credited as being the first computer programmer and the first person to develop an algorithm for a machine.

Code Contents of The Repository

.
├── BS0: Binary Search
│   ├── binarysearch.cpp
│   ├── distancevitto.cpp
│   ├── FindFloorOfAElementInSortedArray.cpp
│   ├── inp.txt
│   ├── kk.cpp
│   ├── LeetCode30.cpp
│   ├── MinimumDifferenceElementInASortedArray.cpp
│   ├── n+nod.cpp
│   ├── Notes.txt
│   ├── peakelement.cpp
│   ├── RotationNumberInSortedRotatedArrayAndIndexOfMinimumElement.cpp
│   ├── SearchAnElementInSortedRotatedArray.cpp
│   ├── SearchingInANearlySortedArray.cpp
│   ├── set_stl_usasge.cpp
│   ├── sqrt.cpp
├── DP0 : Recursion & Backtracking
│   ├── brackets.cpp
│   ├── consecutiveone.cpp
│   ├── friendpairing.cpp
│   ├── hamiltonianpath.cpp
│   ├── input.txt
│   ├── nqueenscount.cpp
│   ├── nqueens.cpp
│   ├── output.txt
│   ├── subsetprint.cpp
│   ├── sudokosolver.cpp
│   ├── tiling_problem.cpp
│   └── towerofhanoi.cpp
├── DP1: Dynamic Programming
│   ├── knapsack_bottomup.cpp
│   ├── knapsack_memo.cpp
│   ├── knapsack_rec.cpp
│   ├── knapsack_testcase.py
│   ├── lcs_bottomup.cpp
│   ├── lcs_memo.cpp
│   ├── lcs_rec.cpp
│   ├── lcs_testcase.py
│   ├── lis_bottomup.cpp
│   ├── lis_memo.cpp
│   ├── lis_rec.cpp
│   ├── lis_testcase.py
│   ├── PrintSetBit.cpp
│   ├── rockclimbing.cpp
│   ├── rockclimbing.py
│   ├── rockclimbing_rec.cpp
│   ├── rodcutting_bottomup.cpp
│   ├── rodcutting_memo.cpp
│   ├── rodcutting_rec.cpp
│   ├── rodcutt_testcase.py
│   ├── test_knapsack.py
│   ├── test_lcs.py
│   ├── test_lis.py
│   └── test_rod.py
├── DP2: Matrix Chain Multiplication
│   ├── MCMBottomUp.cpp
│   ├── MCMmemoization.cpp
│   └── MCMRecursion.cpp
├── DS0: Stack Queue LinkedList
│   ├── allfix_final.cpp
│   ├── circularqueue.cpp
│   ├── infixpostfixprefix.cpp
│   ├── infixtoevaluation.cpp
│   ├── LinkedList.cpp
│   ├── ParanthesesRelated-1.cpp
│   ├── ParanthesesRelated.cpp
│   └── stackqueue.cpp
├── DS1: Tree Binary Tree
│   ├── avltree.cpp
│   ├── BinaryTree.cpp
│   └── BST.cpp
├── DS2: Heap
│   ├── binaryheap.cpp
│   └── BinomialHeap.cpp
├── G1: Basic Graph (BFS, DFS)
│   ├── Bfs.java
│   ├── BfsShortestPath.java
│   ├── Bipartite.java
│   ├── bipartitie.cpp
│   ├── cycle_detection_directed.cpp
│   ├── CycleDetectionDirected.java
│   ├── cycle_detection_undirected.cpp
│   ├── CycleDetectionUndirected.java
│   ├── dfs.java
│   ├── Graph.cpp
│   ├── graphwithedges.cpp
│   ├── topological_sort.cpp
│   └── topologicalSort.java
├── G2: Grid Recursion
│   ├── floodfillalgo.cpp
│   ├── labshortestpathgrid.cpp
│   ├── minimumstepknightneedtoreachtarget.cpp
│   └── ratinamze.cpp
├── G4: Disjoint Set Union
│   ├── dsu1.cpp
│   ├── dsu2.cpp
│   ├── DSUrankPathCompression.java
│   └── inp.txt
├── G5: Bridge Articulation Point
│   ├── articulation point and bridges.cpp
│   ├── ArticulationPointAndBridges.java
│   ├── bestEulerTour.java
│   ├── bridge_articulation.cpp
│   ├── bridge.cpp
│   ├── EulerTour.java
│   ├── inp.txt
│   ├── input1.txt
│   ├── output1.txt
│   └── output.txt
├── G6: Euler Circuit
│   ├── best euler tour.cpp
│   ├── euler tours.cpp
│   └── inp.txt
├── G7: Strongly Connected Compound
│   ├── inp.txt
│   ├── kosaraju algorithm for SCC.cpp
│   ├── KosarajuAlgorithm.java
│   ├── scc.cpp
│   ├── topological Order.cpp
│   └── TopologicalOrder.java
├── G8: Minimum Spanning Tree
│   ├── input1.txt
│   ├── input2.txt
│   ├── input3.txt
│   ├── input4.txt
│   ├── Kruskal Algo Test Driver Code.py
│   ├── Kruskal.java
│   ├── Kruskal_MST.cpp
│   ├── Prim Algo Test Driver Code.py
│   ├── Prim_MST.cpp
│   ├── Prim’s and Kruskal’s Algorithm for Minimum Spanning Tree Analysis.pdf
│   ├── Prims.java
│   ├── Random_Graph_Generation.py
│   └── README.md
├── G9: Shortest Path Algorithm
│   ├── G9.1: Single Source Shortest Path
│   │   ├── 743.network-delay-time.cpp
│   │   ├── bellmanford.cpp
│   │   ├── dijkastra.cpp
│   │   ├── inputdj.txt
│   │   └── Readme.md
│   └── G9.2: All Pair Shortest Path
│   ├── floydwarshallworking.cpp
│   ├── inputdj.txt
│   ├── jhonsonfinal.cpp
│   ├── jhonsons2working.cpp
│   ├── jhonsonsalgorithm.cpp
│   ├── jhonsonscoded.cpp
│   └── output.txt
├── Greedy: Huffman Coding
│   ├── hf1.cpp
│   ├── hf2.cpp
│   └── hftemplate.cpp
├── NF0: Network Flow Basic
│   ├── dinicsAlgo.java
│   ├── dinic's algprithm.cpp
│   ├── driver2.cpp
│   ├── driver.cpp
│   ├── edmond-karp-coded.cpp
│   ├── edmond-karp.cpp
│   ├── edmondkarp_fordfulkerson.cpp
│   ├── inp.txt
│   ├── mbm_maxflow.cpp
│   ├── showsir2.sh
│   ├── showsir.sh
│   └── sirinput.txt
├── NT1: Eucleadian Algorithm GCD
│   ├── gcd_extended.cpp
│   ├── Linear_diaphantine_eqn.png
│   ├── Linear_Diophantine_Equations.cpp
│   ├── multiplicative_modulo_inverse.cpp
│   └── Multiplicative_Modulo_Inverse_using_extended_Eucledian.png
├── Sort1: Sorting Algo
│   ├── CountingInversionUsingMergeSort.cpp
│   └── sorting.cpp
└── T1: Segment Tree
├── FLIPCOIN-codechef.cpp
├── Readme.md
├── segmenttree.cpp
└── segment+tree+with+lazy+propagation.cpp

design-and-analysis-of-algorithm-data-structure's Issues

Prims MST Codes Does Not Handling Decrease Key Operation

Prims algorithm showing error results due to vertex that are not included in MST not handled or their key not changed