DOC/LP/01/28.02.02

/ LESSON PLAN / LP-IT2201
LP Rev. No: 02
Date: 25-06-12
Page 01 of 06
Sub Code & Name :IT2201Data Structures and Algorithms
Unit:I Branch: IT Semester: III

Unit syllabus:

Abstract Data Types (ADT) – List ADT – array-based implementation – linked list implementation – cursor-based linked lists – doubly-linked lists – applications of lists – Stack ADT – Queue ADT – circular queue implementation – Applications of stacks and queues

Objective:

This Unit emphasizes on various implementations of Abstract Data Type (ADT)

Session
No / Topics to be covered / Time / Ref / Pg.No / Teaching Method
1 /

Introduction to Data Structures and Abstract Data Types

The Stack ADT
Array and Linked List Implementation Of Stacks / 50m / 1(87-95)
4(83-97) / BB/OHP
2 / Applications of Stack
Infix to postfix conversion ,Balancing symbols, Postfix Evaluation,Recursion,Backtracking / 50m / 1(87-95)
4(83-97) / BB/OHP
3 / The Queue ADT
Queue Model
Array Implementation Of Queues / 50m / 1(95-100)
3(252-260) / BB
4 / The Queue ADT
Circular Queues
Applications Of Queues / 50m / 1(100)
3(230-238) / BB/OHP
5 /

The List ADT

Array based implementation / 50m / 1 (57-59)
4(187-194) / BB
6 /

The List ADT

Linked list based implementation / 50m / 1(59)
4(170-185) / BB/OHP
7 /

The List ADT

Cursor based implementation
Doubly Linked list / 50m / 1(73-78) / BB/OHP
8 /

The List ADT

Doubly Linked list continuation
Circular Linked list / 50m / 1(67-68)
4(213-228) / BB/OHP
9 / Application of list
Polynomial ADT
Multi List / 50m / 1(68-73)
3(110-113) / BB
/ LESSON PLAN / LP-IT2201
LP Rev. No: 02
Date: 25-06-12
Page 02 of 06
Sub Code & Name IT2201 Data Structures and Algorithms
Unit:II Branch: IT Semester: III

Unit syllabus:

Tree ADT – tree traversals – left child right sibling data structures for general trees – Binary Tree ADT – expression trees – applications of trees – binary search tree ADT – AVL trees – binary heaps

Objective:

This unit provides knowledge to students about tree algorithms.

Session
No / Topics to be covered / Time / Ref / Pg.No / Teaching Method
10 / Tree ADT
Basic Terminology of Trees
Tree Traversals / 50m / 1(105-107)
3(273-278) / BB
11 / Tree ADT
Implementation of trees
Left child Right sibling data structures for general trees / 50m / 2(84-93) / BB
12 / Binary Tree ADT
Implementation of binary tree / 50m / 1(111-113)
3(272-273) / BB/OHP
13 / Binary Tree ADT
Expression trees
Application of trees – directory structure / 50m / 1(113-116)
3(280-282) / BB
14 / Binary Search Tree ADT
Implementation / 50m / 1(116-126)
3(309-323) / BB/OHP
15 / AVL Trees
Insertion
Single Rotation
Double Rotation / 50m / 1(126-139) / BB
16 / AVL Trees
Implementation-Searching,deletion / 50m / 1(126-139) / BB/OHP
17 / Binary Heaps
Structure property
Heap order property / 50m / 1(195-205) / BB
18 / Binary Heaps
Operations-insertion,deletion / 50m / 1(195-205) / BB/OHP
CAT-I
/ LESSON PLAN / LP-IT2201
LP Rev. No: 02
Date: 25-06-12
Page 03 of 06
Sub Code & Name :IT2201Data Structures and Algorithms
Unit:III Branch: IT Semester: III

Unit syllabus:

Hashing – Separate chaining – open addressing – rehashing – extendible hashing – Disjoint Set ADT – dynamic equivalence problem – smart union algorithms – path compression – applications of Sets

Objective:

To impart knowledge to students on Hashing and Disjoint Set ADT

Session
No / Topics to be covered / Time / Ref / Pg.No / Teaching Method
19 / Hashing
Introduction,
Hash function / 50m / 1(165-168) / BB
20 / Hashing
Separate chaining / 50m / 1(168-173) / BB
21 / Open Addressing
Linear Probing
Quadratic Probing / 50m / 1(173-181) / BB
22 / Double Hashing
Re-Hashing / 50m / 1(181-188) / BB
23 / Double Hashing
Extendible Hashing / 50m / 1(181-188) / BB
24 / The Disjoint Set ADT
Equivalence Relations
Dynamic Equivalence Problem / 50m / 1(279-281) / BB
25 / The Disjoint Set ADT
Basic Data Structure
Smart union algorithms / 50m / 1(285-287) / BB/OHP
26 / The Disjoint Set ADT
Path compression / 50m / 1(287-295) / BB
27 / The Disjoint Set ADT
Applications of sets / 50m / 1(287-295) / BB
/ LESSON PLAN / LP-IT2201
LP Rev. No: 02
Date: 25-06-12
Page 04 of 06
Sub Code & Name :IT2201Data Structures And Algorithms
Unit:IV Branch: IT Semester: III

Unit syllabus:

Definitions – Topological sort – breadth-first traversal - shortest-path algorithms – minimum spanning tree – Prim's and Kruskal's algorithms – Depth-first traversal – biconnectivity – Euler circuits – applications of graphs

Objective:

This unit provides an explanation to students about graphs and graph traversals.

Session
No / Topics to be covered / Time / Ref / Pg.No / Teaching Method
28 /

Introduction to Graph

Basic Terminology of Graphs

Representations Of Graphs

Applications of Graph / 50m / 1(299-302)
2(198-199) / BB
29 /

Topological Sort

Implementation / 50m / 1(302-306) / BB/OHP
30 /

Breadth – first Traversal

Implementation / 50m / 2(215-219)
3(487-488) / BB
31 / Shortest-Path Algorithms
Unweighted Shortest Paths / 50m / 1(306-324)
4(514-516) / BB
32 / Shortest-Path Algorithms
Dijkstra’s Algorithm / 50m / 1(295-303)
3(518-522) / BB
33 / Minimum Spanning Tree
Prim’s Algorithm / 50m / 1(329-332)
2(233-239) / BB
34 / Minimum Spanning Tree
Kruskal’s Algorithm / 50m / 1(332-335)
2(233-239) / BB
35 /

Depth-First Traversal

Implementation / 50m / 1(335-338)
3(485-487) / BB
36 /

Applications of Depth-First Traversal

Undirected Graphs

Biconnectivity / 50m / 1(338-342)
4(556-558) / BB/OHP
37 /

Applications ofDepth-First Search

Euler Circuits
Directed graphs
Finding Strong Components / 50m / 1(342-345)
4(559-561) / BB/OHP
CAT II
/ LESSON PLAN / LP-IT2201
LP Rev. No: 02
Date: 25-06-12
Page 05 of 06
Sub Code & Name :IT2201Data Structures and Algorithms
Unit:V Branch: IT Semester: III

Unit syllabus:

Introduction to algorithm design techniques: Greedy algorithms Divide and conquer, Dynamic programming, backtracking, branch and bound, Randomized algorithms – Introduction to algorithm analysis: asymptotic notations, recurrences – Introduction to NP-complete problems

Objective:

This unit provides knowledge to students about various algorithm design techniques

Session
No / Topics to be covered / Time / Ref / Pg.No. / Teaching Method
38 /

Introduction to Algorithm Analysis

Asymptotic notations
Time complexity
Recurrences / 50m / 2(17-27)
2(293-298) / BB/OHP
39 / Greedy Algorithm
Simple Scheduling Problem
Bin Packing / 50m / 1(347-364)
2(321-323) / BB
40 / Divide and Conquer
Closest –Points Problem
Integer Multiplication / 50m / 1(365-374)
2(306-310) / BB
41 / Dynamic Programming
Fibonacci series
All pairs shortest paths / 50m / 1(380-391)
2(311-320) / BB
42 / Randomized Algorithms
Random Number Generators / 50m / 1(399-400) / BB
43 /

BackTracking Algorithms

Games – Tic Tac Toe , 8 Queens Problem / 50m / 1(401-412)
2(324-335) / BB
44 / Intoduction to Branch and Bound / 50m / 4(548-570) / BB
45 / Introduction to NP completeness / 50m / 1(348-353) / BB/OHP
CAT III
/ LESSON PLAN / LP-IT2201
LP Rev. No: 02
Date: 25-06-12
Page 06 of 06
Sub Code & Name :IT2201Data Structures and Algorithms
Branch: IT Semester: III

Course Delivery Plan:

Week / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15
I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II
Units / / 1 / / 2 / / 3 / / 4 / / 5 /

Books Referred: CAT-I CAT-II CAT-III

TEXT BOOK:

1. M. A. Weiss, “Data Structures and Algorithm Analysis in C”, Second Edition,

Pearson Education, 1997.

REFERENCES:

2. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, “Data Structures and Algorithms”, Pearson Education, 1983.

3. R. F. Gilberg, B. A. Forouzan, “Data Structures”, Second Edition, Thomson India Edition, 2005.

4. Sara Baase and A. Van Gelder, “Computer Algorithms”, Third Edition, Pearson Education, 2000.

5. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to algorithms", Second Edition, Prentice Hall of India Ltd, 2001.

Prepared by / Approved by
Signature
Name /
R.Dhanalakshmi AP/IT
M.Vijayasanthi AP/IT / Prof. G.Sumathi
HOD / IT
Date / 25/06/12 / 25/06/12