PCTE Institute of Engineering and Technology

COURSE: B.Tech CSE

SUBJECT NAME: Data Structures
SUBJECT CODE: BTCS-301-18
SEMESTER: 3rd
CREDIT:3
COURSE INSTRUCTOR: Arti Lakhanpal Malhotra

EMAIL ADDRESS : [email protected]

Faculty of Computer Science and Engineering Page 1

 PCTE Institute of Engineering and Technology

OVERALL COURSE OBJECTIVE

 The application & usage of different data structures – Array, Linked list, Stacks & Queues, Trees.
 To make students aware about the searching and sorting methods used in computers to manage the data.
 The students need exposure about writing algorithms which eventually help them in practical implementation as well as in industry.

PREREQUISITES

 Knowledge of programming language : C or C++.

 Students must know how to execute code using any IDE(Integrated Development Environment).
 Student must analytically go through the problem and then solve.

COURSE OUTCOME

COURSE OUTCOMES
CO1 Apply appropriate constructs of Programming language, coding standards for application development
CO2 Use appropriate data structures for problem solving and programming
CO3 Use algorithmic foundations for solving problems and programming
CO4 Apply appropriate searching and/or sorting techniques for application development.
CO5 Develop programming logic and skills.

Faculty of Computer Science and Engineering Page 2

 PCTE Institute of Engineering and Technology

SYLLABUS

Module 1:

Introduction Basic Terminologies: Elementary Data Organizations, Data Structure Operations: insertion, deletion, traversal etc.; Analysis of an
Algorithm, Asymptotic Notations, Time-Space trade off. Searching: Linear Search and Binary Search Techniques and their complexity analysis.

Module 2:

Stacks and Queues ADT Stack and its operations: Algorithms and their complexity analysis, Applications of Stacks: Expression Conversion and
evaluation – corresponding algorithms and complexity analysis. ADT queue, Types of Queue: Simple Queue, Circular Queue, Priority Queue;
Operations on each types of Queues: Algorithms and their analysis.

Module 3:

Linked Lists Singly linked lists: Representation in memory, Algorithms of several operations: Traversing, Searching, Insertion into, Deletion
from linked list; Linked representation of Stack and Queue, Header nodes, Doubly linked list: operations on it and algorithmic analysis; Circular
Linked Lists: All operations their algorithms and the complexity analysis. Trees: Basic Tree Terminologies, Different types of Trees: Binary
Tree, Threaded Binary Tree, Binary Search Tree, AVL Tree; Tree operations on each of the trees and their algorithms with complexity analysis.
Applications of Binary Trees. B Tree, B+ Tree: definitions, algorithms and analysis.

Module 4:

Sorting and Hashing Objective and properties of different sorting algorithms: Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge
Sort, Heap Sort; Performance and Comparison among all the methods, Hashing.

Module 5:

Graph Basic Terminologies and Representations, Graph search and traversal algorithms and complexity analysis.

Faculty of Computer Science and Engineering Page 3

 PCTE Institute of Engineering and Technology

REFERENCE BOOKS

1. Data Structure, Lipschutz Seymour, Second Edition, TMH

2. Algorithm + Data Structures = Programs, Niclaus Wirth, Prentice Hall
3. Data Structures, Tanenbaum, Paperback Edition
4. An Introduction to Data Structures Applications, Trembley&Soreson, Second Edition
5. Data Structures, R.S.Salaria, Second Edition

EVALUATION CRITERIA

Total Internal Weightage: 40 Marks Total External Weightage: 60 Marks

The bifurcation of Internal Weightage of 40 Marks is given below:-

PARAMETER Weightage in internals

Mid Semester Examination 1

24
Mid Semester Examination 2
Class Test/Task 5
Presentation 5
Attendance 6
Total 40

Faculty of Computer Science and Engineering Page 4

 PCTE Institute of Engineering and Technology

Rules for the class

1. It is compulsory for all the students to have 75% attendance in each subject at the end of the semester failing which the student will not be
allowed to write the final exam.

PRESENTATION DETAILS

 Students will deliver this presentation by doing research on the Online System or software or any application chosen by them.
 They must discuss about the
1. Minimum 2 features of the chosen software/application
2. Analyse data structure that can be used for the chosen 2 feature (Array, Linked list, Stack, Queues, Trees etc) as well as any 2
operations in the allocated topic.
3. Design an algorithm in simple English language to implement any one feature.
 Software/App or online system can be :

1 Alibaba
2 Amazon
3 Any game
4 Applock
5 Aarogya setu
6 Bank bazaar
7 Big basket
8 Bitmoji
9 Book my show
10 Car dekho
11 Carwala
Faculty of Computer Science and Engineering Page 5
 PCTE Institute of Engineering and Technology

12 Coupon dunia
13 Cricbuzz
14 Crickinfo
15 Digilocker
16 Ebay
17 Facebook
18 Facebook Messenger
19 First cry
20 Flipkart
21 Food panda
22 Gmail
23 Goibibo
24 Google Pay
25 Groffers
26 Groupon
27 Housing.com
28 Hotstar
29 Instagram
30 IRCTC
31 Magic Bricks
32 Make my Trip
33 Mobikwik
34 Myntra
35 My jio
36 Ola
37 Olx
38 Paypal
39 Paytm
40 Phone pay

Faculty of Computer Science and Engineering Page 6

 PCTE Institute of Engineering and Technology

41 Photo-circle
42 Policy bazaar
43 Rapido
44 Red bricks
45 Sharechat
46 Snapchat
47 Speedtest
48 Swiggy
49 Tiktok
50 Times of India app
51 Truecaller
52 Twitter
53 Uber
54 Uber eats
55 Urbanclap
56 Whatsapp
57 Yahoo mail
58 Youtube
59 Zomato
60 99 acres

Guidelines for Presentation:

Faculty of Computer Science and Engineering Page 7

 PCTE Institute of Engineering and Technology

Presentation will be held during the semester about which you will be informed well in advance. The rules for
presentation are :

Evaluation Criteria for Presentations:

Max. Marks: 20
Break-up of marks will be as follows:
 Synopsis: 3 Marks
 Presentation Skills: 6 Marks
 Content: 6 Marks
 Query handling: 5 Marks

• Bibliography is a must.
• PPT is compulsory for the presentation
• The standard template is to be followed for both the synopsis and the PPTs which is available on IMS.
• Out of all the presentations of a class, one presentation should be a group presentation and one presentation should be
without any aid.
• Students must be dressed formally on the day of the presentation. No student should be allowed to deliver the
presentation in informal dress.
• Sequence of presentation will be completely random.

Faculty of Computer Science and Engineering Page 8

 PCTE Institute of Engineering and Technology

• If a student is absent when his name is called out, he/she will be awarded Reappear.
• A total of 6 sessions will be held during one and half days of each presentation. It is mandatory for each student to
attend at least 5 sessions failing which he/she will be evaluated out of 50% marks only.
• In case of small classes where presentation is concluded in one day only, it is mandatory for each student to attend
atleast 3 sessions out of 4.

Faculty of Computer Science and Engineering Page 9

 PCTE Institute of Engineering and Technology

Session Timings for Presentations:

• 9.00 AM – 11.00 AM
• 11.30 AM- 1.30 PM
• 2.30 PM- 4.40 PM
• Attendance will be marked within the first five minutes of start of each session. Fourth attendance will be taken after
the last presentation of the day.

Evaluation of the presentation would be done out of 50% marks if:

• Student failed to deliver the presentation on the scheduled date when his/her name was announced due to any of the
following reasons:
a) Student is registered but absent(even for medical reasons)
b) Student is not in the strict formals
c) Student’s attendance is less than 5 out of 6 sessions.
d) Student has got a repeat as his/her content ( & research) was not upto the mark.

Faculty of Computer Science and Engineering Page 10

 PCTE Institute of Engineering and Technology

 Present will be marked only for those students who will be present at all the times during which the attendance will be taken.
 It is COMPULSORY for all the students to deliver the Presentation in order to clear the Internals of that subject.
 The students will get attendance according to the number of sessions attended by that student.

COURSE PLAN

Subject: Data Structures Code: BTCS-301-18

Class: B.Tech CSE Semester:3

No. of Lect.: 44 Credit: 3

Name of Instructor: ALM

Keeping in view the University norms, the whole syllabus will be discussed as per the below schedule. The schedule can be
revised as per the delivery of lectures and same will be conveyed to the students before hand.

Lecture No. Topic To be covered Sub Topics to be covered under the topic

1. Introduction to the subject

1 Introduction to Data Structures 2. What is a Data Structure
3. Why data needs to be Structured
2 Problem Analysis 1. Discussion about data, information, algorithms and
flowcharts with examples.Requirement Gathering (Getting

Faculty of Computer Science and Engineering Page 11

 PCTE Institute of Engineering and Technology

the problem and scope)

2. Analyzing the problem (Remove Incompleteness,
Algorithm Complexity Inconsistencies etc.)
3. Complex and simple algorithms, how to measure
Complexity?
1. Tell the students that we can calculate Complexity using 3
Big O Notation notations- Big O, Theta and Omega (best, worst and average
case)
3,4
Time Space Trade off 2. Detail of Big O notation.
3. What is Trade Off
4. Time and Space Tradeoff in Computer
1. Classification of Data Structures- Linear and Non Linear
2. Explain each type falling under above category (Linear-
5 Types of Data Structures
arrays, linked lists, stacks, queues etc. and Non Linear -
Trees, graphs etc.)
1. Definition of Array
2. Memory Representation
6 Arrays 3. Specific Terminology- index, length etc.
4. Operations possible on Arrays
5. Traversing an Array
6. Insertion operation on array (Insertion in the beginning, at
7 Arrays
the end and at Kth Location)
8 Arrays 7. Deletion operation on array (Delete the first element,
Faculty of Computer Science and Engineering Page 12
 PCTE Institute of Engineering and Technology

Delete the last element, Delete the element at Kth location)

9 Arrays One dimensional array and Multi Dimensional Array
Function Prototype, Function calling and Function definition,
10 Function
Recursion
Steps of Algorithm, Advantages and Disadvantages of
11 Linear search algorithm, Practice using numerical problems

Steps of Algorithm, Advantages and Disadvantages of

12 Binary Search algorithm, Practice using numerical problems

Introduction to pointers, Pointer to Structure, Programs based

13 Pointers
on array and pointer
14 Strings Introduction to Strings, Library function of Strings
1. Representation using arrays and list
2. Advantages and Uses
3. Operations on Stacks and Queues (PUSH and POP on
15 Stacks
Stack, INSERT and DELETE on QUEUE)
4. OVERFLOW and UNDERFLOW conditions, and how to
deal with them.
16 Stacks Algorithms of Operations on Stacks
1. Expression Evaluation using Stack
17,18 Stacks
2. Polish Notation Using Stack

Faculty of Computer Science and Engineering Page 13

 PCTE Institute of Engineering and Technology

19,20 Introduction, its representation, Queue Implementation

Queue

21 Queue Operations of Queue

Circular Queue, De-queue and Priority Queue, their
22 Queue
advantages
1. Introduction
2. Terminology of Linked lists - Head, Pointer, data, etc.
3. Types of Linked Lists- Single Linked lists, Doubly Linked
23 Linked Lists
lists, Circular Linked lists, Header Linked lists with
FIGURES
4. Advantages and Disadvantages of various types of LL.
1. Inserting the node at the beginning
24 Insertion Operations on LL 2. Inserting the node at the end
3. Inserting the node after a given Element
25 Insertion Operations on LL Continue with the subtopics of Lecture 24
1. Deleting the node at the beginning
26 Deletion operations on LL 2. Deleting the node at the end
3. Deleting the node after a given Element
27 Deletion operations on LL Continue with the subtopics of Lecture 26
Dynamic Storage management
28 Additional Topics of LL
Garbage Collection
29 Trees 1. Definition

Faculty of Computer Science and Engineering Page 14

 PCTE Institute of Engineering and Technology

2. Terminology- Root, edge, leaf node, parent node,

ancestors, descendents, branches, height of tree etc.
Binary Tree
Binary Search Tree
Full Binary Tree
30 Types of Trees
Complete Binary Tree
Extended Binary Tree
Heap
Inorder
31, 32 Binary Tree Traversals Preorder
Postorder
33 Application of Trees Applications
34 Graphs Introduction, Representation to Graphs
Shortest Path Algorithms
35, 36 Graphs Traversal
Breadth First and Depth First Search Algorithm
1. Definition of Sorting and searching
2. Uses of Sorting & Searching in daily Life
37 Sorting and Searching
3. Techniques of Sorting and searching
4. Complexity of Sorting and Searching Algorithms
Steps of Algorithm, Advantages and Disadvantages of
38 Quick Sort algorithm, Practice using numerical problems

Faculty of Computer Science and Engineering Page 15

 PCTE Institute of Engineering and Technology

Steps of Algorithm, Advantages and Disadvantages of

algorithm, Practice using numerical problems
Bubble Sort

39
Steps of Algorithm, Advantages and Disadvantages of
algorithm, Practice using numerical problems
Selection Sort

Steps of Algorithm, Advantages and Disadvantages of

algorithm, Practice using numerical problems
40 Merge Sort

Introduction to Hashing, Hash Function, Types of Hash

41
Hashing Function
42,43 Collision, Collision Resolution technique, Perfect Hashing
44 Spill Over and Discussion of Previous Year Question papers

GUEST LECTURE

Faculty of Computer Science and Engineering Page 16

 PCTE Institute of Engineering and Technology

Resource Person : Ms Himanshi

Company name : Solitaire Infosys

Topic : How Graph is a crucial Data structure

Faculty of Computer Science and Engineering Page 17