Course Handout for "Data Structure & Algorithms" (CS-2001), School of Computer Engineering Autumn-
2019
KALINGA INSTITUTE OF INDUSTRIAL TECHNOLOGY
Deemed to be University
BHUBANESWAR-751024
School of Computer Engineering
Autumn Semester 2019-20
Course Handout
1. Course code : CS 2001
2. Course Title : Data Structure and Algorithms
3. LTP Structure :
L T P Total Credit
3 1 0 4 4
4. Course Coordinator : Dr. Satarupa Mohanty
5. Course Faculty : Dr. Samaresh Mishra
6. Course offered to the School :
Computer Engineering, Electronic Engineering and Electrical Engineering
7. Branch/Section: 4th Semester CSE-1
8. Course Objective:
Understand different ways to represent different kinds of data.
Learn different kinds of operation performed on different representation of data.
Identify and apply the appropriate data structure and algorithm for a specified application.
Analyse the performance of algorithm for different operation performed on data.
Provide solid foundations in foundational aspects of programming – both data structures and
algorithms
Demonstrate the correctness of the algorithm and analyse their computational complexities
9. Course Outcome:
At the end of the course, students will be able to:
CO # Detail
CO1 Understand the concepts of data structure, data type and
abstract data type (ADT) and compute the complexity of different algorithms.
CO2 Understand, distinguish and implement Array and Linked list data structure on different
types of problems.
CO3 Understand and implement different linear data structures such as Stack and Queue to
solve various problems.
Page 1 of 8
Course Handout for "Data Structure & Algorithms" (CS-2001), School of Computer Engineering Autumn-
2019
CO4 Understand and implement different non-linear data structures such as Tree and Graph
on various computing problems.
CO5 Understand and apply standard algorithms for searching, sorting and hashing.
CO6 Effectively choose and design the data structure that efficiently models the
information in a problem.
8. Course Contents
The course focuses on basic and essential topics in data structures and algorithms, including
arrays, linked lists, Stacks, Queues, Trees, sorting algorithms, searching algorithms and graphs.
Sr# Major Area Detailed Area
1 Introduction Structures and Unions, Pointers, Dynamic Memory Allocation,
Algorithm Specification, Space and Time Complexity
2 Arrays Arrays, Abstract Data Type, Dynamically Allocated Arrays,
Polynomials, Two-dimensional Array, Address Calculation, Matrix
Addition and Multiplication, Sparse Matrix, Upper & Lower
Triangular Matrix, Tridiagonal Matrix
3 Linked List Singly Linked Lists and Chains, Representing Chains in C,
Polynomials, Sparse Matrix, Doubly Linked Lists, Circular &
Header Linked lists
4 Stacks and Queues Stacks, Stacks using Dynamic Arrays and Linked List, Queues,
Queue using Dynamic Arrays and Linked List, Circular Queues
using Dynamic Arrays and Linked List, Evaluation of Expressions,
Priority Queue, Dequeue
5 Trees Introduction, Binary Trees, Binary Tree Traversals, Threaded
Binary Trees, Binary Search Trees, AVL Trees, m-way Search
Trees, B-Trees, Introduction to B+-Trees, Tree Operation, Forests
6 Graphs Graph ADT, Graph Operation – DFS, BFS
7 Sorting Insertion Sort, Quick Sort, Merge Sort, Heap Sort, Bubble Sort,
Selection Sort, Radix Sort
8 Searching Linear Search, Binary Search, Hashing – Hash Function, Collision
Resolution Techniques
9. Text Book:
T1. Fundamentals of Data Structures in C, 2nd Edition, Horowitz, Sahani Anderson-Freed, Universities
Press. Pearson, 1st Edition
10. Reference Books:
RB1. Data Structures, Schaum’s OutLines, Seymour Lipschutz, TATA McGraw Hill
RB2. Data Structures using C by Aaron M. Tenenbaum, Yedidyah Langsam, Moshe J.
Augenstein. Pearson, 1st Edition
RB3. Data Structures A Pseudocode Approach with C, 2nd Edition, Richard F. Gilberg,
Page 2 of 8
Course Handout for "Data Structure & Algorithms" (CS-2001), School of Computer Engineering Autumn-
2019
Behrouz Forouzan, CENGAGE Learning, India Edition
RB4. Data Structures Using C, Second Edition, Reema Thereja, Oxford University Press
RB5. Data Structures and Algorithm Analysis in C, Mark Allen Weiss, Pearson Education,
2nd Edition.
11. Reference Site:
RS1. NPTEL - https://onlinecourses.nptel.ac.in/explorer
RS2. Tutorials Point - https://www.tutorialspoint.com/data_structures_algorithms/
RS3. Geeks for geeks - http://www.geeksforgeeks.org/
12. Pre-requisites:
Programming in C (CS-1001)
Mathematics for Computer Science
13. The day-wise course coverage depicts the provisional date of covering individual topics of the
DS&A subject in the academic session of Autumn 2019-2020 .
Monday (Campus-15, C-15) 10:00 AM - 11:00 AM
Tuesday (Campus-15, C-1): 1:00 PM - 2:00 PM
Wednesday (Campus-15, C-4): 11:00 AM -12:00 Noon
Friday (Campus-15, DL-1): 3:00 PM - 4:00 PM Tutorial/Test
Lecture Unit Topics
Day/Date of
No.
Coverage
1-5 Introduction Introduction, Course Outcomes
Day-1,
Course Coverage Plan, Activities
01-07-2019
Evaluations
Structure, Union
Day-2,
Pointers and Dynamic
02-07-2019
Memory Allocation (DMA)
Algorithm Specification Day-3,
Algorithm Analysis 03-07-2019
Day-4,
Tutorial/Activity/Test
05-07-2019
Time Complexity
Day-5,
Space Complexity
08-07-2019
Class Work
Page 3 of 8
Course Handout for "Data Structure & Algorithms" (CS-2001), School of Computer Engineering Autumn-
2019
6-10 Arrays Array Introduction
Row major order and
Day-6,
address calculation
09-07-2019
Pointers to array, Pointer to
structure, Array of pointers
Difference between static
and dynamic memory
allocation
Day-7,
DMA – 1-D and 2-D arrays
10-07-2019
Problem Solving
Array abstract data type (ADT)
Problem Solving
Tutorial/Activity/Test Day-8,
12-07-2019
Polynomial & its Operation Day-9,
Matrix Operation 15-07-2019
Sparse Matrix and its Operation
Day- 10,
Class Work 16-07-2019
11-21 Linked List Introduction to Linked List
Advantages,
Disadvantages, Day-11,
Application 17-07-2019
Types of Linked List
Representation
Class Work
Tutorial/Activity/Test Day-12,
19-07-2019
Single Linked List Operation –
Traversal, Insertion, Deletion, Day-13,
Insert Last, Delete Last 22-07-2019
Class Work
Continue... Day-14,
23-07-2019
Double Linked List Operations
Day-15,
Class Work
24-07-2019
Tutorial/Activity/Test Day-16,
26-07-2019
Circular Linked List Operations Day-17,
29-07-2019
Header Linked List & operation
Day-18,
Circular Header Linked List 30-07-2019
& operation
Polynomial Day-19,
Double Linked List & operation 31-07-2019
Tutorial/Activity/Test Day-20,
02-08-2019
Page 4 of 8
Course Handout for "Data Structure & Algorithms" (CS-2001), School of Computer Engineering Autumn-
2019
Sparse Matrix Day-21,
Class Work 05-08-2019
22-32 Stacks & Introduction to Stack
Day-22,
Queues Stack Application
06-08-2019
Stack Representation – Arrays
Stack Representation –
Day-23,
Linked List
07-08-2019
Stack ADT
Tutorial/Activity/Test Day-24,
09-08-2019
Arithmetic Expression Evaluation Day-25,
Class Work 13-08-2019
Arithmetic
Expression Day-26,
Conversion 14-08-2019
Class Work
Tutorial/Activity/Test Day-27,
16-08-2019
Introduction to Queues
Day-28,
Queues Application
19-08-2019
Queues Representation – Arrays
Queues Representation –
Linked List Day-29,
Queues ADT 20-08-2019
Class Work
Linear Queue Drawback Day-30,
Circular Queues 21-08-2019
Mid Semester Examination
24-31 August 2019
Deques
Day-31,
Priority Queue
04-09-2019
Class Work
Tutorial/Activity/Test Day-32,
06-09-2019
33-47 Trees Introduction to Trees
Day-33,
Trees Terminology
04-09-2019
Class Work
Tress Application
Binary Tree – Full, Complete
Day-34,
and Extended Binary Trees
10-09-2019
Expression Trees
Class Work
Representation of Binary Tree
– Linked and Array Day-35,
Representation 11-09-2019
Binary Tree ADT
Tutorial/Activity/Test Day-36,
13-09-2019
Page 5 of 8
Course Handout for "Data Structure & Algorithms" (CS-2001), School of Computer Engineering Autumn-
2019
Arithmetic expression
Day-37,
Conversion
16-09-2019
Class Work
Binary Tree Traversal
Concept and Algorithm – In-
Order, Pre- Order and Post- Day-38,
Order & Level- Order 17-09-2019
Binary Tree Construction with
different traversal
Class Work on Binary Tree
Day-39,
Threaded Binary Tree –
18-09-2019
Single and Double Threaded
Tutorial/Activity/Test Day-40,
20-09-2019
Binary Search Tree Day-41,
BST ADT – Search, insertion 23-09-2019
BST ADT – Deletion, Day-42,
Class Work 24-09-2019
Balanced Binary Tree
Day-43,
AVL Tree
25-09-2019
AVL Rotation Techniques, ADT
Tutorial/Activity/Test Day-44,
27-09-2019
Multi-way Search Tree & ADT Day-45,
B-Tree & ADT 30-09-2019
B+ Tree Introduction Day-46,
Forest 01-10-2019
Tutorial/Activity/Test Day-47,
04-10-2019
48-51 Graphs Introduction to Graph
Day-48,
Graph Terminology
14-10-2019
Graph Application
Graph Representation Day-49,
Class Work 15-10-2019
Graph Operation – DFS and BFS Day-50,
Class Work 16-10-2019
Tutorial/Activity/Test Day-51,
18-10-2019
52-55 Sorting Bubble Sort
Day-52,
Insertion Sort
21-10-2019
Selection Sort
Quick Sort Day-53,
Merge Sort 22-10-2019
Heap Sort Day-54,
Radix Sort 23-10-2019
Page 6 of 8
Course Handout for "Data Structure & Algorithms" (CS-2001), School of Computer Engineering Autumn-
2019
Tutorial/Activity/Test Day-55,
25-10-2019
56-59 Searching Linear Search Day-56,
Binary Search 28-10-2019
Hashing – Hash Function Day-57,
Class Work 29-10-2019
Hashing – Collision
Day-58,
Resolution Technique
30-10-2019
Class Work
Tutorial/Activity/Test Day-59,
01-11-2019
Revision/Doubt Clearing Day-60,
11-11-2019
Revision/Doubt Clearing Day-61,
12-11-2019
Revision/Doubt Clearing Day-62,
13-11-2019
Revision/Doubt Clearing Day-63,
15-11-2019
End Semester Examination
20-30 November 2019
Page 7 of 8
Course Handout for "Data Structure & Algorithms" (CS-2001), School of Computer Engineering Autumn-
2019
Page 8 of 8
