/Most-Important-Algorithms-for-Btech-CSE

important algorithms

Primary LanguageJava

#Most Important Algorithms For BTech. CSE

This repository is for all the important algorithms and programs for Btech. CSE students. Anyone can contribute their algorithms and programs it would be highly appreciated.

Following are the topics on which programs are currently available:

1. Backtracking: Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that “works”. Problems which are typically solved using backtracking technique have following property in common. These problems can only be solved by trying every possible configuration and each configuration is tried only once. A Naive solution for these problems is to try all configurations and output a configuration that follows given problem constraints. Backtracking works in incremental way and is an optimization over the Naive solution where all possible configurations are generated and tried.

Available programs are:

  • Hamiltonian Cycle
  • N-Queen
  • Hamiltonian Cycle
  • Permutation of String
  • Sudoku
  • Tug of War
  • Rat Maze

2. Divide and Conquer: Divide and Conquer is an algorithmic paradigm. A typical Divide and Conquer algorithm solves a problem using following three steps.

  1. Divide: Break the given problem into sub-problems of same type.
  2. Conquer: Recursively solve these sub-problems
  3. Combine: Appropriately combine the answers

Available programs are:

  • Count Inversion
  • Median Of 2 Sorted Arrays
  • Power ( x , n )
  • Optimized Count Inversion
  • Optimized Median Of 2 Sorted Arrays
  • Optimized and Extended Version of Power( x , n )

3. Greedy Algorithms: Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems. An optimization problem can be solved using Greedy if the problem has the following property: At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.
If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem as the Greedy algorithms are in general more efficient than other techniques like Dynamic Programming. But Greedy algorithms cannot always be applied. For example, Fractional Knapsack problem can be solved using Greedy, but [0-1] Knapsack cannot be solved using Greedy.

Available programs are:

  • Activity Selection
  • Dijkstra's Algorithm
  • Huffman Coding
  • Kruskal's MST Algorithm
  • Prim's MST Algorithm
  • Prim's MST for Adjacency List Representation

4. Searching Algorithms: Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Based on the type of search operation, these algorithms are generally classified into two categories:

  1. Sequential Search: In this, the list or array is traversed sequentially and every element is checked. For example: Linear Search.
  2. Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half. For Example: Binary Search.

Available programs are:

  • Linear Search
  • iterative Binary Search
  • Recursive Binary Search

5. Sorting Algorithms:- A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of element in the respective data structure.

Available programs are:

  • Bubble Sort

  • Heap Sort

  • Insertion Sort

  • Merge Sort

  • Optimized Bubble Sort

  • Quick Sort

  • Selection Sort

  • Shell Sort

    This is all for now. Contribution of any type is highly appreciated.