CSE256
CSE256
CSE256
CO1 :: describe the process to find efficiency of algorithms and arrays in real world
CO2 :: illustrate the importance of Linked List in context of real world problems
CO3 :: differentiate the Stack and Queue data structures for problem solving
Unit I
Introduction : Basic Concepts and Notations, Complexity analysis: time space and trade off, how to
calculate complexity of iterative and recursive algorithm., Omega Notation, Theta Notation, O
Notation, Basic Data Structures
Arrays : Linear arrays: memory representation, Array operations: traversal, insertion, deletion,
sorting, searching and merging and their complexity analysis.
Sorting : Bubble sort, Insertion sort, Selection sort
Unit II
Linked Lists : Introduction, Memory representation and allocation, Linked List Operations: Traversal,
Insertion, Deletion and their complexity analysis, Header linked list, Two-way lists: operations on two
way linked lists, Grounded and Circular Linked List
Unit III
Stacks : Introduction: List and Array representations, Operations on stack (traversal, push and pop),
Arithmetic expressions: polish notation, evaluation and transformation of expressions.
Queue : Array and list representation, operations (traversal, insertion and deletion), Priority Queues,
Deques
Recursion : Introduction, Recursive implementation of Towers of Hanoi, Merge sort, Quick sort
Unit IV
Trees : Introduction, Memory representation, Basic terminologies and properties, Tree traversal:
Inorder, Preorder and Postorder, Binary Tree: Introduction, Insertion, Deletion and Searching, Binary
Search Tree: Introduction, Insertion, Deletion and Searching
AVL trees and Heaps : AVL Tree: Introduction, Insertion, Deletion and Searching, Heap Tree:
Introduction, Insertion, Deletion, Searching and Heap sort, Huffman coding
Unit V
Graphs : Introduction, Memory representation, Types of Graphs, Basic Properties, Graph Traversal:
BFS, DFS, Shortest path algorithm, Warshall's algorithm, Floyd Warshall Algorithm(modified warshall
algorithm)
Unit VI
Hashing : Hashing introduction: hash functions, hash table, Open hashing (separate chaining),
Closed hashing (open addressing): linear probing, quadratic probing and double hashing.
Programs:
• Array: Program to implement insertion and deletion operations in arrays
• Searching: Program to implement different searching techniques - linear and binary search
• Sorting: Program to implement different sorting techniques – bubble, selection and insertion sort
• Linked List: Program to implement searching, insertion and deletion operations in linked list
• Doubly Linked List: Program to implement searching, insertion and deletion operations in doubly
linked list
• Stack: Program to implement push and pop operations in stacks using both arrays and linked list
• Recursive Sorting: Program to implement recursive sorting techniques - merge sort, quick sort
• Tree: Program to create and traverse a binary tree recursively and iteratively.
• Binary Search Tree: Program to implement searching, insertion and deletion operations in BST
Text Books:
1. DATA STRUCTURES by SEYMOUR LIPSCHUTZ, M.G.Hills
References:
1. DATA STRUCTURES AND ALGORITHMS BY PEARSON by ALFRED V. AHO, JEFFREY D.
ULLMAN AND JOHN E. HOPCROFT,, PEARSON