Data Structures CST 201 KTU Third Semester CS - Dr Binu V P

SYLLABUS  Module 1 -Basic Concepts of Data Structures  System Life Cycle, Algorithms, Performance Analysis, Space Complexity, Time Complexity, Asymptotic Notation, Complexity Calculation of Simple Algorithms Module 2 -Arrays and Searching   Polynomial representation using Arrays, Sparse matrix, Stacks, Queues-Circular Queues, Priority Queues, Double Ended Queues, Evaluation of Expressions Linear Search and Binary Search  Module 3 -Linked List and Memory Management Self Referential Structures, Dynamic Memory Allocation, Singly Linked List-Operations on Linked List. Doubly Linked List, Circular Linked List, Stacks and Queues using Linked List, Polynomial representation using Linked List Memory allocation and de-allocation-First-fit, Best-fit and Worst-fit allocation schemes  Module 4 -Trees and Graphs   Trees, Binary Trees-Tree Operations, Binary Tree Representation, Tree Traversals, Binary Search Trees- Binary Search Tree Operations Graphs, Representation of Graphs, Depth First Search a

 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 compl

 Model Question Paper QP CODE: PAGES:3 Reg No:_______________ Name:_________________ APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY THIRD SEMESTER B.TECH DEGREE EXAMINATION, MONTH & YEAR Course Code: CST 201 Course Name: DATA STRUCTURES Max.Marks:100 Duration: 3 Hours PART A Answer all Questions. Each question carries 3 Marks 1. Calculate the frequency count of the statement x = x+1; in the following code segment for (i = 0; i< n; i++) for (j = 0; j< n; j*=2) x = x + 1; 2. What is the relevance of verification in System Life Cycle? 3. Write an algorithm to insert a new element in a particular position of an array. 4. Convert the expression ((A/(B-D+E))*(F-G)*H) to postfix form. Show each step in the  conversion including the stack contents 5. Write an algorithm to count the number of occurrences of a character in a linked list (each node contains only one character) 6. Write an algorithm for best-fit method of memory allocation 7. Draw the binary tree whose sequential representatio

     

Sorting techniques are fundamental algorithms used in computer science and data processing to arrange a collection of items or data elements into a specific order. This ordered arrangement can make it easier to search for, retrieve, and analyze data efficiently. Sorting is a crucial concept in various fields, including computer science, data analysis, and database management. In this introduction, we will explore the key aspects of sorting techniques. 1. Importance of Sorting: Sorting is a fundamental operation in computer science and plays a vital role in various applications, such as: Information retrieval: Sorting helps in quickly locating specific items within a large dataset, improving search times. Data analysis: Sorted data is essential for statistical analysis, trend identification, and generating meaningful reports. Database management: Databases often rely on sorted indexes to optimize data retrieval. Algorithm design: Many advanced algorithms build upon sorting as a key

Selection Sort is a simple sorting algorithm that repeatedly selects the smallest (or largest, depending on the desired order) element from the unsorted part of the array and moves it to the beginning of the sorted part. Here's a detailed explanation of the Selection Sort algorithm along with an example: Algorithm: Selection Sort 1.Initialization: Start with the first element as the minimum (assuming it's the smallest). 2.Find the Minimum: Scan the unsorted part of the array to find the minimum element. Compare the current element with the minimum found so far. If a smaller element is found, update the minimum. 3.Swap: Once you've found the minimum element in the unsorted part, swap it with the first element in the unsorted part. 4.Repeat: Repeat steps 2 and 3 for the remaining unsorted part of the array, excluding the element that was just swapped into the sorted part. 5.Continue: Keep repeating steps 2 to 4 until the entire array is sorted. The sorted part of the array g

Insertion sort is a simple and efficient sorting algorithm that builds the final sorted array one item at a time. It's an in-place sorting algorithm, which means it doesn't require additional memory for sorting. Here's a detailed algorithm for insertion sort, along with an example: Algorithm: Insertion Sort Start with the second element (index 1) in the array. This is the key element to be inserted into the sorted portion of the array. Compare the key element with the element(s) to its left in the sorted portion of the array. Move elements greater than the key element one position to the right until you find an element that is less than or equal to the key element, or until you reach the beginning of the array. Insert the key element into the position where you stopped moving elements in step 3. Repeat steps 1-4 for each element in the array, moving from left to right. The array is now sorted. Example We'll perform insertion sort on this array: Initial Array: [12, 11, 1

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, indicating that the list is sorted. It is called "bubble sort" because smaller elements "bubble" to the top of the list as the algorithm iterates through it. Here's a step-by-step description of the bubble sort algorithm along with a real-time example: Algorithm Description: 1.Start at the beginning of the list. 2.Compare the first two elements. If the first element is larger than the second element, swap them. 3.Move to the next pair of elements (i.e., the second and third elements), and repeat step 2. Continue this process until you reach the end of the list. After this pass, the largest element will have "bubbled up" to the end of the list. 4.Repeat steps 1-3 for the remaining elements (excluding the last one, which

Binary search is a popular search algorithm that works on sorted arrays or lists. It's an efficient way to find a specific target element within a collection of data. Here's a detailed algorithm for binary search, along with a real-time example. Binary Search Algorithm: Binary search works by repeatedly dividing the search interval in half. It compares the middle element of the current interval with the target element. If the middle element matches the target, the search is successful. If not, it narrows down the search interval to the left or right half, depending on whether the target is greater or less than the middle element. This process continues until the target element is found or the search interval becomes empty. Input: arr: A sorted array (or list) of elements. target: The element you want to find in the array. Initialization: Initialize two pointers, left and right, to the first and last indices of the array, respectively. Search Loop: While left is less than or equ

Linear search, also known as sequential search, is a simple searching algorithm that searches for a target element in a list or array one element at a time, starting from the beginning and moving sequentially through the list until the element is found or the end of the list is reached. Here's a detailed algorithm for linear search, along with a real-time example: 1.Linear Search Algorithm:Start from the first element (index 0) of the list. 2.Compare the current element with the target element you are searching for. 3.If the current element is equal to the target element, you have found a match, and you can return the index of the current element as the result. 4.If the current element is not equal to the target element and you have not reached the end of the list, move to the next element (increment the index by 1) and repeat steps 2-3. 5.If you have reached the end of the list (i.e., you have compared all elements) and have not found a match, return a "not found" or &qu

Merge Sort is a popular sorting algorithm that uses a divide-and-conquer approach to sort an array or list. Merge Sort works by recursively dividing an array or list into smaller sub-arrays until each sub-array contains only one element (which is trivially sorted). Then, it repeatedly merges these smaller sorted sub-arrays to produce a larger, sorted array. It's efficient and stable, with a time complexity of O(n log n) in the worst, average, and best cases. Here's a detailed algorithm for Merge Sort. Algorithm: Divide: Divide the unsorted list into two sublists of about equal size. You can do this by finding the middle point of the list. Divide the unsorted array into two halves.Find the middle of the array by calculating  middle = (start + end) // 2, where start is the index of the first element, and end is the index of the last element. Conquer: Recursively sort both sublists. This is done by applying the merge sort algorithm to each sublist until they become smaller sublist

Heap Sort is a comparison-based sorting algorithm that works by first converting the input array into a max-heap or a min-heap, depending on whether you want to sort in ascending or descending order. Here, I'll provide a detailed algorithm for Heap Sort. Algorithm: Heap Sort Build a Max-Heap: Build a max-heap from the input array. A max-heap is a binary tree where each parent node is greater than or equal to its child nodes. This step ensures that the largest element is at the root of the heap. Swap Root with Last Element: Swap the root element (the largest) with the last element in the heap. This ensures that the largest element is in its correct sorted position at the end of the array. Heapify: After the swap, the heap property may be violated. To restore it, perform a heapify operation on the reduced heap (excluding the last element). This will bring the next largest element to the root. Repeat: Repeat steps 2 and 3 until the entire array is sorted. The heap size decreases wit