Computer Algorithms

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

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