Lovely Professional University,Punjab
Format For Instruction Plan [for Courses with Lectures and Labs
Course No
Cours Title
Course Planner
CSE205
DATA STRUCTURES
14594 :: Usha Mittal
Text Book:
Other Specific Book:
Lectures Tutorial Practical Credits
4
1 Schaum Outline series by: Seymour Lipschutz, Publishers: Tata McGraw Hill, New Delhi,Year of Publication:2006
2 Adam Drozdek, Data Structure & Algorithms in C++. Thomson
3 Yashwant P Kanetkar, Title: Let Us C
Other Reading
Sr No
Jouranls atricles as compulsary readings (specific articles, Complete reference)
4 http://projects.csail.mit.edu/jacm/jacm80.html
5 http://bryanpendleton.blogspot.com/2010/06/distributed-data-structures.html
6 http://comjnl.oxfordjournals.org/content/28/1/44.short
7 http://onlinelibrary.wiley.com/journal/10.1002/%28ISSN%291097-0118
8 http://www1.cs.columbia.edu/~sanders/graphtheory/writings/journals.html
9 http://www.informatik.uni-trier.de/~ley/db/journals/jgt/jgt48.html
Relevant Websites
Sr. No. (Web adress) (only if relevant to the courses)
Salient Features
10 http://en.wikipedia.org/wiki/Array_data_structure
Arrays in data structures
11 http://www.java2s.com/Code/Cpp/Pointer/Pointer-Array.htm
Pointer Arrays
12 http://en.wikipedia.org/wiki/Linked_list
Linked List
13 http://en.wikipedia.org/wiki/Stack_(data_structure)
Stacks
Approved for Spring Session 2011-12
14 http://en.wikipedia.org/wiki/Queue_(data_structure)
Queues
15 http://www.cmpe.boun.edu.tr/~akin/cmpe223/chap2.htm
Stacks and Queues
16 http://www.cs.auckland.ac.nz/~jmor159/PLDS210/recursion.ht Recursion
ml
17 http://en.wikipedia.org/wiki/Binary_tree
Binary Tree
18 http://en.wikipedia.org/wiki/Binary_search_tree
Binary Search tree
19 http://xw2k.nist.gov/dads//HTML/binarySearchTree.html
Binary search Tree
20 http://isg.cs.tcd.ie/giangt/Heaps.pdf
Heap
21 http://hamilton.bell.ac.uk/swdev2/notes/notes_18.pdf
Graphs
22 http://hamilton.bell.ac.uk/swdev2/notes/notes_17.pdf
Hashing
23 http://en.wikipedia.org/wiki/Hash_table
Hash Table
24 http://www.google.co.in/url?
Hashing ppt
sa=t&source=web&cd=1&ved=0CBUQFjAA&url=http%3A%2F
%2Fwww.cs.sjsu.edu%2F~lee%2Fcs157b
%2FHashing.ppt&rct=j&q=hashing%20in%20data
%20structure%20ppt&ei=jUK0TIn0F4GivQOjtoCmCg&us
25 http://www.google.co.in/url?
Searching and sorting
sa=t&source=web&cd=1&ved=0CBUQFjAA&url=http%3A%2F
%2Fwww.macs.hw.ac.uk%2F~bpalmer
%2FDSA1%2FLectures%2FWeek%25204%2520Searching
%2520and%2520sorting.ppt&rct=j&q=searching%20an
26 http://pw1.netcom.com/~tjensen/ptr/pointers.htm
introduction to pointers
Detailed Plan For Lectures
Week Number Lecture Number Lecture Topic
Chapters/Sections of Pedagogical tool
Textbook/other
Demonstration/case
reference
study/images/anmatio
n ctc. planned
Part 1
Week 1
Lecture 1
Basic concepts and notations, data structures and
data structure operations
->Reference :1,Ch 1
Sec 1.1 1.2 1.3 1.4
Lecture 2
Basic Data structures like arrays, linked list, stacks
and queues etc.
->Reference :1,Ch 1
Sec 1.1 1.2 1.3 1.4 1.5
Approved for Spring Session 2011-12
Week 1
Week 2
Week 3
Week 4
Lecture 3
Complexity Analysis: Mathematical notation and
functions, algorithmic complexity and time space
trade off, Big O Notation
->Reference :1,Ch 2
sec 2.1 2.2 2.3 2.4 2.5
2.6 2.7 2.8
Lecture 4
The best, average & Worst cases analysis
methodology
->Reference :1,Ch 2
sec 2.5 2.6
Lecture 5
Introduction to arrays, Representation of arrays in
memory, traversing linear arrays.
->Reference :1,Ch 4
sec 4.1 4.2 4.3 4.4
Lecture 6
Operations on arrays: insertion and deletion
->Reference :1,Ch 4
sec 4.5
Lecture 7
Linear Search and Binary Search and analysis of
their complexity
->Reference :1,Ch 4
sec 4.7 4.8
Lecture 8
Multidimensional Arrays, Pointers; Pointer Arrays
->Reference :1,Ch 4
sec 4.9 4.10
Lecture 9
Records; Records Structures, Representation of
records in memory
->Reference :1,Ch 4
sec 4.11 4.12
Lecture 10
Dynamic memory management,Usage of pointers,
memory management functions,
debugging pointers
->Reference
:3,Chapter 5
->Reference :26
Lecture 11
Introduction to linked list, Representation in
memory, Traversing of linked list
->Reference :1,Ch 5
Sec 5.1 5.2 5.3 5.4
Lecture 12
Searching in sorted linked list and in unsorted linked ->Reference :1,Ch 5
list. Memory Allocation
Sec 5.5 5.6
Lecture 13
Insertion into linked list
->Reference :1,Ch 5
Sec 5.7
Lecture 14
Deletion in linked list
->Reference :1,Ch 5
Sec 5.8
Lecture 15
Header linked list and its operations
->Reference :1,Ch 5
Sec 5.9
Lecture 16
Circular linked list and its operations
->Reference :1,Ch 5
Sec 5.9
Lecture 17
Two way linked list, traversing and searching in two ->Reference :1,Ch 5
way linked list
Sec 5.10
Lecture 18
Insertion in two way linked list
Lecture 19
Deletion in two way linked list. Applications of linked ->Reference :1,Ch 5
list.
Sec 5.10
Lecture 20
Conduct Test 1
Arrays.ppt
multidimensional_array.
ppt
Term Paper Allotment
Part 2
Week 4
Week 5
circular_linked_list.ppt
->Reference :1,Ch 5
Sec 5.10
Allotment of mini project
Approved for Spring Session 2011-12
Week 6
Week 7
Lecture 21
Introduction to stacks, sequential and linked
representation of stacks.
->Reference :1,Ch 6
sec 6.1 6.2 6.3 6.4
stacks.ppt
Lecture 22
Stack Operations
->Reference :1,Ch 6
sec 6.5
Lecture 23
Applications of linked list: Arithmetic expressions;
polish notation
->Reference :1,Ch 6
sec 6.5
Lecture 24
Applications of linked list: Arithmetic expressions;
polish notation
->Reference :1,Ch 6
sec 6.7 6.8
Recursion.ppt
Lecture 25
Definition of Recursion, Function Call & Recursion
implementation & Complexity issues,
->Reference :1,Ch 6
sec 6.10 6.11
Queues.ppt
Lecture 26
Tower of hanoi
->Reference :1,Ch 6
sec 6.12 6.13
Lecture 27
Introduction to Queues, Representation in memory, ->Reference :1,Ch 7
Operations on queues
sec 7.1 7.2 7.3 7.4
Lecture 28
Various types of queues and its applications
->Reference :1,Ch 7
sec 7.4
MID-TERM
Part 3
Week 8
Week 9
Week 10
Lecture 29
Introduction of binary trees,basic terminology,
representing binary trees in memory,
->Reference :1,Ch 7
sec 7.4
Lecture 30
Traversal of binary trees using stack.
->Reference :1,Ch 7
sec 7.7 7.8
Lecture 31
Introduction to BST, searching in BST
->Reference :1,Ch 7
sec 7.8
Lecture 32
Insertion & Deletion in BST
->Reference :1,Ch 7
sec 7.9
Lecture 33
AVL Search Trees, Insertion in AVL Search trees
->Reference :1,Ch 7
sec 7.10 7.11
Lecture 34
Deletion in AVL Search Trees
->Reference :1,Ch 7
sec 7.12
Lecture 35
Heaps, insertion in heap
->Reference :1,Ch 7
sec 7.17
Lecture 36
Deletion in heap, Heap sort, Heaps as priority
Queues.
->Reference :1,Ch 7
sec 7.17
Lecture 37
Huffman Algorithm
->Reference :1,Ch 7
sec 7.18
Lecture 38
Introduction to graphs, basic terminology
Lecture 39
Sequential and linked representation
->Reference :1,Ch 8
sec 8.1 8.2 8.3 8.5
heap.ppt
graphs.ppt
Approved for Spring Session 2011-12
Part 4
Week 10
Lecture 40
Traversing a graph(BFS, DFS)
->Reference :1,Ch 8
sec 8.7
Week 11
Lecture 41
Warshall's Algorithm, Shortest Path
->Reference :1,Ch 8
sec 8.4
Lecture 42
Topological Sorting, Applications of Graphs
->Reference :1,Ch 8
sec 8.8
Lecture 43
Hashing, hash table, hash Functions
->Reference :1,Ch 9
sec 9.9
Lecture 44
Various types of hash functions, Collision resolution ->Reference :1,Ch 9
techniques.
sec 9.9
Lecture 45
Searching and sorting use of various data structures ->Reference :1,Ch 9
for searching and sorting
sec 9.1 9.2
Lecture 46
Bubble Sort
->Reference :1,Ch 4
sec 4.6
sorting.ppt
Lecture 47
Insertion Sort
->Reference :1,Ch 9
sec 9.3
sorting.ppt
Lecture 48
Selection Sort
->Reference :1,Ch 9
sec 9.4
sorting.ppt
Lecture 49
Merge Sort
->Reference :1,Ch 9
sec 9.6
sorting.ppt
Lecture 50
Quick Sort
->Reference :1,Ch 6
sec 6.6
sorting.ppt
Lecture 51
Radix Sort
->Reference :1,Ch 9
sec 9.7
sorting.ppt
Lecture 52
Comparison of all the sorting algorithms and their
complexity analysis
->Reference :1,ch 9
sorting.ppt
Week 12
Week 13
Submission of mini
project
Term Paper Submission
Hashing.ppt
Spill Over
Week 14
Lecture 53
Abstract data types
Lecture 54
Uses of queues in Operating System
Details of homework and case studies
Approved for Spring Session 2011-12
Homework No.
Objective
Test 1
To have a
knowledge of
basics of data
Structure
Mini project 1
Term Paper 1
Topic of the Homework
Nature of homework
(group/individuals/field
work
Syllabus covered from week 1 to week 4
Individual
Evaluation Mode
Allottment /
submission
Week
Written Test
3/5
To have the
A mini project is allocated to a group of 3 students. Mini project be Group
knowledge of
like implementation of telephone directory, address book, English
practical concepts dictionary etc.
of data structures.
Mini Project
5 / 10
To have the
knowledge of
basic data
structure and
applications of
data structures.
Term paper
3 / 11
Term Paper
Individual
Scheme for CA:out of 100*
Component
Frequency
Term Paper,Test,Mini project
Out Of
2
Each Marks Total Marks
3
Total :-
10
20
10
20
* In ENG courses wherever the total exceeds 100, consider x best out of y components of CA, as explained in teacher's guide available on the
UMS
List of suggested topics for term paper[at least 15] (Student to spend about 15 hrs on any one specified term paper)
Sr. No. Topic
1 AVL trees and its operations .Comparisons with other trees and uses
2 In depth comparisons of all sorting algorithms and considering the cases in which a particular sorting
3 Role of Data Structures in Compiler Design
4 Compare the practical performance of Fibonacci heaps and binary heaps.
5 Complexity of Algorithms
6 Queue and its uses in Opearting System
Approved for Spring Session 2011-12
7 Application of Linked Lists in Operating System at least 4 cases
8 Role of Data Structures in Programming languages
9 Different Balanced binary trees
10 Comparative study of BFS, DFS on trees and graphs
11 Fault tolerant data structures
12 Comparative Study of Dynamic and Static Array
13 Multi-dimension Linked Lists
14 Travelling salesman problem
15 Hashing
Approved for Spring Session 2011-12
