Download to read offline
Introduction to Data Structures and Algo
- 1.
- 2. Subject Overview Course Description Thecourse covers the standard data representation and algorithms to solve computing problems efficiently (with respect to space requirements and time complexity of algorithm). This covers the following: Stacks, Queues, Trees, Graphs, Maps and Sets. Through of sorting and searching algorithms and hashing is covered. Learning Outcome • Explain and utilize linked lists, stacks, queues, and trees. • Incorporate algorithmic design know-how and data structures to create reliable and structured programs. • Describe the design and performance of various searching and sorting algorithms. • Use advanced object-oriented concepts such as abstract base classes, friend classes, and operator overloading in the implementation of data structures.
- 3. Introduction to DataStructures and Algorithm
- 4. Airline Booking System Consideran airline booking system that stores thousands of flight schedules, including departure times, destinations, and available seats. When a passenger searches for flights from New York to London, the system looks through the stored records to find all flights that match. Once the matches are found, the system can arrange them by departure time, price, or shortest travel duration before showing the results. Sample Scenario In the above scenario, figure out the ff: ⚬ Data structure: how the information is stored. ⚬ Algorithm: the step-by-step method used to search, filter, or sort that stored information. ⚬ Connection: why the way data is stored affects how fast and accurate the search or sorting process is.
- 5. What are DataStructures and Algorithm Good for? ⚬ A data structure is an arrangement of data in a computer’s memory (or sometimes on a disk). Data structures include arrays, linked lists, stacks, binary trees, and hash tables, among others. ⚬ Algorithms manipulate the data in these structures in various ways, such as searching for a particular data item and sorting the data.
- 6. Overview Data Structures Adata structure is a specialized format for organizing, processing, and storing data so it can be accessed and modified efficiently. It defines the way data elements are arranged in memory and the operations that can be performed on them. Data Structure is a systematic way to organize data in order to use it efficiently. The following terms are the foundation terms of a data structure. ⚬ Interface Each data structure has an interface. The interface represents the set of − operations that a data structure supports. An interface only provides the list of supported operations, the type of parameters they can accept, and the return type of these operations. ⚬ Implementation Implementation provides the internal representation of a data − structure. The implementation also provides the definition of the algorithms used in the operations of the data structure.
- 7. Characteristics Data Structures •Correctness Data structure implementation should implement its − interface correctly. • Time Complexity Running time or the execution time of operations of − the data structure must be as small as possible. • Space Complexity Memory usage of a data structure operation − should be as little as possible.
- 8. Need for DataStructures • As applications are getting complex and data-rich, there are three common problems that applications face nowadays. ⚬ Data Search − Consider an inventory of 1 million(106) items of a store. If the application is to search an item, it has to search an item in 1 million(106) items every time slowing down the search. As data grows, search will become slower. ⚬ Processor Speed − Processor speed, although very high, falls limited if the data grows to billion records. ⚬ Multiple Requests − As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data. • To solve the above-mentioned problems, data structures come to the rescue. Data can be organized in a data structure in such a way that all items may not be required to be searched, and the required data can be searched almost instantly.
- 9. Execution Time Cases •There are three cases that are usually used to compare various data structures’ execution times in a relative manner. ⚬ Worst Case This is the scenario where a particular data structure operation − takes the maximum time it can take. If an operation’s worst-case time is ƒ(n) then this operation will not take more than ƒ(n) time, where ƒ(n) represents the function of n. ⚬ Average Case This is the scene depicting the average execution time of an − operation of a data structure. If an operation takes ƒ(n) time in execution, then m operations will take m ƒ(n) time. ⚬ Best Case This is the scene depicting the least possible execution time of an − operation of a data structure. If an operation takes ƒ(n) time in execution, then the actual operation may take time as the random number which would be maximum as ƒ(n).
- 10. Basic Terminology • Data− Data are values or sets of values. • Data Item Data item refers to a single unit of values. − • Group Items Data items that are divided into sub-items are called Group Items. − • Elementary Items Data items that cannot be divided are called Elementary Items. − • Attribute and Entity An entity is that which contains certain attributes or properties, − which may be assigned values. • Entity Set Entities of similar attributes form an entity set. − • Field Field is a single elementary unit of information representing an attribute of an − entity. • Record A record is a collection of field values of a given entity. − • File A file is a collection of records of the entities in a given entity set. −
- 11. Characteristics of DataStructure
- 12. Characteristics of DataStructure
- 13. Overview of Algorithms •Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language. • Many of the algorithms we’ll discuss apply directly to specific data structures. For most data structures, you need to know how to ⚬ Insert a new data item. ⚬ Search for a specified item. ⚬ Delete a specified item. • From the data structure point of view, the following are some important categories of algorithms ⚬ Search Algorithm to search an item in a data structure. − ⚬ Sort Algorithm to sort items in a certain order. − ⚬ Insert Algorithm to insert an item in a data structure. − ⚬ Update Algorithm to update an existing item in a data structure. − ⚬ Delete Algorithm to delete an existing item from a data structure. −
- 14. Characteristics of anAlgorithm • Not all procedures can be called an algorithm. An algorithm should have the following characteristics ⚬ Unambiguous The algorithm should be clear and unambiguous. Each of its steps (or − phases), and their inputs/outputs should be clear and must lead to only one meaning. ⚬ Input An algorithm should have 0 or more well-defined inputs. − ⚬ Output An algorithm should have 1 or more well-defined outputs and should match the − desired output. ⚬ Finiteness Algorithms must terminate after a finite number of steps. − ⚬ Feasibility This should be feasible with the available resources. − ⚬ Independent An algorithm should have step-by-step directions, which should be − independent of any programming code.
- 15. How to Writean Algorithm? • There are no well-defined standards for writing algorithms. Rather, it is problem and resource- dependent. Algorithms are never written to support a particular programming code. • As we know that all programming languages share basic code constructs like loops (do, for, while), flow-control (if-else), etc. These common constructs can be used to write an algorithm. • We write algorithms in a step-by-step manner, but it is not always the case. Algorithm writing is a process and is executed after the problem domain is well-defined. That is, we should know the problem domain, for which we are designing a solution.
- 18. ■There are multipleways to solve a problem using a computer program. For instance, there are several ways to sort items in an array. You can use merge sort, bubble sort, insertion sort, etc. All these algorithms have their own pros and cons. An algorithm can be thought of as a procedure or formula to solve a particular problem. The question is, which algorithm to use to solve a specific problem when there exist multiple solutions to the problem? ■Algorithm analysis refers to the analysis of the complexity of different algorithms and finding the most efficient algorithm to solve the problem at hand. Big-O Notation is a statistical measure, used to describe the complexity of the algorithm.
- 21. Algorithm Analysis withBig-O Notation • Big-O notation is a metric used to find algorithm complexity. Basically, Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm. It is denoted by a big "O" followed by opening and closing parenthesis. Inside the parenthesis, the relationship between the input and the steps taken by the algorithm is presented using "n". • For instance, if there is a linear relationship between the input and the step taken by the algorithm to complete its execution, the Big-O notation used will be O(n). Similarly, the Big-O notation for quadratic functions is O(n^2)
- 23.
- 24.
- 25.
- 26.
- 28.
- 31. Worst vs BestCase Complexity
- 32.
- 33. Watch this videoas supplemental discussion
Editor's Notes
- #3 A data structure is a way to store data. We structure data in different ways depending on what data we have, and what we want to do with it linear elements are arranged sequentially non linear elements are not arrange representing hierarchical or network relationships
- #4 Data Structure: Flight details (city, time, seats, price) are stored in tables or databases so the system can access them quickly. Algorithm: The steps the system follows to find flights from New York to London, then arrange them by time, price, or duration. Connection: How flights are stored affects how fast and accurate the search and sorting will be. An organized structure makes the process much quicker. elationship Between Data Structures and Algorithms Data structures deal with how data is stored. Algorithms deal with how data is processed.
- #5 A linked list is a data structure that stores a sequence of elements. Each element in the list is called a node, and each node has a reference to the next node in the list. The first node in the list is called the head, and the last node in the list is called the tail. A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains only one pointer top pointer pointing to the topmost element of the stack A “binary tree” is a tree data structure where every node has two child nodes (at the most) that form the tree branches. These child nodes are called left and right child nodes. A hash table is a data structure that is used to store keys/value pairs. It uses a hash function to compute an index into an array in which an element will be inserted or searched.
- #6 A data structure is not worth much if you cannot search through it or manipulate it efficiently using algorithms, and the algorithms in this tutorial are not worth much without a data structure to work on. Interface - It acts as a contract that specifies "what" a data structure can do, without revealing "how" it does it. Implementation - It involves defining how the data is stored in memory and how the various operations (like adding, deleting, or accessing elements) are performed using specific algorithms
- #14 admitting of no doubt or misunderstanding; having only one meaning or interpretation and leading to only one conclusion. Finite-having limits feasible-convenient
- #16 In design and analysis of algorithms, usually the second method is used to describe an algorithm. It makes it easy for the analyst to analyze the algorithm ignoring all unwanted definitions. He can observe what operations are being used and how the process is flowing.
- #19 https://stackabuse.com/big-o-notation-and-algorithm-analysis-with-python-examples/ Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself.
- #20 µ - expected value ±
- #21 O(n) – Linear we used the BIG O notation to describe the performance of algorithm Specifically, it describes the worst-case scenario in terms of time or space complexity. and helps us determine if a given program is scalable or not pasabot makatimbang timbang ba sya kong magkadaghan ang execute nga codes just because it response quickly doesn’t mean its gonna perform well kong dinaghanay o dinagkoay na nga data sets Now, what does this have to do with algorithm? Certain operation can be more or less costly depending on what data structure we use
- #22 Logarithmic is the inverse of exponential functions
- #23 Irrespective means without considering o not needing to allow for Line 1: def constant_algo(items): def: This keyword defines a function. constant_algo: This is the name of the function. items: This is a parameter that will be passed to the function. It represents a list of items. Line 2: result = items[0] * items[0] result: This is a variable that will store the calculated value. items[0]: This accesses the first element in the items list. *: This is the multiplication operator. items[0]: This accesses the first element in the items list again. The line calculates the square of the first element in the items list and stores the result in the result variable. Line 3: print() print(): This function is used to print output to the console. However, since there's no argument passed to it, it will print an empty line.
- #24 import matplotlib.pyplot as plt: This line imports the pyplot module from the matplotlib library and assigns it the alias plt. matplotlib is a powerful library for creating visualizations and plots in Python. pyplot provides a simple interface for creating various types of plots, including line plots, scatter plots, histograms, and more. 2. import numpy as np: This line imports the numpy library and assigns it the alias np. numpy is a fundamental library for numerical computations in Python. It provides efficient data structures and functions for working with arrays and matrices. 3. x = [2, 4, 6, 8, 10, 12]: This line creates a list named x and assigns it the values [2, 4, 6, 8, 10, 12]. This list will represent the input values for the plot. 4. y = [2, 2, 2, 2, 2, 2]: This line creates a list named y and assigns it the values [2, 2, 2, 2, 2, 2]. This list will represent the corresponding output values (steps) for the plot. 5. plt.plot(x, y, 'b'): This line creates a line plot using the plt.plot() function. The arguments are: x: The list of input values. y: The list of corresponding output values. 'b': The color of the line, where 'b' stands for blue. 6. plt.xlabel('Inputs'): This line sets the label for the x-axis to 'Inputs'. 7. plt.ylabel('Steps'): This line sets the label for the y-axis to 'Steps'. 8. plt.title('Constant Complexity'): This line sets the title of the plot to 'Constant Complexity'. 9. plt.show(): The output of the program would be a line plot showing the relationship between the input values (x) and the corresponding output values (y). Since all the output values in y are 2, the plot will be a horizontal line at y=2. The x-axis will be labeled as "Inputs" and the y-axis will be labeled as "Steps". The title of the plot will be "Constant Complexity".
- #28 when the runtime scales quadratically with the input. As the input size increases, the runtime of the algorithm also increases in a quadratic fashion Line 1: def quadratic_algo(items): def: This keyword defines a function. quadratic_algo: This is the name of the function. items: This is a parameter that will be passed to the function. It represents a list of items. Line 2: for item in items: for: This keyword initiates a loop. item: This is a temporary variable that will hold each element of the items list during the loop. items: This is the list that will be iterated over. This line starts a loop that will iterate over each element in the items list. Line 3: for item2 in items: This line starts a nested loop within the outer loop. It will iterate over each element in the items list again for each element in the outer loop. item2: This is a temporary variable that will hold each element of the items list during the inner loop. Line 4: print(item, " ", item) This line prints the current values of item and item2 to the console, separated by a space. print(): This function is used to print output to the console. item: The first element of the pair. " ": A space to separate the elements. item2: The second element of the pair. Line 5: quadratic_algo([4, 5, 6, 8]) This line calls the quadratic_algo function and passes it a list of numbers: [4, 5, 6, 8]. Overall Functionality The code defines a function named quadratic_algo that takes a list of items as input. It uses nested loops to iterate over each pair of elements in the list and prints them to the console. The output will be a series of pairs, where each pair consists of two elements from the input list. The time complexity of this algorithm is quadratic because the inner loop iterates over the list for each element in the outer loop, resulting in a total of n^2 iterations (where n is the number of elements in the list).
- #29 Line 1: def complex_algo(items): def: This keyword defines a function. complex_algo: This is the name of the function. items: This is a parameter that will be passed to the function. It represents a list of items. Line 2: for i in range(5): for: This keyword initiates a loop. i: This is a temporary variable that will hold the current index value during the loop. range(5): This creates a range of numbers from 0 to 4 (inclusive). This line starts a loop that will iterate 5 times. Line 3: print("Python is awesome") This line prints the string "Python is awesome" to the console. Line 4: for item in items: This line starts another loop that will iterate over each element in the items list. item: This is a temporary variable that will hold each element of the items list during the loop. Line 5: print(item) This line prints the current value of item to the console. Line 6: for item in items: This line starts another loop that will iterate over each element in the items list again. Line 7: print(item) This line prints the current value of item to the console. Lines 8-10: print("Big O") These lines print the string "Big O" to the console three times. Line 11: complex_algo([4, 5, 6, 8]) This line calls the complex_algo function and passes it a list of numbers: [4, 5, 6, 8]. Overall Functionality The code defines a function named complex_algo that takes a list of items as input. It performs the following steps: Loop 1: Iterates 5 times and prints "Python is awesome" each time. This is a constant-time operation with a time complexity of O(1). Loop 2: Iterates over each element in the items list and prints the element. This is a linear-time operation with a time complexity of O(n), where n is the number of elements in the list. Loop 3: Iterates over each element in the items list again and prints the element. This is also a linear-time operation with a time complexity of O(n). Prints "Big O" three times: This is a constant-time operation with a time complexity of O(1). The overall time complexity of the function is dominated by the two linear-time loops, so the total time complexity is O(n) + O(n) = O(2n) = O(n). This means that the function's running time grows linearly with the size of the input list.
- #31 best-case time complexity of an algorithm is the minimum amount of time it takes to solve a problem for any input. The worst-case time complexity is the maximum amount of time it takes to solve a problem for any input.
- #32 amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input