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

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

  In hash table data structures, several hashing techniques are commonly used. Here are some of the most popular ones: Division Hashing: Uses the modulo operation to obtain a hash code. The formula is hash_code = key % table_size . Simple and computationally efficient. Prone to clustering if keys have a pattern that aligns with the table size. Multiplication Hashing: Involves multiplying the key by a constant A in the range (0, 1), extracting the fractional part, and then multiplying it by the size of the hash table. Formula: hash_code = int(table_size * ((key * A) % 1)) . Provides a more uniform distribution compared to division hashing. Universal Hashing: Uses a family of hash functions, and a random hash function is selected for each instance of the hash table. Reduces the likelihood of collisions, even for worst-case key distributions. Achieves good average-case performance. Double Hashing: Involves using a secondary hash function to resolve collisions. The formula is hash_code = (

Hashing is a technique used in data structures to map data of arbitrary size to fixed-size values, typically for the purpose of creating a faster and more efficient data retrieval system. The concept is based on a hash function, which takes an input (or 'key') and produces a fixed-size string of characters, which is usually a hash code. The hash code is then used to index into a data structure (usually an array or a hash table) where the values are stored. Let's go through the key components and concepts related to hashing: Hash Function: A hash function is a mathematical function that takes an input (or 'key') and produces a fixed-size string of characters, which is the hash code. The goal is to distribute the keys uniformly across the range of possible hash codes. Key properties of a good hash function: Deterministic: For the same input, the hash function should always produce the same hash code. Efficient: The hash function should be computationally efficient t

A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. This provides a data structure that can be searched in O(1) time. Each bucket can consists of S slots. Each bucket can hold only one record if it contains one slot. Example: Lets consider a hash table with 26 buckets and 2 slots. Lets consider a hash function F(X) which maps all identifiers X based on the first character in X. The identifiers A,A2,D,GA,G are hashed into the corresponding buckets/slots as shown below. Here are the key components and characteristics of a hash table: Hash Function: A hash function takes a key as input and produces a hash code, which is used as an index to access the corresponding value in the hash table. The hash function should be deterministic (same key should always produce the same hash code) and prov