/Data-Structures-and-Algorithms

This repository contains data structure programs and solutions [ in C++] of a problem using different techniques like Dynamic Programming , Greedy Algorithms , Divide and Conquer , Backtracking etc.

Primary LanguageC++MIT LicenseMIT

Data Structures and Algorithms

This repository contains data structure programs and solutions in C++ of a problem using different techniques like Dynamic Programming , Greedy Algorithms , Divide and Conquer , Backtracking etc.

Algorithm Design Techniques

Dynamic Programming
    Dynamic Programming is a method for solving a complex problem by breaking it down into a 
collection of simpler subproblems, solving each of those subproblems just once, and storing 
their solutions using a memory-based data structure (array, map,etc). Each of the subproblem 
solutions is indexed in some way, typically based on the values of its input parameters, so 
as to facilitate its lookup. So the next time the same subproblem occurs, instead of recomputing
its solution, one simply looks up the previously computed solution, thereby saving computation
time. This technique of storing solutions to subproblems instead of recomputing them is called
memoization.

Here's some problems and their solution(s):



Greedy Algorithms
    A greedy algorithm, as the name suggests, always makes the choice that seems to be the 
best at that moment. This means that it makes a locally-optimal choice in the hope that 
this choice will lead to a globally-optimal solution.

Here's some problems and their solution(s):



Divide and Conquer
  A typical Divide and Conquer algorithm solves a problem using following three steps.
    - Divide: Break the given problem into subproblems of same type.
    - Conquer: Recursively solve these subproblems
    - Combine: Appropriately combine the answers

Here's some problems and their solution(s):



Backtracking
    Backtracking is a general algorithm for finding all (or some) solutions to some 
computational problems, notably constraint satisfaction problems, that incrementally
builds candidates to the solutions, and abandons a candidate ("backtracks") as soon 
as it determines that the candidate cannot possibly be completed to a valid solution.

Here's some problems and their solution(s):



Miscellaneous
    Except above algorithm design techniques , here's some important
algorithms.

Here's some problems and their solution(s):



Data Structures

Array/Vector
    An array is a collection of items stored at contiguous memory locations. The idea is to 
store multiple items of the same type together. This makes it easier to calculate the position
of each element by simply adding an offset to a base value, i.e., the memory location of the 
first element of the array (generally denoted by the name of the array).
    Vector is Dynamic Array.
    Matrix is 2D Array.

Here's some problems and their solution(s):



Matrix
    Matrix is 2D Array. A matrix is defined as an ordered rectangular array of 
    numbers. They can be used to represent systems of linear equations

Here's some problems and their solution(s):



Linked List
    A linked list is a linear data structure, in which the elements are not stored at 
contiguous memory locations.

Here's some problems and their solution(s):



Binary Tree
    A tree whose elements have at most 2 children is called a binary tree. Since each element 
in a binary tree can have only 2 children, we typically name them the left and right child.

Here's some problems and their solution(s):



Binary Search Tree
    Binary Search Tree is a node-based binary tree data structure which has the following properties:
    - The left subtree of a node contains only nodes with keys lesser than the node’s key.
    - The right subtree of a node contains only nodes with keys greater than the node’s key.
    - The left and right subtree each must also be a binary search tree.

Here's some problems and their solution(s):



Heap
    A Heap is a special Tree-based data structure in which the tree is a complete binary tree. 
Generally, Heaps can be of two types:
     - Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys
            present at all of it’s children. The same property must be recursively true for all 
            sub-trees in that Binary Tree.
     - Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys 
            present at all of it’s children. The same property must be recursively true for all 
            sub-trees in that Binary Tree.


Hash Map
    Hashing is an important Data Structure which is designed to use a special function 
called the Hash function which is used to map a given value with a particular key for 
faster access of elements. The efficiency of mapping depends of the efficiency of the 
hash function used.


Graph
    A Graph is a non-linear data structure consisting of nodes and edges. The nodes are
sometimes also referred to as vertices and the edges are lines or arcs that connect any 
two nodes in the graph.

Here's some problems and their solution(s):



Trie
    In computer science, a trie, also called digital tree, radix tree or prefix tree is a 
kind of search tree—an ordered tree data structure used to store a dynamic set or associative 
array where the keys are usually strings. Unlike a binary search tree, no node in the tree 
stores the key associated with that node; instead, its position in the tree defines the key 
with which it is associated. All the descendants of a node have a common prefix of the string
associated with that node, and the root is associated with the empty string. Keys tend to be 
associated with leaves, though some inner nodes may correspond to keys of interest. Hence, 
keys are not necessarily associated with every node. For the space-optimized presentation of 
prefix tree, see compact prefix tree.