Data Structures and Algorithms Notes PDF

# DATA STRUCTURES AND ALGORITHMS ## COURSE OUTLINE 1. DSA Concepts 2. Intro to Arrays 3. Stacks 4. Queues 5. Linked-list 6. Binary trees 7. Recursions 8. Sorting ## REFERENCES - Data Structures asing C/C++ - Tenenbaum - Data Structures and Algorithm - Savitch ## DSA CONCEPTS Data structure is...

# DATA STRUCTURES AND ALGORITHMS ## COURSE OUTLINE 1. DSA Concepts 2. Intro to Arrays 3. Stacks 4. Queues 5. Linked-list 6. Binary trees 7. Recursions 8. Sorting ## REFERENCES - Data Structures asing C/C++ - Tenenbaum - Data Structures and Algorithm - Savitch ## DSA CONCEPTS Data structure is a method of organizing data in a virtual system. Ex. sequence of numbers, tables of data. Algorithm is a sequence of steps executed by a computer that takes an input and transforms it into a target output. ## USES OF DSA Allow us to organize and store data while algorithms allow us to process that data in a meaningful way. - Specialized format for organizing, processing, retrieving, and storing data. ## IMPORTANCE OF DSA IN PROBLEM SOLVING - Helps breakdown complex problems into smaller, more manageable components, allowing for easier analysis and solution design. - Developers (programmers) can identify patterns and apply appropriate solutions to a wide range of challenges. ## ARRAY - A type of linear data structures that is defined as a collection of elements with the same or different data types. - Ex: - Index: 0 1 2 ... n - Array: 100 32 1 ... A - Array is used as a solution to many problems from the small sorting problems to more complex problems ## STACKS - An ordered list in which all insertions and deletions are made at one end, called the top of the stack. - Ex: Insert 5, 3, 1, 4, 2 onto the stack and arrange the numbers in ascending order, such that the smallest number or element is the bottommost element. ### BASIC OPERATIONS 1. Clearstack (C) - If clears the stack, all elements in the stack will be deleted / cleared. 2. Empty stack (S) - There is no element in the stack. 3. Push (i, s) - Insert or add an element into the stack. 4. Pop (s, d) - Remove or delete an element from the stack. ### EXAMPLE Convert the following infix notations to prefix and postfix notation. 1. A + B * (C + D) / E + F - Prefix: ++A * BC + DE + F - Postfix: AB CD + * DE / + F + 2. (A / D * (B ^ C * D) / E) - H - Prefix: - + / AD * ^ BC * DE - Postfix: AD / BC * DE ^ * / E H - 3. A * (B + C / D ^ E) + (F * G * H) - Prefix: + * A + B / C ^ DE * F * G * H - Postfix: A B C D ^ / + * F G H * * + 4. A / B + C / D - E * F ^ G - Prefix: + / A B / C D * E F ^ G - Postfix: AB / CD / + E FG ^ * - 5. A + B + C + D + E + F + G - Prefix: +++++++ABCDEFG - Postfix: ABCDEFG ++++++ ### PREFIX TO INFIX ``` A + B + C + D + E + F + G + * ^ A ^ B ^ C B E / F G H + * ^ A ^ B (C ^ D)/(F ^ G) H + * ^ A (B ^ C ^ D)E (F ^ G / H) + * (A ^ B ^ C ^ D) F (F ^ G / H) + (A ^ B ^ C ^ D F E) (F ^ G / H) A ^ B ^ C ^ D E + F ^ G / H ``` ### POSTFIX TO INFIX ``` ABCD ^ ^ E F E H + AB (L A D) ^ ^ E * (F G) H / + A (B ^ ( ^ D) * E * (F ^ G / H) + (A ^ B ^ C ^ D) E * (F ^ G / H) + (A ^ B ^ ( ^ O K E) (F ^ G / H) + A^B^C^D*E+ F^G/H ``` ## QUEUE - An ordered list in which all insertions are made at one end called rear, and all deletion are made at the other end called the front. - Representation: - Rear: A - [B] <- - Front: C - Remove (Dequeue) - Insert (Enqueue) ### BASIC OPERATIONS 1. Clear Queue (Q): It clears the queue, once the queue is clear, no elements remain in the queue. 2. Empty Queue (Q): If there is no element in the queue. 3. Inqueue (i, q): Insert an element or node in the queue. 4. Dequeue (q, d): Delete an element or node in the queue. ### EXAMPLE Simulate the algorithm below: ``` Clear queue (Q); i = 1; x = 2; y = 0; i = 4; Enqueue (w, q); Enqueue (x, q); Enqueue (y, q); Enqueue (z, q); for (i = 1; i < 3; i++) { Enqueue (w + x, q); Enqueue (y + z, q); Enqueue (w + x + y + z, q); Enqueue (z, q); } While not empty queue (Q) do { Dequeue (q, w); Dequeue (q, x); Dequeue (q, y); Print F ("%d", x); Print F ("%d", y); Print F ("%d", z); } ``` ### OUTPUT ``` 12873737104 3 3 7 3 7 10 4 3 7 3 7 10 4 4 4 2 8 4 3 7 3 1 2 4 W X Y W X Y W Y Z ``` ## BINARY TREE - Hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. It is commonly used for efficient storage and retrieval of data, with various operations such as insertion, deletion, and traversal. ### Types of Binary Tree 1. Full Binary Tree 2. Complete Binary Tree ### Binary Tree Traversal 1. **Inorder Traversal:** LTR - A + B 2. **Preorder Traversal:** TLR - A B + 3. **Post Order Traversal:** LRT - A B + ### EXAMPLE ``` C E F G H I J K L INORDER (LTR): HOIDJTAFKCGL PREORDER (TLR): ABDHIEJCTKGL POSTORDER (LLTR): HIDJEBKFL 6CA ``` ### BINARY SEARCH TREE - Is a data structure used for organizing and storing data in a sorted manner. Each node has at most two children, with the left child containing values less than the parent node, and the right child containing values greater than the parent node. This structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree. - Draw the following series of numbers (integers) using binary search tree. - 18 42 100 23 45 11 71 34 49 52 4 - 70 4 120 9 48 61 \ 24 11 40 61 32 4 120 43 5 8 - LTR: 6 11 18 23 34 45 49 52 62 - 11 100 - 70 4 9 5 8 11 24 \ 32 39 40 43 48 \ 41 61 70 120 100 ## Conclusion This document provides an overview of the basic concepts of data structures and algorithms, highlighting their importance, uses, and implementation in programming. The document covers key data structures like arrays, stacks, queues, and binary trees, explaining their operations and highlighting their significance in problem-solving. The document also introduces the concept of binary search trees, a specialized data structure used for efficient searching and sorting. Overall, this document serves as an excellent foundation for understanding the core concepts of data structures and algorithms, providing a comprehensive framework for further exploration in this field.