School of Computer Engineering

Kalinga Institute of Industrial Technology (KIIT)

Deemed to be University
Bhubaneswar-751024

Lesson Plan and Activity Calendar

Design and Analysis of Algorithms – CS 2012 (L-T-P-Cr: 2-1-0-3)

Semester: 5th
Discipline: B.Tech. (CS, IT, CSSE, CSCE)
Session: Autumn 2023

Instructor:
Name : Meghana G Raj
Chamber : Faculty Room Number- 09, Block-B, Campus-15
Contact Number : +91-9000177935
Email : [email protected]

Lesson Plan

Mod. No. Module Name Topics to be covered Lecture

No. of
serial
lectures
nos.
 Concepts in algorithm analysis & design
- motivation
 Complexity of an algorithm (Space and
time Complexity)
 Analysis of time complexity of Insertion
Sort by step count method
1. Introduction  Growth of functions 8 1-8
 Asymptotic notations (O, Θ
 Solving recurrences
(Iterative/Substitution/ Recurrence
Tree/Master theorem/Change of
variable method)
Tutorials / Activity
 Structure of Divide-and-Conquer
algorithm
 Analysis of divide-and-conquer run
time recurrence relations of
Divide and  Binary Search
 Merge Sort
2. Conquer 9 9-17
 Quick Sort
Method, Heap  Randomized Quick Sort
 Building a heap
 Heap sort algorithm
 Priority queue
Tutorials / Activity
  Overview of Greedy paradigm
Greedy  Fractional knapsack problem
3.  Activity selection problem 4 18-21
Method  Huffman’s code
Tutorials / Activity
 Overview of Dynamic Programming
paradigm
Dynamic  Difference between Divide and Conquer
4. and Dynamic Programming 4 22-25
Programming
 Matrix Chain Multiplication
 Longest Common Subsequence
Tutorials / Activity
 Dis-joint Set Data Structure
 Representation Of Graph
 Graph Traversals :: BFS DFS
 Single Source Shortest Path
- Dijkstra’s Algorithm
Graph - Bellman-Ford Algorithm
5. 10 26-35
Algorithms  All Pair Shortest Path
Floyd-Warshall Algorithm
 Minimum Cost Spanning Tree
- Kruskal’s Algorithm
- Prim’s Algorithm
Tutorials / Activity
Computationa  Complexity Classes: P, NP, NP-Hard and
6. NP-Complete 2 36-37
l Complexity
Tutorials / Activity
Day-wise Lesson Handouts:

Week Lecture Topics

No.
Week - 1 1 Concepts in algorithm analysis & design. It’s motivation. Difference between
Algorithm and Programs, Characteristics of algorithms, Performance
Analysis: Space and Time Complexity
2 Pseudo code Conventions, Analysis of Linear Search by step count method,
Analysis of Insertion Sort by step count method (Incremental Approach),
Best-case, Worst-case and Average-case Analysis.
3 Amortized Complexity, Growth of functions, Asymptotic Notations ()
Week - 2 4 Asymptotic Notations (), Asymptotic Notation Properties
5 Recurrences, solving recurrences using Iterative, Substitution method
6 Divide-and-Conquer Approach, Merge Sort Algorithm
Week – 3 7 Analyzing divide-and-conquer algorithms, Analysis of merge-sort
8 Solving recurrences using Recursion-tree method
9 Solving recurrences using Master method
Week - 4 10 Change of Variable method, More recurrence examples
11 Binary Search and its complexity analysis
12 Quicksort Algorithm, Performance of quicksort (Worst-case, Best-case and
Balanced Partitioning)
Week - 5 13 Randomized Algorithms: An informal description
14 Randomized Quicksort and its complexity analysis
15 Introduction to Heap, Maintaining the heap property, Building a heap
Week - 6 16 Heap-sort algorithm and its complexity analysis
17 Application of Heap: Priority Queues
18 Overview of Greedy paradigm, An Activity Selection Problem: Recursive,
Iterative greedy algorithm
Week - 7 19 Elements of greedy strategy
20 Knapsack Problem, Difference between Fractional Knapsack and 0/1
Knapsack
21 Huffman codes, Constructing a Huffman code (tree)
Week - 8 22 Overview of Dynamic Programming paradigm, Divide and Conquer vs
Dynamic Programming, Greedy vs Dynamic Programming
23 Matrix Chain Multiplication
24 Elements of dynamic programming, Tabulation vs Memoization
Week - 9 25 Longest Common Subsequence
26 Dis-joint Set Data Structure
27 Representation Of Graph and its terminology
Week - 10 28 Graph Traversals: BFS
29 Graph Traversals: DFS
30 Single Source Shortest Path: Dijkstra’s Algorithm
Week - 11 31 Single Source Shortest Path: Bellman-Ford Algorithm
32 All Pair Shortest Path: Floyd-Warshall Algorithm
33 Introduction to Spanning Tree
Week - 12 34 Minimum Cost Spanning Tree: Kruskal’s Algorithm
35 Minimum Cost Spanning Tree: Prim’s Algorithm
36 Complexity Classes: P, NP, NP-Hard and NP-Complete
Week - 13 37 NP-Complete Problems: The Clique problems
38 Revisions
Activity Calendar - Autumn 2023(Tentative)

Activity Marks
Type of Activity Probable Date CO
No. (Weightage)

QUIZ TEST-1
1 07.08.23 – 11.08.23 5
(Scheduled MCQ/ Subjective Test)

HOME ASSIGNMENT
2 21.08.23 – 25.08.23 5
(Individual Home Assignments)

CLASS TEST/SURPRISE TEST

3 28-08.23 – 01.09.23 5
(Class Test/ Surprise Test)
Mid Semester Examination [11th Sep 2023 – 16th Sep 2023]
QUIZ TEST-2
4 09.10.23 – 13.10.23 5
(Scheduled MCQ/ Subjective Test)
CLASS PARTICIPATION
5 01.11.23 - 10.11.23 5
(Attendance + Group Presentation)
PROGRAMMING
ASSIGNMENT
6 13.11.23 – 17.11.23 5
(Programming Assignments/Case
Studies based on Critical Thinking)
End Semester Examination [25th Nov 2023 – 2nd Dec 2023]

Course Outcome:
CO1: analyse the asymptotic performance of algorithms
CO2: understand different algorithm design techniques
CO3: apply important algorithm design paradigms and methods of analysis
CO4: demonstrate familiarity with major algorithms and data structures
CO5: modify existing algorithms to apply in common engineering design situations.
CO6: understand different classes of problems P, NP, NP-Complete and NP-Hard.

Text books:
 Thomas H. Coreman, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
“Introduction to Algorithms”, PHI.
 Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, “Fundamentals of
Computer Algorithms”, Universities Press.

Reference books:
 Jon Kleinberg, Eva Tardos, “Algorithm Design”, Pearson.
 Michael T. Goodrich, Roberto Tamassia, “Algorithm Design: Foundations,
Analysis, and Internet Examples”, Wiley India.
Grading Policy:

Pedagogy: Lecture, Assignments, Quiz, Debate, Summarization, Short Projects

Evaluation Methodology: Internal: 50 (20- Midterm Exam & 30 Activity), End Term: 50
Distribution of Marks:

SL Evaluation Evaluation Course Lecture No. Mode

No. Component Marks
From To

1 Mid-Semester 20 1 21 Closed Book

Examination
2 Activity based 30 NA NA Open Book, Closed
Teaching and Book and
Learning Presentation, Short
quiz
3 End-Semester 50 1 37 Closed Book
Examination

Note #
 Tentative Mid-Semester Syllabus would be up to Greedy Method as per
the Lesson Plan.
 Modifications to the above-mentioned structure (Lesson Plan /
Examination Process / Any other modifications) may take place as per
the University Guidelines.

=======================XXXXXXXX====================