The course is one of the courses of Bachelor of Computer Applications programme of IGNOU. This course help to learn about properties of algorithm and how to design an algorithm, discuss asymptotic notations, Design and measure time complexity analysis of searching, sorting and Graph traversal algorithms. Make comparison of different type of algorithm likes Linear, Quadratic, Polynomial and Exponential. Describe how greedy approach facilitate solving the problem. Discuss Divide and Conquer approach for solving the problem. The topics included in the course are: BLOCK 1: Introduction to Algorithm Unit 1: Basics of an Algorithm Definition and Example of an algorithm, Characteristics of an algorithm, Steps in Designing of Algorithms, Growth of function, Recurrence, Problem Formulation (Tower of Hanoi), Substitution Method, Iteration Method, Master Method. Unit 2: Asymptotic Bounds Asymptotic Notations, Concept of efficiency of analysis of an algorithm Comparative efficiencies of algorithms: Linear, Quadratic, Polynomial and Exponential. Unit 3: Analysis of simple Algorithms Euclid’s algorithm for GCD, Horner’s Rule for polynomial evaluation, Simple Matrix (n x n) Multiplication, Exponent evaluation e.g. an, Searching, Linear Search, Sorting, Bubble sort, Insertion Sort, Selection sort. BLOCK 2: Design Techniques Unit 1: Greedy Technique Elements of Greedy strategy, Activity Selection Problem, Continuous Knapsack Problem, Coin changing Problem, More Examples. Unit 2: Divide and Conquer Approach General Issues in Divide and Conquer, Binary Search, Merge Sort, Quick Sort, Integer Multiplication, More Examples. Unit 3: Graph Algorithm Representation of Graphs, Adjacency Matrix, Adjacency List, Depth First Search and Examples, Breadth First Search and Examples.
Overview
Syllabus
Week(s)
Unit (S)
Title of the Video Session
Block and Unit of the Course
Week-1
Block 1: Introduction to Algorithm
Unit -1: Basics of an Algorithm
1. Definition and Example of an algorithm, Characteristics of an algorithm, Steps in Designing of Algorithms
Block 1: Unit 1
2. Growth of function, Recurrence, Problem Formulation (Tower of Hanoi)
Block 1: Unit 1
3. Substitution Method, Iteration Method, Master Method
Block 1: Unit 1
Week-2
Block 1: Introduction to Algorithm
Unit -2: Asymptotic Bounds
4. Asymptotic Notations, Concept of efficiency of analysis of an algorithm Comparative efficiencies of algorithms: Linear
Block 1: Unit 2
5. Comparative efficiencies of algorithms: Quadratic and Plynomial Polynomial
Block 1: Unit 2
6. Comparative efficiencies of algorithms: Exponential
Block 1 and Unit 2
Week-3
Block 1: Introduction to Algorithm
Unit 3: Analysis of simple Algorithms
7. Euclid’s algorithm for GCD, Horner’s Rule for polynomial evaluation
Block 1 and Unit 3
8. Simple Matrix (n x n) Multiplication
Block 1 and Unit 3
9. Exponent evaluation e.g. an
Block 1 and Unit 3
10. Searching, Linear Search; Sorting, Bubble sort
Block 1 and Unit 3
11. Insertion Sort, Selection sort.
Block 1 and Unit 3
Week-4
Block 2: Design Techniques
Unit 1: Greedy Technique
12. Elements of Greedy strategy, Activity Selection Problem
Block 2 and Unit 1
13. Continuous Knapsack Problem, Coin changing Problem
Block 2 and Unit 1
14. More Examples of Greedy Techniques
Block 2 and Unit 1
Week-5
Block 2: Design Techniques
Unit 2: Divide and Conquer Approach
15. General Issues in Divide and Conquer, Binary Search
Block 2 and Unit 2
16. Merge Sort, Quick Sort
Block 2 and Unit 2
17. Integer Multiplication, More Examples
Block 2 and Unit 2
Week-6
Block 2: Design Techniques
Unit 3: Graph Algorithms
18. Representation of Graphs, Adjacency Matrix, Adjacency List
Block 2 and Unit 3
19. Depth First Search and Examples
Block 2 and Unit 3
20. Breadth First Search and Examples.
Block 2 and Unit 3
Taught by
Prof. Divakar Yadav
