Name: Creating a design specification for data structures
Uploaded: 2022-12-08
Duration: 12 min 31 s
Description: Creating a design specification for data structures.

Creating a design specification for data structures. 

Scene 1

Creating a design specification for data structures

This presentation will cover the following topics. 

Scene 2

This presentation will cover the following topics

1.	The specifications of data structures 2.	The operations of data structures 3.	A stack ADT example 4.	Concrete data structure 5.	Bubble sort  6.	Quick sort 7.	Dijkstra's Algorithm 8.	A* Algorithm

Introduction. A group of people sitting at a table. 

Scene 3

• Dat:a is organized in computer science by using dat:a
structures "Dat:a structure provides efficiency, reusability
and abstraction. It plays an import:ant role in enhancing
the performance of a program because the main function
of the program is to store and retrieve the user's dat:a as
fast as possible." (R, 2021)

Data Points Digital background. 1.	The specifications of data structures. 

Scene 4

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.” (www.tutorialspoint.com, n.d.)

Data Points Digital background. 2.	The operations of data structures. 

Scene 5

This section will adumbrate the operations of the following:  Fixed-size data structure type (Arrays) Variable-size data structure types (Lists, sets)

Data Points Digital background. 2.1.	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. (www.w3schools.com, n.d.) 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.” (GeeksforGeeks, 2022). 

Scene 6

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. (www.w3schools.com, n.d.) 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.” (GeeksforGeeks, 2022)

Data Points Digital background. 2.2.	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. 

Scene 7

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

Data Points Digital background. List example in python list1 = ["eva", "mia", "nikki"] list2 = [6, 12, 18, 24, 30] list3 = ["car", "bus", "train"] print(list1) print(list2) print(list3). 

Scene 8

List example in python list1 = ["eva", "mia", "nikki"] list2 = [6, 12, 18, 24, 30] list3 = ["car", "bus", "train"] 	 print(list1) print(list2) print(list3)

Data Points Digital background. Append example names = ["eva", "mia", "nikki"] names.append("rebeca") print(names). 

Scene 9

Append example names = ["eva", "mia", "nikki"] names.append("rebeca") print(names)

Data Points Digital background. 3.	A stack ADT example. 

Scene 10

An example of an abstract 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 abstract because it gives an implementation-
independent view." (GeeksforGeeks, 2017) ADT'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.

Data Points Digital background. 11. 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. 

Scene 11

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

Data Points Digital background. 12. 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.. 

Scene 12

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.

Data Points Digital background. 13. 4.	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 .” (GeeksforGeeks, 2021). 

Scene 13

4.	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 .” (GeeksforGeeks, 2021)

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.

Data Points Digital background. 14. 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.. 

Scene 14

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.

Data Points Digital background. 15. 4.1.	Concrete data structure for a First In First out (FIFO) queue example. 

Scene 15

4.1.	Concrete data structure for a First In First out (FIFO) queue example

Enqueue(“Messi”) Dequeue() Enqueue(“C.Ronaldo”) Dequeue() Enqueue(“Mbappe”)

Data Points Digital background. 16. Results. C.Ronaldo. 

Scene 16

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.

Data Points Digital background. 17. 5.	Bubble sort. 

Scene 17

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.” (Vritika, 2018)For this reason this algorithm is regarded as less useful because it is more time consuming than other sorting algorithms.

Data Points Digital background. 18. 5.	Bubble sort example. 

Scene 18

The image below is an unsorted array. As  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.

Data Points Digital background. 19. 10 is compared to 11. As 10 is smaller than 11 it remains in place and the sort is complete. 

Scene 19

10 is compared to 11. As 10 is smaller than 11 it remains in place and the sort is complete

This was a simple example of a bubble sort where the array was sorting was complete in one iteration. If the array was more complicated the sort would begin a second iteration from the beginning, then a third iteration and so on until the array is sorted.

Data Points Digital background. 20. 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.” (Patel, 2022). 

Scene 20

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.” (Patel, 2022)

Data Points Digital background. 21. The quick sort is more useful than the bubble sort in terms of its industrial value and in terms that the yielding of faster results make it more productive. However, the coding is more complicated than the bubble sort. In addition, “It’s difficult to implement since it’s a recursive process, especially if recursion isn’t available.” (Patel, 2022) It also uses more memory than the bubble sort.. 

Scene 21

The quick sort is more useful than the bubble sort in terms of its industrial value and in terms that the yielding of faster results make it more productive. However, the coding is more complicated than the bubble sort. In addition, “It’s difficult to implement since it’s a recursive process, especially if recursion isn’t available.” (Patel, 2022) It also uses more memory than the bubble sort.

Data Points Digital background. 22. Quick sort example. 

Scene 22

Sub array 1              Pivot                  sub array 2

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.

Data Points Digital background. 23. 2 7 3 1 8 9 11 10 14 15. 

Scene 23

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.  T he pivot will be 3.

1 will go to the left of three and 7 will go to the right.

Data Points Digital background. 24. 1 2 3 7 8 9 11 10 14 15. 

Scene 24

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.

Data Points Digital background. 25. Dijkstra’s algorithm. 

Scene 25

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.

Figure 1: Weighted graph (Freecodecamp.org, 2022

Data Points Digital background. 26. 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.” (freeCodeCamp.org, 2020) The algorithm begins at the node of the users choosing and examine the graph to locate the shortest path. 

Scene 26

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.” (freeCodeCamp.org, 2020) The algorithm begins at the node of the users choosing and examine the graph to locate the shortest path

Data Points Digital background. 27. 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.. 

Scene 27

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.

Data Points Digital background. 28. A* Algorithm. 

Scene 28

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”  (Isaac Computer Science, n.d.) 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.

Data Points Digital background. 29. A* Algorithm. 

Scene 29

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.

Thank You. Presented by Theo Joseph. Data Points Digital background. 

Scene 30

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].. 

Scene 31

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. 

Scene 32

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.. 

Scene 33

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.