Scribd
Upload
18 views

Data Structures

Uploaded by

Ilesh Shah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views

Data Structures

Uploaded by

Ilesh Shah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Banasthali Vidyapith-Faculty of Mathematics & Computing

Course Handout: B. Tech.–III Semester (CS)


July - December 2023
Date: 30-June-2023
Course Code: CS 209 Course Name: Data Structures
Credit Points: 4 Max. Marks: 100 (CA: 40 ESA: 60)
Course Instructors: Dr. S. K Sharma, Professor, Computer Science – (Section-A&B)
Dr. Neelam Sharma, Associate Professor, Computer Science – (Section-C)

Learning Outcomes:
After successful completion of the course, students will be able to:
• Develop knowledge of basic data structures for storage and retrieval of ordered or unordered data. Data
structures include arrays, linked lists, stacks, queues, binary trees, heaps.
• Develop knowledge of applications of data structures including the ability to implement algorithms for the
creation, insertion, deletion, searching, and sorting of each data structure.
• Analyze and compare algorithms for efficiency using Big-O notation.
• Describe the concept of dynamic memory management, data types, algorithms, Big O notation.
• Apply Algorithm for solving problems like sorting, searching, insertion and deletion of data.

Syllabus:
Section A
Concept of data types, Abstract data type, Data structures, running time of a program, asymptotic notations:
Big-Oh, Theta, Little-oh, Omega. Linear data structures: Static implementation of stack, queue, and their
applications Searching and Sorting: Linear search and Binary Search, Bubble sort, Selection sort, Insertion
sort, Quick sort, Radix sort.
Section B
Linked List: Linear, doubly or two way, circular, header and various operations; Representation of
polynomial using linked list, addition and subtraction of polynomials. Dynamic implementation of stacks
and queues. Dynamic memory management: fixed and variable block storage, storage techniques: first-fit,
best-fit, worst-fit, next-fit; data compaction, and garbage collection.
Section C
Nonlinear data structures: Tree concepts, General Tree, binary tree and types, binary search tree,
implementation of various operations on Binary Search Tree (tree traversal, searching, insertion and
deletion, counting leaf and non-leaf nodes, height), Heap and heap sort, Balanced tree: concepts, rotations,
insertion and deletion.
Suggested Readings:
S1. Langsam, Y., Augenstein, M., Tenenbaum, A. M. (1996), Data Structures using C and C++, New
Jersey: Prentice Hall.
S2. Tremblay, J. P., Sorenson, P. G. (1976), An introduction to data structures with applications, New
York: McGraw-Hill.
S3. Horowitz, E., Sahni, S., & Anderson-Freed, S. (2008), Fundamentals of data structures in C,
Universities Press: Computer Science.
S4. Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1983), Data Structures and algorithms, Addison Wesley
Publishing Company.

Suggested E-Learning Material:


E1 : Programming and Data Structures https://swayam.gov.in/course/1407-programming-and-data-
structures
E2 : Data Structures and Program Methodology https://nptel.ac.in/courses/10610
Evaluation Scheme:

Component Marks Submission/ Allotment/ Syllabus


Examination Date(s)
Home Assignment I 10 28 August 2023 Topics shall be allotted in the class
by 12 August, 2023
Periodical Test I 10 8-11 September, 2023* Syllabus completed till date
Home Assignment II 10 11 October, 2023 Topics shall be allotted in the class
by 25 September, 2023
Periodical Test II 10 4-8 November, 2023* Syllabus completed till date
Semester Examination 60 2-18 December, 2023* Entire Syllabus
*Subject to change

Lecture-Wise Plan:

Suggested
Lecture No. Topics to be covered
Readings
1 Introduction to Data types, Data structures, Abstract data type S1
Review of Array based problems, Pointers with arrays, strings, Structures,
2-5 S1, E2
functions
6-9 Sorting and Searching – Binary and Linear search, Bubble, Insertion, Selection. S1
Running time of program (time complexity), asymptotic notations: Big-Oh,
10-11 S1
Theta, Little-oh, Omega
Static implementation of Stack, Applications of stack in recursion, expressions
12-16 S1, S4
conversion (infix, prefix and postfix), expression evaluation.
Queue (simple, circular), static representation of queue and its implementation
17-22 (insertion, deletion), Various types of queue (priority, d-queue) and its S1, S4
applications, Radix and Quick sort,
Linear linked list, and operations (insertion, deletion, searching, reverse,
23-27 merging, traversals etc.), Circular and Header linked list, Polynomial S1, S4
representation and operations (addition, subtraction) using linked list.
28-31 Dynamic Implementation of stack and queue using linked list S1,E1
Dynamic memory management: fixed and variable block storage, Storage
32-34 techniques: first-fit, best-fit, next-fit, worst-fit, Data compaction and garbage S1,E2
collection
Tree concepts, general tree, binary tree and types, Binary Search Tree (BST)
35-38 S1
and its representations.
Implementation of BST and its operations (insertion, deletion, searching,
39-43 traversals, counting leaf and non-leaf nodes, and height). S1, S4
Conversions of general trees to binary trees.
44-47 Heap and Heap sort. S1,E1
48-50 Balance Tree(AVL Tree) Concepts, Rotations, Insertion and Deletion S1,E1

Dr. S. K. Sharma
Dr. Neelam Sharma

You might also like