Unit 1 Introduction to Algorithms and Analysis

6 lecture hours

• Overview and importance of algorithms and data structures
• Fundamentals of algorithm analysis
• Space and time complexity of an algorithm
• Types of asymptotic notations and orders of growth
• Algorithm efficiency – best case
• worst case
• average case
• Analysis of non-recursive and recursive algorithms
• Asymptotic analysis for recurrence relation – Recursive Tree Method

Unit 2 Linear Data Structures

8 lecture hours

• Array- 1D and 2D array
• Stack - Applications of stack: Expression Evaluation - Conversion of Infix to postfix and prefix expression
• Tower of Hanoi
• Queue - Types of Queue: Circular Queue
• Double Ended Queue (deQueue)
• Applications – Priority Queue using Arrays
• List - Singly linked lists – Doubly linked lists - Circular linked lists

Unit 3 Sorting and Searching Techniques, Hashing

7 lecture hours

• Searching - Linear Search and binary search (divide and conquer technique)
• Applications - Sorting – Insertion sort - Selection sort – Bubble sort – Quick sort – Merge sort
• Analysis of sorting algorithms
• Hash functions
• open hashing-separate chaining
• closed hashing - linear probing
• quadratic probing
• double hashing

Unit 4 Divide and Conquer Algorithm

4 lecture hours

• Recurrence, and different methods to solve recurrence
• multiplying large Integers Problem

Unit 5 Non-linear Data Structures – Trees

7 lecture hours

• Tree - Terminology
• Binary Tree – Terminology and Properties
• Tree Traversals
• Expression Trees – Binary Search Trees – operations in BST – insertion
• finding min and max, Finding the kth minimum element in a BST, AVL tree

Unit 6 Non-linear Data Structures – Graphs

4 lecture hours

• Graph – basic definition and Terminology – Representation of Graph – Graph Traversal: Breadth First Search (BFS)
• Depth First Search (DFS)

Unit 7 Greedy Algorithm

• General Characteristics of greedy algorithms
• Problem solving using Greedy Algorithm - Activity selection problem
• Elements of Greedy Strategy
• 04 Subject Code: 3134201 w.e.f
• AY 2020-21 Minimum Spanning trees (Kruskal’s algorithm
• Prim’s algorithm)
• Graphs: Shortest paths
• The Knapsack Problem
• Job Scheduling Problem

Unit 8 Dynamic Programming

5 lecture hours

• The Principle of Optimality
• Problem Solving using Dynamic Programming – Calculating the Binomial Coefficient
• Making Change Problem
• Assembly Line-Scheduling
• Knapsack problem
• Matrix chain multiplication
• Longest Common Subsequence

Unit 9 Backtracking and Branch and Bound

3 lecture hours

• The Eight queens’ problem
• Knapsack problem
• Travelling Salesman problem
• Minimax principle