Course Plan

A. Course Handout (Version 1.0)

Institute/School Name Chitkara University Institute of Engineering and Technology

Department Name Department of Computer Science & Engineering
Programme Name Bachelor of Engineering (B.E.), Computer Science & Engineering
Course Name Data Structures Session 2024-2025
Course Code 23CS004 Semester/Batch 4th/2023
L-T-P (Per Week) 2-0-4 Course Credits 04
Basic concepts of computer
Pre-requisite NHEQF Level 05
fundamentals
Course Coordinator Dr. Heena Wadhwa SDG Number 4,8,9

Understand the basics of data structure, complexity of algorithms, and the implementation
CLO01 of various operations on arrays and linked lists.
Illustrate the concepts of stack and queue with their applications and apply recursion to solve
CLO02
certain problems.
CLO03 Persuade different searching and sorting mechanisms with their comparisons.
Understand, implement, and analyze linked list and queue data structure and apply it to real-
CLO04 world problems.

CLO05 Analyze different tree traversal techniques and understand various kinds of trees.

1. Objectives of the Course

Data structures play a central role in modern computer science. Data structures are essential building blocks in
obtaining efficient algorithms. This course covers elementary data structures (Array, Binary search trees) and
algorithmic approaches to solve classical problems (sorting, graph searching). It Introduces the mathematical
modeling of computational problems, as well as common algorithms, algorithmic paradigms, and data structures
used to solve these problems.
The main objectives of the course are:
• To use object oriented programming knowledge for solving real world problem statements.
• To evaluate time-space complexity tradeoffs for all categories of algorithms.
• To understand concepts of searching and sorting techniques.
• To understand basic concepts of stacks, queues, list, and trees.
• To understand about writing algorithms and step by step approach in solving problems with the
help of fundamental data structures.

2. Course Learning Outcomes

After completion of the course, student should be able to:

Course Learning Outcome *POs **CL ***KC Sessions

Understand the basics of data PO1, PO2, PO3, K2 Factual 28

structure, complexity of algorithms, PO4, PO9, PO11, Conceptual
CLO01
and the implementation of various PO12
operations on arrays and linked lists.

Page 1 of 8
Data Structures / 23CS004
 Course Plan

CLO02 Illustrate the concepts of stack and PO1, PO2, PO3, K3 Conceptual 33
queue with their applications and PO4, PO9, PO11, Procedural
apply recursion to solve certain PO12
problems.
CLO03 Persuade different searching and PO1, PO2, PO3, K3 Conceptual 41
sorting mechanisms with their PO4, PO9, PO11, Procedural
comparisons. PO12
CLO04 Understand, implement, and analyze PO1, PO2, PO3, K4 Conceptual 28
linked list and queue data structure and PO4, PO9, PO11,
apply it to real-world problems. PO12
CLO05 Analyze different tree traversal PO1, PO2, PO3, K3 Conceptual 20
techniques and understand various PO4, PO9, PO11,
kinds of trees. PO12
Total Contact Hours 150

Revised Bloom’s Taxonomy Terminology

* PO’s available at (shorturl.at/cryzF)
**Cognitive Level =CL
***Knowledge Categories = KC

Course PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
Learning
Outcomes

CLO01 H H H M L L H

CLO02 H H H M L L H

CLO03 H H H H M M H

CLO04 H H H H M H M H

CLO05 H H H H M H M H
H=High, M=Medium, L=Low

3. ERISE Grid Mapping

Feature Enablement Level (1-5, 5 being highest)

Entrepreneurship 2

Research 4

Innovation 3

Skills 5

Employability 5

4. Recommended Books:
Text Books
B01: Data Structures and Algorithms in Java, Robert Lafore, Sams Publishing, 2nd edition, 2002

Page 2 of 8
Data Structures / 23CS004
 Course Plan

B02: Data structures and algorithms in Java. John, Goodrich MT, Tamassia R, Goldwasser MH, wiley 2014
Reference Books
B03: Introduction to Algorithms by Thomas H. Cormen, The MIT Pressman 3rd Edition, 2001
B04: The textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, Pearson Education, Inc.,
2011
E-Resources:
https://library.chitkara.edu.in/subscribed-books.php

5. Other readings and relevant websites:

Serial Link of Journals, Magazines, websites and Research Papers

No
1. https://nptel.ac.in/courses/106/102/106102064/
2. https://algs4.cs.princeton.edu/home/
3. https://cse.iitkgp.ac.in/~dsamanta/joywithjava/data/slides/Chapter9.pdf
4. https://onlinecourses.nptel.ac.in/noc22_cs92/preview

6. Recommended Tools and Platforms

Testpad, Apache NetBeans, Visual Studio

7. Course Plan:

Lecture Number Topics Text Book

1-2 Data Structures and Algorithms: Importance in programming and B01-Chapter-01
real-world applications, Elementary Data Organization, Data
Structure Types and Operations Types: Linear vs Non-linear,
Static vs Dynamic.
3-4 Algorithm: Complexity Analysis, Time vs Space trade-offs, B01-Chapter-02
Asymptotic Notations for Complexity( Ω, ω ,θ, O, o) Analysis,
Operation counting, Iterative approach, Master theorem
5-6 Practice Problems for complexity computation B01-Chapter-02
7-8 Array: Introduction, Representation of Linear Arrays in Memory, B01-Chapter-02
Traversing Linear Arrays, Insertion and Deletion in arrays.
Processing Multi-Dimensional Arrays as Collection of 1-D arrays
Applications in databases, caching, and matrix operations.
Recursion and its applications
9-10 Searching: Linear and Binary Search with their Complexity Analysis B02-Chapter10
ST-01
11-12 Sorting techniques: Selection Sort, Insertion Sort, Quick Sort, B01-Chapter-03,
Merge Sort. B04-Chapter-02
13-15 Linked List: Introduction & its memory representation, traversing B01-Chapter-04
a Linked List, Insertion into Linked List (sorted and unsorted
Linked List), Deleting elements from Linked List,
Operations on Doubly Linked List, Circular linked List & its
applications
16-18 Stacks: Array representation of Stacks, implementation of stack B01-Chapter-05
using linked list.
19-21 Applications of Stack: Application in undo operations, Arithmetic B01-Chapter-04,05
Expressions, Polish Notation, Transforming Infix Expressions into B03-Chapter-05
Postfix Expressions, Implementations of recursive and non-
recursive procedures by Stacks
ST-02

Page 3 of 8
Data Structures / 23CS004
 Course Plan

22-24 Queues: Representation as Array and Linked List B01-Chapter-04

Operations (insertion, deletion, and updation) in Queue, Practice B04-Chapter-01
Problems
25-26 Deques, Circular Queues, Priority Queues B01-Chapter-04
Operations: insertion, deletion, and updation, Practice problems B03-Chapter10
27-28 Trees: Binary trees, complete binary trees, Binary Search Trees, B01-Chapter-8,
Representing binary trees B02-Chapter10
29-30 Tree and their Implementation, Tree Traversal: preorder, In B01-Chpater-8,
order, Post order and their algorithms, Insertion, Deletion and B02-Chapter10
Searching of elements in Binary Trees, Practice Problems

End Term Examination

8. Delivery/Instructional Resources
Lecture Web References Audio-Video References
Topics
Numbers
1-2 Data Structures and Algorithms: Basic https://portal.abuad.edu.ng/l https://ocw.mit.edu/courses/6-
Terminology, Elementary Data ecturer/documents/16043931 006-introduction-to-algorithms-
Organization, Data Structures and 39CSC_207-slide1- spring-2020/resources/lecture-2-
Operations introduction_and_terminologi data-structures-and-dynamic-
es.pptx arrays/

3-4 Algorithm : Complexity, Time and https://ocw.mit.edu/courses/1- https://ocw.mit.edu/courses/6-006-

Space & Complexity, Asymptotic 204-computer-algorithms-in- introduction-to-algorithms-spring-
Notations for Complexity( Ω, ω ,θ, O, systems-engineering-spring- 2020/resources/lecture-1-
o) 2010/8ee75d49f1cb9a947f1d3f algorithms-and-computation/
15a2aa9e00_MIT1_204S10_lec
05.pdf
5-6 Practice Problems for complexity https://cse.mait.ac.in/pdf/LAB https://www.codechef.com/blogs/d
computation %20MANUAL/DS.pdf ata-structures-in-java

7-8 Array: Introduction, Representation https://home.csulb.edu/~hill/e https://ocw.mit.edu/courses/6-006-

of Linear Arrays in Memory, e444/Lectures%20- introduction-to-algorithms-spring-
Traversing Linear Arrays, Insertion %20Deprecated/04%20C++%20 2020/resources/lecture-2-data-
and Deletion in arrays. Arrays%20Arduino.pdf structures-and-dynamic-arrays/

9-10 Searching: Linear and Binary Search https://courses.cs.washington. https://www.youtube.com/watch?

with their Complexity. edu/courses/cse143/12wi/lectu v=k4xVQhMERuQ
res/01-13/05-binarysearch-
complexity.pdf

11-12 Sorting techniques: Selection Sort, https://ocw.mit.edu/courses/6- https://ocw.mit.edu/courses/6-

Insertion Sort, Quick Sort, Merge 0001-introduction-to- 006-introduction-to-algorithms-
Sort. computer-science-and- spring-2020/resources/lecture-5-
programming-in-python-fall- linear-sorting/
2016/resources/mit6_0001f16_
lec12/

Page 4 of 8
Data Structures / 23CS004
 Course Plan

13-15 Linked List: Introduction & its https://web.stanford.edu/clas https://www.youtube.com/watch

memory representation, traversing s/archive/cs/cs106b/cs106b.1 ?v=6wXZ_m3SbEs
a Linked List, Insertion into Linked 188/lectures/Lecture16/Lectu
List (sorted and unsorted Linked re16.pdf
List), Deleting from Linked List
16-18 Stacks: Array representation of https://web.stanford.edu/clas https://www.youtube.com/watch
Stacks, implementation of stack s/archive/cs/cs106b/cs106b.1 ?v=08QSylWv6jM
using linked list. 186/lectures/05-
19-21 Stacks_Queues/5-
Applications of Stack: Application in https://web.stanford.edu/clas https://www.youtube.com/watch
undo operations, Arithmetic Stacks_Queues.pdf
s/archive/cs/cs106b/cs106b.1 ?v=XkLfiA7Xbks
Expressions, Polish Notation, 186/lectures/05-
Transforming Infix Expressions into Stacks_Queues/5-
Postfix Expressions, Stacks_Queues.pdf
Implementations of recursive and
non-recursive procedures by Stacks
22-24 Queues: Representation as Array and https://web.stanford.edu/clas https://www.youtube.com/watch?
Linked List Operations (insertion, s/archive/cs/cs106b/cs106b.1 v=XkLfiA7Xbks
deletion, and updation) in Queue, 186/lectures/05-
Practice Problems Stacks_Queues/5-
Stacks_Queues.pdf
25-26 Deques, Circular Queues, Priority https://web.eecs.utk.edu/~bv https://www.youtube.com/watch?
Queues Operations: insertion, anderz/teaching/cs140Fa10/n v=2zQtymZV6dk
deletion, and updation, Practice otes/Queues/
problems
27-28 Trees: Binary trees, complete binary https://ocw.mit.edu/courses/ https://ocw.mit.edu/courses/6-
trees, Binary Search Trees, 6-006-introduction-to- 851-advanced-data-structures-
Representing binary trees algorithms-spring- spring-2012/resources/session-15-
2020/resources/mit6_006s20 static-trees/
_lec6/
29-30 Tree and their Implementation, Tree http://webdocs.cs.ualberta.ca https://ocw.mit.edu/courses/6-
Traversal: preorder, In order, Post /~holte/T26/tree- 006-introduction-to-algorithms-
order and their algorithms, Insertion, traversal.html spring-2020/resources/lecture-6-
Deletion and Searching of elements in binary-trees-part-1/
Binary Trees, Practice Problems

9. Lab Plan
Sr. Lab Experiments Learning Resource
No. Number
Introduction of Data structures and https://www.tutorialspoint.com/dsa_using_java
1 1-4 Algorithms: Operations of Data Structures /dsa_using_java_algorithms.htm

Algorithm Complexity and Complexity https://blog.geekster.in/time-complexity-in-

Computation java/
5-9
2. Calculate Time and Space complexity of
algorithms
3. Calculate the worst case, best case and https://www.geeksforgeeks.org/analysis-
10-20 average for each algorithm. algorithms-big-o-analysis/

Page 5 of 8
Data Structures / 23CS004
 Course Plan

Describe each algorithm’s overall

performance using the possible class in Big‐𝑂
notation.
https://www.geeksforgeeks.org/arrays-in-java/
21-28 Representation of Linear array in memory
4.
https://www.geeksforgeeks.org/java-program-
5. 29-35 Implement sparse matrix using array. to-determine-if-a-given-matrix-is-a-sparse-
matrix/
Perform Linear Search and Binary Search on https://www.tutorialspoint.com/dsa_using_java
an array. /dsa_using_java_array.htm
Search the element by passing the array to a
36-42
6. function and then returning the position of
the element from the function

Sorting techniques: Selection Sort, Insertion https://www.geeksforgeeks.org/sorting-

Sort, Quick Sort, Merge Sort. algorithms/

Implementation of selection sort

43-57
7. Implementation of Insertion sort
Implementation of Quick sort
Implementation of Merge sort

Create a linked list with nodes having https://www.geeksforgeeks.org/student-record-

information about a student and perform management-system-using-linked-list/

Insert a new node at specified position.

8. 58-63
Delete of a node with the roll number of
student specified.

Reversal of that linked list

Create a stack and perform Pop, Push, https://www.geeksforgeeks.org/implement-a-
9. 64-71 Traverse operations on the stack using Linear stack-using-singly-linked-list/
Linked list
Implement insertion, deletion and display https://www.geeksforgeeks.org/binary-search-
10. 72-80 (inorder, preorder and postorder) on binary tree-traversal-inorder-preorder-post-order/
search tree
The enqueue operation can be used to add https://www.geeksforgeeks.org/queue-
the element to the rear of the queue. implementation-using-linked-list-in-java/

81-102
11. The dequeue operation can be used to
removes the element from the front of the
queues
Create a Binary Tree https://www.geeksforgeeks.org/tree-traversals-
inorder-preorder-and-postorder/
102-112 Perform Tree traversals (Preorder,
12. Postorder, Inorder)

Page 6 of 8
Data Structures / 23CS004
 Course Plan

https://codingzap.com/binary-search-tree-java/
Insertion, Deletion and Searching of element
13. 113-120
in Binary Tree

10. Action plan for different types of learners

Slow Learners Average Learners Fast Learners

 Remedial Classes on Saturdays  Workshops  Engaging students to hold hands of
 Encouragement for improvement  Formative Exercises used slow learners by creating a Peer
using Peer Tutoring to highlight concepts and Tutoring Group
 Use of Audio and Visual Materials notions  Design solutions for complex
 Use of Real-Life Examples  E-notes and E-exercises to problems
read ahead of the pedagogic  Design solutions for
material. complex problems
 Presentation on topics beyond
those covered in CHO

11. Evaluation Scheme & Components:

Evaluation No. of Weightage of Mode of
Type of Component
Component Assessments Component Assessment

Testpad module progress and

Component 1 - 10% Online
completion
Component 2 Sessional Test 03* 40% Online

Component 3 End Term Examinations 01** 50% Online

Total 100%
*Students will have to appear in all Sessional Tests.
*Makeup Examination will compensate for either ST-1 or ST-2 (Only for genuine cases, based on the Dean’s approval).
**As per Academic Guidelines, a minimum of 75% attendance is required to become eligible for appearing in the End Semester
Examination.

12. Syllabus of the Course:

Subject: Data Structures / 22CS004

No. of
S. No. Topic (s) Weightage %
Sessions
1 Data Structures and Algorithms: Importance in
programming and real-world applications, Elementary Data
Organization, Data Structure Types and Operations
Types: Linear vs Non-linear, Static vs Dynamic.
Algorithm : Complexity Analysis, Time vs Space trade-offs,
Asymptotic Notations for Complexity( Ω, ω ,θ, O, o) Analysis, 52 34%
Operation counting, Iterative approach, Master theorem
Practice Problems for complexity computation
Array: Introduction, Representation of Linear Arrays in
Memory, Traversing Linear Arrays, Insertion and Deletion in
arrays.

Page 7 of 8
Data Structures / 23CS004
 Course Plan

Processing Multi-Dimensional Arrays as Collection of 1-D

arrays
Applications in databases, caching, and matrix operations.
Recursion and its applications
Searching: Linear and Binary Search with their Complexity
Analysis

ST-1 (Covering 30% syllabus)

2. Sorting techniques: Selection Sort, Insertion Sort, Quick
Sort, Merge Sort.

Linked List: Introduction & its memory representation,

traversing a Linked List, Insertion into Linked List (sorted and
unsorted Linked List), Deleting elements from Linked List,
Operations on Doubly Linked List, Circular linked List & its
applications
Stacks: Array representation of Stacks, implementation of 99 66%
stack using linked list.
Applications of Stack: Application in undo operations,
Arithmetic Expressions, Polish Notation, Transforming Infix
Expressions into Postfix Expressions, Implementations of
recursive and non-recursive procedures by Stacks
Queues: Representation as Array and Linked List
Operations (insertion, deletion, and updation) in Queue,
Practice Problems.
ST-2 (Covering 60% syllabus)
3. Deques, Circular Queues, Priority Queues
Operations: insertion, deletion, and updation, Practice
problems
Trees: Binary trees, complete binary trees, Binary Search
Trees, Representing binary trees 150 100%
Tree and their Implementation, Tree Traversal: preorder, In
order, Post order and their algorithms, Insertion, Deletion
and Searching of elements in Binary Trees, Practice
Problems
Sessional Test-3 (Project Based Evaluation)
End Term 100% syllabus

This Document is approved by:

Designation Name Signature

Course Coordinator Dr. Heena Wadhwa
Head-Academic Delivery Dr. Mrinal Paliwal
Dean Dr. Rishu Chhabra
Date 29.11.2024

Page 8 of 8
Data Structures / 23CS004