DATA STRUCTURE & ALGORITHMS

Subject Code: BEETC-405T/BEEN-405T/BEEC-405T Credits:03

UNIT I: Data Structures (7Marks)
Introduction to Data Structures, Need of Data Structure, Abstract Data type, Types of
Data StructuresAlgorithms: Algorithm, Efficiency of an Algorithm, Time and Space

Complexity, Asymptotic notations (Big O, Omega Ω, Theta  ), Time-Space trade-
off.Searching- Linear & Binary Search, Sorting- Bubble Sort, Insertion Sort, Selection

Sort, Algorithm design strategies - Divide and Conquer strategy, Merge Sort, Quick Sort,
complexity analysis of sorting methods.

UNIT II: Abstract Data Types (ADTs) Arrays (8 Marks)
Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major
Order, and Column Major Order, Application of arrays
Stacks- Introduction, PUSH and POP operations on Stacks, Prefix, Infix & Postfix
expressions- Conversion and Evaluation, Multiple Stacks.
Queues- Introduction, Insertion & deletion in Queues, Circular Queues, Priority Queues.

UNIT III: Linked List- Linked List as ADT (7Marks)

Dynamic Memory Allocation Functions, Types of Linked Lists- (single, double, circular),
Operations on Linked Lists- (create, insert, delete, reverse etc.), Applications of Linked
List- Polynomial Representation (Addition/deletion/multiplication of two polynomials).
Trees- Introduction, Implementation of Trees, Tree Traversals with an Application,
Binary Trees, BST- Insertion & Deletion, Expression Trees, AVL Trees, Heap Trees.

UNIT IV: Graphs (7 Marks)
Graphs- Data Structures for Graphs, Graph Traversals Directed Graphs, Graph Storage
Structures (Adjacency Matrix, Adjacency List) Weighted Graphs, Shortest Paths, and
Minimum spanning Trees. Applications of DFS and BFS.
HASING TECHNIQUES
Symbol Tables: static tree tables, dynamic tree tables, hash tables, hash functions,
Collision resolution, overflow handling, Applications

UNIT V: ALGORITHMS (7Marks)
Advanced algorithms based on the data structures. Shortest-Path Algorithms, Dijkstra's
Algorithm, Graphs with Negative Edge Costs, Acyclic Graphs, Network Flow Problems, Matrix
Chain Multiplication, Longest Common Subsequence, Optimal Binary Search Tree,
Backtracking strategy - 4 queens problem, Hamiltonian Path.

Text books:
1. Data Structures with C, Seymour Lipschutz, Schaums Outlines, Tata McGraw Hill
Education.
2. Fundamentals of Computer Algorithms by Horowitz, Sahni,Galgotia Pub. 2001 ed.
3. Data Structures using C and C++ by Y. Langsam, Pearson Education.
4. Data Structures using C by Tanenbaum, Pearson Education
5. Data structures and Algorithm Analysis in C, 2nd edition, M.A.Weiss, Pearson
Reference books:
1. Data Structures and program design in C by Robert Kruse, Bruce Leung & Clovis
Tondo.
2. Data Structures: A Pseudocode Approach with C by Richard F. Gilberg and
BehrouForouzan.
3. Fundamentals of Data Structures, Illustrated Edition by Ellis Horowitz,
SartajSahni,Computer Science Press.

4. Introduction to Algorithms, by Thomas Corman III edition, PHI
5. Analysis and Design of Algorithms: A Beginner's Approach, by Rajesh K. Shukla,
Willey Publications
6. “Algorithms, Data Structuresand Problem Solving with C++”, Illustrated Edition
by Mark Allen Weiss, Addison-Wesley Publishing Company.