|
DATA STRUCTURES AND APPLICATIONS (Effective from the academic
year 2018 -2019) SEMESTER – III |
||||
|
Course Code |
18CS32 |
CIE Marks |
40 |
|
|
Number of Contact Hours/Week |
3:2:0 |
SEE Marks |
60 |
|
|
Total Number
of Contact Hours |
50 |
Exam Hours |
03 |
|
|
CREDITS –4 |
||||
|
Course Learning Objectives: This course (18CS32) will enable students to: |
||||
|
· Explain fundamentals of data structures and
their applications essential for programming/problem solving. ·
Illustrate linear
representation of data
structures: Stack, Queues, Lists, Trees and Graphs. ·
Demonstrate sorting
and searching algorithms. ·
Find suitable data structure during
application development/Problem Solving. |
||||
|
Module 1 |
Contact Hours |
|||
|
Introduction:
Data Structures,
Classifications (Primitive & Non Primitive), Data structure Operations, Review of Arrays,
Structures, Self-Referential Structures, and Unions. Pointers and Dynamic
Memory Allocation Functions. Representation
of Linear Arrays in Memory, Dynamically allocated arrays. Array Operations: Traversing, inserting, deleting, searching, and sorting. Multidimensional Arrays, Polynomials and Sparse Matrices. Strings: Basic Terminology, Storing, Operations and Pattern
Matching algorithms. Programming Examples. Textbook
1: Chapter 1: 1.2, Chapter
2: 2.2 - 2.7 Text Textbook 2: Chapter 1: 1.1 - 1.4, Chapter 3: 3.1 - 3.3, 3.5,
3.7, Ch apter 4: 4.1 - 4.9, 4.14
Reference 3: Chapter 1: 1.4 RBT: L1, L2, L3 |
10 |
|||
|
Module 2 |
|
|||
|
Stacks:
Definition, Stack
Operations, Array Representation of Stacks, Stacks using Dynamic Arrays, Stack Applications: Polish
notation, Infix to postfix conversion, evaluation of postfix expression. Recursion - Factorial, GCD, Fibonacci Sequence, Tower of Hanoi, Ackerman's
function. Queues: Definition, Array
Representation, Queue Operations, Circular Queues, Circular queues using Dynamic arrays, Dequeues, Priority Queues, A
Mazing Problem. Multiple Stacks
and Queues. Programming Examples. Textbook 1: Chapter 3: 3.1
-3.7 Textbook 2: Chapter 6: 6.1 -6.3, 6.5, 6.7-6.10, 6.12, 6.13 RBT: L1, L2, L3 |
10 |
|||
|
Module 3 |
|
|||
|
Linked
Lists: Definition,
Representation of linked lists in Memory, Memory allocation; Garbage Collection. Linked list
operations: Traversing, Searching, Insertion, and Deletion. Doubly Linked lists, Circular linked
lists, and header linked lists. Linked Stacks and Queues. Applications of Linked lists
– Polynomials, Sparse
matrix representation. Programming Examples Textbook 1: Ch apter
4: 4.1 – 4.6, 4.8, Textbook 2: Ch apter 5: 5.1 – 5.10, RBT: L1, L2, L3 |
10 |
|||
|
Module 4 |
|
|||
|
Trees: Terminology, Binary Trees,
Properties of Binary
trees, Array and linked Representation of Binary Trees,
Binary Tree Traversals - Inorder, postorder, preorder; Additional
Binary tree operations. Threaded binary trees, Binary Search Trees –
Definition, Insertion, Deletion, Traversal, Searching, Application of Trees-Evaluation of Expression, Programming Examples |
10 |
|||
|
Textbook 1: Chapter 5: 5.1 –5.5, 5.7;
Textbook 2: Chapter 7: 7.1 – 7.9 RBT:
L1, L2, L3 |
|
|
Module 5 |
|
|
Graphs:
Definitions, Terminologies, Matrix and Adjacency List Representation Of
Graphs, Elementary Graph
operations, Traversal methods: Breadth First Search
and Depth First
Search. Sorting and Searching: Insertion Sort,
Radix sort, Address Calculation Sort. Hashing: Hash Table organizations, Hashing Functions, Static
and Dynamic Hashing. Files
and Their Organization: Data
Hierarchy, File Attributes, Text Files and Binary Files, Basic
File Operations, File Organizations
and Indexing Textbook 1: Chapter 6 : 6.1 –6.2,
Chapter 7:7.2, Chapter 8 : 8.1-8.3 Textbook 2: Chapter 8 : 8.1 – 8.7,
Chapter 9 : 9.1-9.3, 9.7, 9.9 Reference 2: Chapter 16 : 16.1 - 16.7 RBT: L1, L2, L3 |
10 |
|
Course Outcomes: The student will be able to : |
|
|
·
Use different types of data structures, operations and algorithms ·
Apply searching and sorting operations on files ·
Use stack,
Queue, Lists, Trees
and Graphs in problem solving ·
Implement all data structures in a high-level language for problem solving. |
|
|
Question Paper
Pattern: |
|
|
·
The question paper will have ten questions. ·
Each full
Question consisting of 20 marks ·
There will be 2 full questions (with a maximum of four sub questions) from each module. ·
Each full question will have sub questions covering all the topics
under a module. ·
The students will have to answer 5 full questions, selecting one
full question from each
module. |
|
|
Textbooks: |
|
|
1. Ellis Horowitz and Sartaj Sahni,
Fundamentals of Data Structures in C, 2nd Ed, Universities Press, 2014. 2.
Seymour Lipschutz, Data Structures Schaum's Outlines, Revised 1st Ed, McGraw Hill,
2014. |
|
|
Reference Books: |
|
|
1. Gilberg & Forouzan, Data Structures: A
Pseudo-code approach with C, 2nd Ed, Cengage Learning,2014. 2.
Reema Thareja, Data Structures using
C, 3rd Ed, Oxford press,
2012. 3. Jean-Paul Tremblay & Paul G. Sorenson,
An Introduction to Data Structures with Applications, 2nd Ed,
McGraw Hill, 2013 4.
A M Tenenbaum, Data
Structures using C, PHI, 1989 5.
Robert Kruse,
Data Structures and
Program Design in C, 2nd Ed, PHI, 1996. |
|