Code Pumpkin

Data Structures and Algorithms

Data Structures

A data structure is a particular way of organizing data in a computer so that it can be used effectively. The idea is to reduce the space and time complexities of different tasks. Here is the list of some of most used data structures in computer science.

  1. Array
  2. Stack Implementation Using Array
  3. Array List
  4. Linked List
  5. Heap (Min/Max Heap)
  6. Tree
  7. Graph
  8. Set
  9. Map

What is Algorithm?

We know that a computer cannot do anything by itself. We have to program a computer. So, a program should be based on well defined solution for a specific problem. If the solution is not defined properly, we cannot expect the right response from a computer, because that computer is not properly instructedby the programmer. This step by step instructions are nothing but an algorithm.

In other words, Algorithm is  a set of well defined instructions to achieve specific outcome or transform the input into the output.

Any real life problems can be solved using two steps. 

  1. Define the problem.
  2. Design the algorithm ti solve that problem.

One of the challenge for any programmer is to analyse time and space complexity of the algorithm and optimize it for better performance. In below set of articles, we have tried to cover some of the algorithms with thier time and space complexity analysis.


Recursion – Backtracking

In backtracking algorithms you try to build a solution one step at a time. If at some step it becomes clear that the current path that you are on cannot lead to a solution you go back to the previous step (backtrack) and choose a different path. Briefly, once you exhaust all your options at a certain step you go back.

Think of a labyrinth or maze – how do you find a way from an entrance to an exit? Once you reach a dead end, you must backtrack. But backtrack to where? to the previous choice point. Here is the list of problems which can be solved using recursion backtracking.

  1. Sudoku Solver
  2. N Queen Problem

Searching

Searching is a process of checking and finding an element from a list of elements. Let A be a collection of data elements and we want to search element  in collection A. The search is said to be successful, if X does appear in and unsuccessful otherwise. There are several types of searching techniques; one has some advantages over other. Following are some of the important searching techniques.

  1. Linear or Sequential Searching – not recommended
  2. Binary Search
  3. Fibonacci Search
  4. Interpolation Search
  5. Hashing

Sorting

One of the fundamental problem of computer science is ordering a list of records. Computer systems are often used to store large amount of data from which individual records must be retrieved according to some search criterian. Searching becomes much easier if these records are sorted. There are plenty of sorting algorithms available. Each one has their pros and cons. 

  1. Bubble Sort
  2. Selection Sort
  3. Insertion Sort
  4. Merge Sort
  5. Quick Sort
  6. Heap Sort
  7. Shell Sort
  8. Radix Sort
  9. Radix Exchange Sort

Graph

Graph is a non linear data structure, it contains a set of points known as nodes (or vertices) and set of links known as edges which connects the vertices. The pictorial representation is shown in the image in the right pane. There are various algorithm which are based on graph data structure from which we have covered below :

  1. Graph Search – Breadth First Search
  2. Graph Search – Depth First Search

We will keep adding graph related algorithms in this section, stay tuned 🙂 

Directed Graph


Total Posts : 124
follow us in feedly

Like Us On Facebook