EVEN 2020 - Lecture Plan
15B11CI411 – Algorithms and Problem Solving
Course Coordinator – Sherry Garg (J62) / Varsha Garg (J128)
Title of the
Lecture # Topics to be Discussed
Module
Lecture 1 General discussion about time and space
requirements in an algorithm. Asymptotic
notations (Big O, Big Omega, etc.)
Lecture 2 Asymptotic analysis using various interactive
algorithms, e.g. linear search, finding maximum
and minimum elements in an array, etc.
Lecture 3 Finding recurrences for various recursive
Introduction
algorithms, e.g. binary search, merge sort, quick
sort, median search, heap sort, etc.
Lecture 4 Solving recurrences using substitution method
Lecture 5 Solving recurrences using tree substitution
method
Lecture 6 Solving recurrences using Master’s Theorem
method
Lecture 7 Query efficient data structures, segment tree
and interval tree. Various operations, e.g. insert,
range search, etc. on segment tree and interval
tree
Lecture 8 Structure of the balanced binary search tree, RB
tree, insert operations in RB tree. Discussion of
the improved search efficiency using RB tree
Search Trees
Lecture 9 Delete operation on RB tree
and
Lecture 10 Overview of the implementation of priority
Priority
queue using binary heap. Creation of priority
Queue
queue using binomial heap
Lecture 11 Analysis of the insert, extract min, and merge
operations on binomial heap. Structure of the
Fibonacci heap
Lecture 12 Insert, extract min, merge, delete, and decrease
key operations on Fibonacci heap and their
analysis
Lecture 13 Design Fundamentals of Divide and Conquer (D&C)
Technique: approach. Review of D&C based searching and
Divide and sorting techniques
Lecture 14 Conquer D&C based Strassen’s matrix multiplication and
finding closest pair in 1D and 2D search spaces
Lecture 15 Design Depth first and breadth first searches in graph.
Technique: Review of the backtracking algorithms using N
Backtracking queen and rat in a maze problem. Backtrack
Algorithms based solution approach for the graph colouring
problem
Lecture 16 Backtracking based strategy for finding
Hamiltonian Cycle in un-weighted graph. Solving
traveling salesman problem using backtracking
Lecture 17 Finding maximum flow in the flow network using
DFS and BFS. Discussion of the residual flow
network
Lecture 18 Computation of the maximum flow in the given
flow network using Ford Fulkerson and Edmond
Karp algorithms
Lecture 19 Introduction to the greedy design technique,
effectiveness of the objective function, finding
minimum spanning tree (MST) using Kruskal’s
algorithm, efficient data structures for
implementation of Kruskal’s algorithm
Lecture 20 Prim’s algorithm for finding the MST.
Effectiveness of different data structures for
implementation of the Prim’s algorithm
Lecture 21 Finding single source shortest path using greedy
design technique based Dijkstra’s algorithm,
objective functions for solving Knapsack (0/1 and
Design
fractional) and coinage problems
Technique:
Lecture 22 Discussion of the various objective functions
Greedy
(first fit, best fit, etc.) for solving packing
Algorithms
problems in 1D (Strip packing), 2D & 3D (bin
packing and container loading). Greedy
algorithm (shortest job first, etc.) for solving
scheduling problems
Lecture 23 Solving the problem of graph colouring using
greedy design technique. Discussion of the
applications of the graph colouring in scheduling
problems, e.g. time table scheduling
Lecture 24 Greedy design technique based schemes
(Huffman and Shannon-Fano) for text
compression
Lecture 25 Discussion of the NP completeness and NP hard
Tractable
problems, listing of various NP hard problems,
and Non-
viz. vertex cover, graph color, Hamiltonian cycles,
Tractable
etc.
Problems
Lecture 26 Solution approaches for NP hard problems
Lecture 27 Dynamic Fundamentals of Dynamic Programming, e.g.
Programming sub-problem identification, overlapping sub-
problems/states, memorization scheme, and
recurrence. Developing the recurrence for
solving the 0/1 Knapsack problem
Lecture 28 Solving 0/1 Knapsack and Coinage problem using
Dynamic Programming
Lecture 29 Discussion of the all source all destination
shortest path using dynamic programming
Lecture 30 Finding longest common subsequence in given
two strings using dynamic programming
Lecture 31 Developing the dynamic programming based
solution strategy for Matrix Chain Multiplication
and String Editing problem
Lecture 32 Finding longest increasing sequence using
dynamic programming. Discussion of the
problems based on LIS
Lecture 33 Real life applications of String matching, Brute
force approach for finding patterns in given text
Lecture 34 Pattern matching using finite automata. Finding
multiple patterns in a given text using finite
automata
Lecture 35 Approach of Knuth Morris Pratt for pattern
String
matching
Algorithms
Lecture 36 Hashing based approach (Rabin Karp) for pattern
matching
Lecture 37 Data structures (Tries and compressed tries) for
string
Lecture 38 Suffix tree and Suffix array data structures and
related operation for string handling
Lecture 39 Introduction to problem solving, search space,
discussion of various puzzles e.g. 8-puzzle, tic-
tac-toe, etc. as examples of problem solving
Lecture 40 Discussion of uninformed search and informed
Problem search, relevance of heuristics for implementing
Spaces and the informed search, informed search using Hill
Problem
solving by climbing, solving puzzles using hill climbing
Lecture 41 search Informed search using Best first search. Analysis
of the performance of the hill climbing and best
first search techniques of informed search
Lecture 42 Discussion of A* algorithm. Finding shortest path
using A* algorithm