About the course Data Structures CST 201 KTU

 CST 201 DATA STRUCTURES 

CATEGORY      L  T P    CREDIT     YEAR OF INTRODUCTION 

PCC                   3   1 0         4                     2019

Preamble: This course aims at moulding the learner to understand the various data structures, their organization and operations. The course helps the learners to assess the applicability of different data structures and associated algorithms for solving real world problem which requires to compare and select appropriate data structures to solve the problem efficiently. This course introduces abstract concepts for data organization and manipulation using data structures such as stacks, queues, linked lists, binary trees, heaps and graphs for designing their own data structures to solve practical application problems in various fields of Computer Science. 

Prerequisite: Topics covered under the course Programming in C (EST 102)

Course Outcomes

CO1 Design an algorithm for a computational task and calculate the time/space complexities of that algorithm (Cognitive Knowledge Level: Apply) 

CO2 Identify the suitable data structure (array or linked list) to represent a data item required to be processed to solve a given computational problem and write an algorithm to find the solution of the computational problem (Cognitive Knowledge Level: Apply) 

CO3 Write an algorithm to find the solution of a computational problem by selecting an appropriate data structure (binary tree/graph) to represent a data item to be processed (Cognitive Knowledge Level: Apply) 

CO4 Store a given dataset using an appropriate Hash Function to enable efficient access of data in the given set (Cognitive Knowledge Level: Apply) 

CO5 Select appropriate sorting algorithms to be used in specific circumstances (Cognitive Knowledge Level: Analyze) 

CO6 Design and implement Data Structures for solving real world problems efficiently (Cognitive Knowledge Level: Apply)

Assessment Pattern

Bloom’s Category        Continuous Assessment Tests                    End Semester 

                                    Test1 (Percentage) Test2 (Percentage)         Examination Marks 

Remember                             30                    30                                 30 

Understand                            30                    30                                 30 

Apply                                    40                    40                                 40

Internal Examination Pattern: Each of the two internal examinations has to be conducted out of 50 marks 

First Internal Examination shall be preferably conducted after completing the first half of the syllabus and the Second Internal Examination shall be preferably conducted after completing remaining part of the syllabus. There will be two parts: Part A and Part B. Part A contains 5 questions (preferably, 2 questions each from the completed modules and 1 question from the partly covered module), having 3 marks for each question adding up to 15 marks for part A. Students should answer all questions from Part A. Part B contains 7 questions (preferably, 3 questions each from the completed modules and 1 question from the partly covered module), each with 7 marks. Out of the 7 questions in Part B, a student should answer any 5. 

End Semester Examination Pattern: There will be two parts; Part A and Part B. Part A contains 10 questions with 2 questions from each module, having 3 marks for each question. Students should answer all questions. Part B contains 2 questions from each module of which a student should answer any one. Each question can have maximum 2 sub-divisions and carries 14 marks.

Teaching Plan

Module 1 :Basic Concepts of Data Structures (5 hours)

1.1 System Life Cycle, 1 hour

1.2 Algorithms , Performance Analysis 1 hour

1.3 Space Complexity, Time Complexity 1 hour

1.4 Asymptotic Notation (Big O Notation) 1 hour

1.5 Complexity Calculation of Simple Algorithms 1hour

Module 2 :Arrays and Searching (10 hours)

2.1 Polynomial representation using Arrays 1 hour

2.2 Sparse matrix (Lecture 1) 1 hour

2.3 Sparse matrix (Lecture 2) 1 hour

2.4 Stacks 1 hour

2.5 Queues, Circular Queues 1 hour

2.6 Priority Queues, 1 hour

2.7 Double Ended Queues, 1 hour

2.8 Conversion and Evaluation of Expressions (Lecture 1) 1 hour

2.9 Conversion and Evaluation of Expressions (Lecture 2) 1 hour

2.10 Linear Search and Binary Search 1 hour

Module 3 : Linked List and Memory Management (12 hours)

3.1 Self Referential Structures 1 hour

3.2 Dynamic Memory Allocation 1 hour

3.3 Singly Linked List-Operations on Linked List, 1 hour

3.4 Doubly Linked List 1 hour

3.5 Circular Linked List 1 hour

3.6 Stacks using Linked List 1 hour

3.7 Queues using Linked List 1 hour

3.8 Polynomial representation using Linked List (Lecture 1) 1 hour

3.9 Polynomial representation using Linked List (Lecture2) 1 hour

3.10 Memory de-allocation 1 hour

3.11 Memory allocation-First-fit 1 hour

3.12 Best-fit and Worst-fit allocation schemes 1hour

Module 4 :Trees and Graphs (8 hours)

4.1 Trees,Binary Trees 1hour

4.2 Tree Operations, Binary Tree Representation, 1hour

4.3 Tree Traversals 1hour

4.4 Binary Search Trees 1hour

4.5 Binary Search Tree Operations 1hour

4.6 Graphs, Representation of Graphs 1hour

4.7 Depth First Search and Breadth First Search on Graphs 1hour

4.8 Applications of Graphs 1hour

Module 5 : Sorting and Hashing (10 hours)

5.1 Sorting Techniques – Selection Sort 1hour

5.2 Insertion Sort 1hour

5.3 Quick Sort 1hour

5.4 Merge Sort 1hour

5.5 Heap Sort 1hour

5.6 Hashing- Hashing Techniques 1hour

5.7 Collision Resolution 1hour

5.8 Overflow handling 1hour

5.9 Hashing functions – Mid square and Division methods 1hour

5.10 Folding and Digit Analysis methods 1hour

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more