Data Structures & Algorithms Notes PDF

# Hanoi Tower - C# ```C# public class tower { static void towerofHanoi(int n, char from, char to, char help) { if (n == 0) { return; } towerofHanoi(n - 1, from, help, to); System.out.println("Take disk " + n + " from rod " + from + " to rod " + to);...

# Hanoi Tower - C# ```C# public class tower { static void towerofHanoi(int n, char from, char to, char help) { if (n == 0) { return; } towerofHanoi(n - 1, from, help, to); System.out.println("Take disk " + n + " from rod " + from + " to rod " + to); towerofHanoi(n - 1, help, to, from); } public static void main(String args[]) { int n = 3; towerofHanoi(n, 'A', 'C', 'B'); }} ``` **Output:** 1. From A to C 2. From A to B 1. From C to B 3. From A to C. 1. From B to A 2. From B to C 1. From A to C ## Fibonacci Series in C# ### What it is **Definition:** `fib(n) = fib(n-1) + fib(n-2)` **Example:** ```C# fib(4) = fib(3) + fib(2) // fib(4) is the 4th number in the Fibonacci Series = fib(2) + fib(1) + fib(1) + fib(0) = fib(1) + fib(0) + 1 + 1 + 0 = 1 + 0 + 1 + 1 + 0 = 3 ``` ## Hashing in C# ### What it is - Hashing: A technique to search in O(1). - Hash Table/Hash Map: A data structure used to store key-value pairs. ### Implementation - HashTable: - Uses key to produce a hash value, which is a small integer value. - The hash value is then used to determine the index of the key in the hash table. ### Collision and Resolution - When two keys produce the same hash value, a collision occurs. - There are several ways to resolve collisions: - **Closed addressing, Open Hashing (Chaining):** This method keeps a linked list of keys that map to the collided hash value. - **Open addressing, Closed hashing:** This method continues to look for an empty index within the hash table. ### Load Factor - The load factor is the ratio of the number of used spots in the hash table to the size of the hash table. - A load factor of 1 means there is one entry for each index in the hash table. - Load factor = (No. of Occupancies/Table Size). ## Closed Addressing, Open Hashing (Bucket) ### Example: ```C# // Example data: 10, 22, 86, 12, 42 // Hash function: h(x) = x % 10 ``` | Index | Value | |---|---| | 0 | 10 | | 1 | N/A | | 2 | 22, 12, 42 | | 3 | N/A | | 4 | N/A | | 5 | N/A | | 6 | 86 | | 7 | N/A | | 8 | N/A | | 9 | N/A | Load Factor = 5/10 = 0.5 ## Closed Addressing, Open Hashing (Chaining) ### Example: ```C# // Example data: 10, 22, 86, 12, 42 // Hash function: h(x) = x % 10 ``` - Index 0: 10 - Index 2: 22 -> 12 -> 42 - Index 6: 86