Mahesh Goyani

Algorithm is set of rules defined in specific order to do certain computation and carry out some predefined task. Algorithm is step by step procedure to solve the problem.

The first ever algorithm was developed by Babylonians for factorization of number and to find roots of the equation. Euclid had proposed a famous algorithm for finding greatest common divisor (GCD) of two numbers.

Algorithm reads some data as an input, processes it and generates the information as an output. Well understood problem is converted to algorithmic steps and which in turn, converted in to program. Algorithm makes coding easier for programmer. Algorithmic notation bridges the semantic gap between problem description and programming language syntax.

A good algorithm should have following properties / characteristics :

Input : Algorithm may take zero or more input arguments. Depending on problem, input may be scalar, vector, array, tree, graph or some other data structures.
Output : Algorithm processes input presented to it, processes it and produces at least one value as output. Output also may be scalar, vector, array, tree, graph or some other data structure.
Definiteness : All instructions in algorithm should be unambiguous. Instruction should be simple to interpret. There should not be multiple ways to interpret the same instruction.
initeness :Every algorithm must terminate after finite number of steps. If algorithm contains loop, upper bound of loop must be finite. Recursive calls should have well defined base case.
Effectiveness :Algorithm should be written with basic set of instruction. It should not use hypothetical higher level instruction to carry out complex tasks. Underlying architecture of machine may have instruction for multiplying two numbers, but it should not have instruction to find factorial of n, or Fibonacci series. Such operations must be computed with the help of basic set of instructions.

Course Detail

Syllabus for Internal Examination

Introduction: From problems to programs, set theory, functions and relations Insertion sort, analyzing algorithms, designing algorithms, asymptotic notation.
Divide and conquer: Strassen’s algorithm for matrix multiplication, The substitution method for solving recurrences, The recursion tree method for solving recurrences, master method
Dynamic programming: Making Change, The principal of optimality, the knapsack problem, Floyd’s algorithm for shortest paths
Greedy Algorithms: making change, Knapsack problem, Shortest Path – Dijkstra’s algorithm, Huffman codes

Reading Material

Topics	Topics
Introduction To Algorithms: What is Algorithm? – Nutshell Explanation Evolution of Algorithm – Origin and History How a Smart Algorithm Can beat a Great Hardware? 3 ways to Representing Solution to the Problem Correctness of Algorithm – Concept and Proof Efficient Algorithm Writing – Tricks and Examples Proof Techniques for Algorithms Set Theory – Mathematics for Algorithm	Efficiency Analysis: Approaches for Efficiency Analysis of Algorithm Efficiency Analysis Framework of Algorithm Asymptotic Notations – Big Oh, Omega, and Theta Examples on Asymptotic Notation – Upper, Lower and Tight Bound Analyzing Control Structures in Algorithm Tower of Hanoi – Algorithm and Recurrence Equation
Sorting Algorithms: Sorting Algorithm Bubble Sort Selection Sort Insertion Sort Heap Sort Shell Sort Merge Sort Quick Sort Counting Sort Radix Sort Bucket Sort	Divide and Conquer: Divide and Conquer Strategy for Problem Solving Linear Search Binary Search Convex Hull Problem Max-Min Problem Large Integer Multiplication problem Strassen's Matrix Multiplication Exponential Problem
Greedy Algorithms: Greedy Algorithm – What Every one Has to Say? Binary Knapsack Problem using Greedy Algorithm Fractional Knapsack Using Greedy Algorithm Job Scheduling using Greedy Algorithm Activity Selection Problem Huffman Coding Optimal Storage on Tapes Optimal Merge Pattern Basics of Graph – Terminologies You Must Know Prim’s Algorithm Kruskal’s Algorithm Prim’s vs Kruskal Algorithm Dijkstra’s Algorithm – Single Source Shortest Path Algorithm	Dynamic Programming: Introduction to Dynamic Programming Divide and Conquer Vs Dynamic Programming Dynamic Programming Vs Greedy Algorithm Greedy vs Divide and Conquer Approach Binomial Coefficient Making Change Problem Knapsack Problem using Dynamic Programming Multistage Graph Problem Optimal Binary Search Tree Matrix Chain Multiplication Problem Longest Common Subsequence Bellman Ford Algorithm All Pairs Shortest Path (Floyd-Warshall) Algorithm Assembly Line Scheduling Traveling Salesman Problem Flow Shop Scheduling
Graph Algorithms: Graph Representation Methods: Matrix and List Depth First Search Breadth First Search Depth First Search vs. Breadth First Search Topological Sort Connected Components in Graph Preconditioning	Backtracking: Backtracking – What, Why, and How? Control Abstraction for Backtracking N Queen Problem Examples of N Queen Problem Sum of Subsets Graph Coloring Problem Knapsack Problem Hamiltonian Cycle
Branch and Bound Branch and Bound Backtracking Vs Branch and Bound Dynamic Programming vs Branch and Bound Least Cost Branch and Bound FIFO Branch and Bound Job Sequencing Knapsack Problem Travelling Salesman Problem Minimax Principle	String Matching: String Matching Algorithms Naive String Matching Algorithm Rabin Karp String Matching Algorithm KMP String Matching Algorithm

Interview Questions on Algorithms

MCQs on Algorithms

Course Detail

Syllabus for Internal Examination

Introduction: From problems to programs, set theory, functions and relations Insertion sort, analyzing algorithms, designing algorithms, asymptotic notation.
Divide and conquer: Strassen’s algorithm for matrix multiplication, The substitution method for solving recurrences, The recursion tree method for solving recurrences, master method
Dynamic programming: Making Change, The principal of optimality, the knapsack problem, Floyd’s algorithm for shortest paths
Greedy Algorithms: making change, Knapsack problem, Shortest Path – Dijkstra’s algorithm, Huffman codes

Course Detail

Syllabus for Internal Examination

Basics of Algorithms and Mathematics: What is an algorithm?, Mathematics for Algorithmic Sets, Functions and Relations, Vectors and Matrices, Linear Inequalities and Linear Equations.
Analysis of Algorithm: The efficient algorithm, Average, Best and worst case analysis, Amortized analysis , Asymptotic Notations, Analyzing control statement, Loop invariant and the correctness of the algorithm, Sorting Algorithms and analysis: Bubble sort, Selection sort, Insertion sort, Shell sort Heap sort, Sorting in linear time : Bucket sort, Radix sort and Counting sort
Divide and Conquer Algorithm: Introduction, Recurrence and different methods to solve recurrence, Multiplying large Integers Problem, Problem Solving using divide and conquer algorithm - Binary Search, Max-Min problem, Sorting (Merge Sort, Quick Sort), Matrix Multiplication, Exponential.
Dynamic Programming: Introduction, The Principle of Optimality, Problem Solving using Dynamic Programming – Calculating the Binomial Coefficient, Making Change Problem, Assembly Line-Scheduling, Knapsack problem, All Points Shortest path, Matrix chain multiplication, Longest Common Subsequence.
Greedy Algorithm: General Characteristics of greedy algorithms, Problem solving using Greedy Algorithm - Activity selection problem, Elements of Greedy Strategy, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm), Graphs: Shortest paths, The Knapsack Problem, Job Scheduling Problem, Huffman code.

Course Detail

Syllabus for Internal Examination

Introduction: From problems to programs, set theory, functions and relations Insertion sort, analyzing algorithms, designing algorithms, asymptotic notation.
Divide and conquer: Strassen’s algorithm for matrix multiplication, The substitution method for solving recurrences, The recursion tree method for solving recurrences, master method
Dynamic programming: Making Change, The principal of optimality, the knapsack problem, Floyd’s algorithm for shortest paths
Greedy Algorithms: making change, Knapsack problem, Shortest Path – Dijkstra’s algorithm, Huffman codes

Course Detail

Syllabus for Internal Examination

Introduction To Algorithms
Growth of Function & Asymptotic Notation
Pseudo Code Conventions
Sorting Methods (Quadratic Time): Insertion Sort, Bubble Sort, Selection Sort
Sorting Methods (Log - Linear Time): Merge Sort, Quick Sort, Heap Sort
Sorting Methods (Linear Time): Radix Sort
Array & Storage Structure of Array
Structure & Array of Structures
Stack & Its Applications
Queue, Doubly Ended Queue, Circular Queue
Priority Queue
Applications of Queue

Video Tutorials

Web Resources

Academic Year : 2023-24 (UG)

Academic Year : 2022-23 (UG)

Academic Year : 2019-20 (UG)

Academic Year : 2018-19 (PG)

Academic Year : 2017-18 (UG)