Creating a design specification for data structures

[Audio] Welcome to this presentation on creating a design specification for data structures. This presentation will cover the following topics. It will begin by the defining the specifications of data structures. The next topic will deal with the operations of data structures. Examples of how operations can be applied will be then demonstrated by the elucidation of an data type, and a concrete data type. Then the presentation will focus on two sorting algorithms. There are multiple sorting algorithms but this presentation will focus on the bubble sort and the quick sort. This presentation will conclude by two network shortest path algorithms. The shortest path algorithms that will be adumbrated is the single-source algorithm and the all-pairs algorithm..

[Audio] The specifics of data structure .The number of components determine how a data structure is specified. Data structures are fixed if the components are even. Data structures are variable when components transform. Arrays and records are examples of fixed-size data structure types. Stacks, lists, sets, tables, and files are an example of variable size data types. Variable size data objects use a pointer data type that enables fixed-size data objects to be connected explicitly by the programmer..

[Audio] This section will adumbrate the operations of data structures. The fixed size data structure type known as arrays and will be discussed. This will be followed by the description of variable size data structure types such as lists and sets..

[Audio] Arrays. The programming language at developers at this company use is Python. This programming language does not support arrays without the import of a library therefore the discussion of arrays will be brief, and no example is necessary. In Python lists are used instead of arrays. Arrays are used in Java to store multiple values in one single variable. The operations that can be performed with arrays are traverse, insertion, deletion, search , and update. Arrays can perform mathematical operations. The limitation of arrays is that the size of the array needs to known in advance. In addition, The array is a static data structure with a fixed size so, the size of the array cannot be modified further and hence no modification can be done during runtime.

[Audio] Lists. Like arrays lists are used to store multiple items in one variable. Unlike arrays lists cannot perform mathematical operations. Lists also use more memory that arrays. The advantage of lists over arrays is that they are changeable and allows duplicates. Operations include Indexing, subscripting, membership test, appending, popping..

[Audio] Here is an example of a list in python.. Data Points Digital background.

[Audio] Here is an example of how to and a new item to the list. This is called appending..

[Audio] An example of an data ( ADT) will be given but first a brief description of ADT` s will be given. ADT`s behaviour is defined be a set of values and operations. It is called because it gives an implementation-independent viewADT`s use class, hides inside details, is reusable, and the concepts are high level. The rule for stack is last in first out so the last element inserted will be at the top of the stack. Here are the results. Holland was pushed to the top ahead of Argentina. Iran was pushed to the top ahead of Holland but these to items were removed because of two pops. Poland was then pushed to the top above Argentina. Finally, Belgium is pushed to the top of the stack. There are different types of ADT`s such as lists and queues but the example below is that of a stack ADT. The operations used in a ADT stack are push(), pop() peek(), size, isEmpty, and isFull. In this example the picture will illustrate push and pop operations. The push will push a object to the top of the stack. Pop removes the object from the stack the following commands below is instructions to implement world cup teams into a program..

[Audio] Concrete data structure for a First In First out ( FIFO) queue. A concrete data structure differs from an ADT because It is a specialized solution-oriented data type that represents a well-defined single solution domain concept. Unlike ADT`s data cannot be improved without breaking the program. Concrete data structure have less efficiency and the concept are simple in contrast to ADT`s. The data type uses structure rather that class and the data is transparent. This data type is hardly ever able to be reused. First in first out( fifo) refers to the linear structure of concrete data structures. Elements are inserted at the back and deleted at the front. Insertion is known as enqueue deletion is known as dequeue other operations include front operation which shares similarities with ADT`s peek and isEmpty which checks whether the queue is empty. The following slide will show an example of a fifo queue using enqueue and dequeue. Here is an example of a concrete data structure for a First In First out (FIFO) queue. Messi will be added. Cruyff will be removed, Ronaldo will be added as will Mbappe. The results are as follows. Messi is enqueued and thus goes to the back of the queue behind Maradona. Cruyff is dequeued at the front. C.Ronaldo is enqueued, Pele is dequeued. Finally Mbappe is enqueued..

[Audio] The first of two sorting algorithms to be explained is the bubble sort. The bubble sort is a sorting algorithm that is simple and iterative. The methodology of this algorithm is to repeatedly swap adjacent elements until everything is in order. Its time complexity is O(n^ 2). If the value of n is 2, ideally the loop is going to run 4 times, and if it is 4, it would run 16 times; and so on. For this reason this algorithm is regarded as less useful because it is more time consuming than other sorting algorithms. Here is an example of a bubble sort. This is an unsorted array. 10 is compared to 4. As 10 is greater than 4 the elements must swap. 10 is now compared to 6. As 10 is greater than 6 the elements must swap. 10 is compared to 8. As 10 is greater than 8 the elements must swap. 10 is compared to 11. As 10 is smaller than 11 it remains in place and the sort is complete.

[Audio] Quick sort. The quick sort is know as a divide and conquer algorithm. It conquers the problem of an array being out of order by selecting a pivotal point. Once the pivotal element is selected the other elements are partitioned into two sub arrays. As the name suggests it is a fast sorting algorithm. It has the best time complexity when compared to other sorting algorithms. Here is a quick sort example. The image above shows the array being split into two sub arrays and the number 8 has been selected as the pivot everything smaller than 8 will be shifted to its left, everything that is greater than 8 will be shifted to the right as can be seen below. This sub-array is now sorted. Now its time for the sub-array to the right of the 8 to be sorted 10 is the chosen pivot point. As 11 is greater than 10 it move to the right of ten. The list is now sorted The initial quick sort has successfully moved the numbers less than 8 to the left and greater than 8 to the right. But the two sub arrays are still not in order so another pivot will be chosen to the left of 8. The pivot will be 3. 1 will go to the left of three and 7 will go to the right.

[Audio] Dijkstra's algorithm. Dijkstra's algorithm is known as a shortest path algorithm. The purpose of shortest path algorithm is to minimise the routing cost by finding the shortest path between nodes. Graph`s are often used to represent the distance between nodes. Dijkstra`s algorithm serves an important purpose in this increasing age of artificial intelligence. This algorithm is used in GPS devices to find the shortest path between the current location and the destination. It has broad applications in industry, specially in domains that require modelling networks. The algorithm begins at the node of the users choosing and examine the graph to locate the shortest path. The algorithm keeps a record of the shortest distance from each node making regular updates. Each node is marked as visited and the process continues until every node is added to the path..

[Audio] The A* algorithm is regarded as one of the best shortest path algorithms. This algorithm not only uses the principles of Dijkstra's algorithm but expands on in it to get a quicker solution to finding the shortest paths between two nodes The algorithm simultaneously peeks at multiple paths rather than Dijkstra`s one by one approach. Like Dijkstra`s algorithm this algorithm is also good for maps, gaming, and so on. Each path is weighted. As the multiple paths are explored the weight will fluctuate. The heuristic approach that the A* algorithm takes makes this algorithm faster and better than Dijkstra`s model. Heuristics is good because it prioritises the algorithms options..

Bibliography. freeCodeCamp.org. (2020). Dijkstra’s Shortest Path Algorithm - A Detailed and Visual Introduction. [online] Available at: https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/#:~:text=You%20need%20to%20follow%20these [Accessed 7 Dec. 2022]. Freecodecamp.org. (2022). [online] Available at: https://www.freecodecamp.org/news/content/images/2020/06/image-126.png [Accessed 7 Dec. 2022]..

Bibliography. GeeksforGeeks (20 1 7).Abstract Data Types - GeeksforGeeks. [online] GeeksforGeeks. Available at: https://www.geeksforgeeks.org/abstract-data-types/. GeeksforGeeks. (2022).Applications,Advantages and Disadvantages of Array. [online] Available at: https:llwww.geeksforgeeks.orglapplications-advantages-and-disadvantages- of-array-data- Oarray%20is%20a%20static [Accessed 27 Nov. 2022]. Patel, H. (2022).An Overview of QuickSort Algorithm. [online] Medium.Available at: https://towardsdatascience.com/an-overview-of-quicksort-algorithm- b9 144e3.

Bibliography. R, V. (2021). What is Data Structure: Need, Types & Classification. [online] Great Learning Blog: Free Resources what Matters to shape your Career! Available at: https://www.mygreatlearning.com/blog/data-structure-tutorial-for-beginners/#need-of-data-structure [Accessed 23 Nov. 2022]. www.tutorialspoint.com. (n.d.). What are the specifications and operations of data structures in compiler design? [online] Available at: https://www.tutorialspoint.com/what-are-the-specifications-and-operations-of-data-structures-in-compiler-design# [Accessed 23 Nov. 2022]. www.w3schools.com. (n.d.). Python Arrays. [online] Available at: https://www.w3schools.com/python/python_arrays.asp..