Data Structures and Algorithms: A Comprehensive Guide

Desklib provides solved assignments and past papers to help students succeed.

DATA STRUCTURE AND ALGORITHMS

Table of Contents
Introduction......................................................................................................................................3
LO1. Examine abstract data types, concrete data structure and algorithms....................................4
P1. Create a design specification for data structures explaining the valid operations that can be
carried out on the structures.........................................................................................................4
P2. Determine the operations of a memory stack and how it is used to implement function
calls in a computer.......................................................................................................................8
M1. Illustrate, with an example, a concrete data structure for a First in First out (FIFO) queue.
...................................................................................................................................................10
M2. Compare the performance of two sorting algorithms........................................................11
LO2. Specify abstract data types and algorithms in a formal notation..........................................12
P3. Using an imperative definition, specify the abstract data type for a software stack...........12
M3. Examine the advantages of encapsulation and information hiding when using an ADT.. 14
LO3. Implement complex data structures and algorithms.............................................................15
P4. Implement a complex ADT and algorithm in an executable programming language to
solve a well-defined problem.....................................................................................................15
P5. Implement error handling and report test results.....................................................................21
M4. Demonstrate how the implementation of an ADT/algorithm solves a well-defined
problem......................................................................................................................................22
LO4 Assess the effectiveness of data structures and algorithms...................................................25
P6. Discuss how asymptotic analysis can be used to assess the effectiveness of an algorithm.25
Asymptotic Annotations:...........................................................................................................25
P7. Determine two ways in which the efficiency of an algorithm can be measured, illustrating
your answer with an example....................................................................................................28
M5. Interpret what a trade-off is when specifying an ADT using an example to support your
answer........................................................................................................................................29
Conclusion.....................................................................................................................................30
References......................................................................................................................................31
2 | P a g e

Table of Figures
Figure 1: Flowchart..........................................................................................................................5
Figure 2: Data Flow Diagram..........................................................................................................6
Figure 3: Class Diagram..................................................................................................................6
Figure 4: Singly Linked List............................................................................................................7
Figure 5: Doubly Linked List..........................................................................................................7
Figure 6: Circular Linked List.........................................................................................................7
Figure 7: Stack Data Structure.........................................................................................................9
Figure 8: Queue Data Structure.....................................................................................................11
Figure 9: Program 1.......................................................................................................................16
Figure 10: Program 2.....................................................................................................................17
Figure 11: Program 3.....................................................................................................................18
Figure 12: Program 4.....................................................................................................................19
Figure 13: Program 5.....................................................................................................................20
Figure 14: Program 6.....................................................................................................................21
Figure 15: Error handling..............................................................................................................22
Figure 16: Console of Program......................................................................................................23
Figure 17: Adding an element in a queue......................................................................................23
Figure 18: Printing Available Jobs................................................................................................24
Figure 19: Print Next Job...............................................................................................................24
Figure 20: Total count of present Jobs..........................................................................................24
Figure 21: Clear all Jobs................................................................................................................25
Figure 22: Error message that list is empty...................................................................................25
Figure 23: Big-Oh Notation...........................................................................................................26
Figure 24: Omega Notation...........................................................................................................27
Figure 25: Theta Notation..............................................................................................................27
Figure 26: list of Asymptotic Notations........................................................................................28
Figure 27: Space Complexity........................................................................................................29
Figure 28: Time Complexity.........................................................................................................29
List of Tables
Table 1: Comparison between Selection sort and Heap sort.........................................................12
Table 2: Functions of List ADT.....................................................................................................13
Table 3: Queue ADT.....................................................................................................................13
Table 4: Stack ADT.......................................................................................................................13
3 | P a g e

Introduction
The algorithm is the type of data structure used for solving the problems in the regular formation.
In the overall scenario, the algorithm was also discussed in brief with the design specification
with valid operations such as flow chart, linked list and many other. In the next part, stack and
queue structure will also be discussed with the help of their functionalities and their behavior.
After that, the program of queue structure will be developed for better understanding of the
queue formation.
4 | P a g e

LO1. Examine abstract data types, concrete data structure, and algorithms.
P1. Create a design specification for data structures explaining the valid operations
that can be carried out on the structures.
Data Structure: It is the structure of organizing and storing the data or information that will be
used effectively and efficiently. In computer programming, the data structure was designed or
selected for storing data with the help of numerous algorithms. There are many types of data
structure that includes pointers, array, linked list, structure, stack, queue, searching, sorting,
graph, programs and many more. There were some operations were used in the design
specification for the data structure:
- Flowchart: It is the graphical representation of the processed steps of the algorithm. The
steps in the flowchart were shown in the boxes of numerous types with their order for
connecting with the arrows.
Figure 1: Flowchart
(Source: Visual-paradigm, 2019)
In the above diagram, various shapes of flowchart were made with their different kinds of
conventional meanings.
- Data Flow Diagram: It is the form for representing the data flow of the system or the
process. It provides the information for the inputs and the outputs of every process and
the entity itself.
5 | P a g e

Figure 2: Data Flow Diagram
(Source: Lucidchart, 2019)
- Class Diagram: It is the UML diagram which is the type of the static diagram which
describes the system structure for showing classes of system, operations and the attributes
among objects.
Figure 3: Class Diagram
(Source: Medium, 2017)
6 | P a g e

Linked List: It is the linear structure of the data elements where every element is the separate
objects. It is used to store data elements with the use of their pointers. Linked list are three types,
such as Singly Linked List, Doubly Linked List and Circular Linked List (Fouss, et al., 2016).
Singly Liked List: In this type of linked list, the data elements or the list items will navigate in
the forward direction only.
Figure 4: Singly Linked List
(Source: HackerEarth, 2019)
Doubly Linked List: In this type of linked list, the data elements or the list items will navigate
in both directions as the backward and forward direction.
Figure 5: Doubly Linked List
(Source: javatpoint, 2019)
Circular Linked List: In this linked list, the first element having the link with the next element
and last with the previous element.
Figure 6: Circular Linked List
(Source: javatpoint, 2019)
7 | P a g e

Pseudo Code: It is the informal formation of the description of programming which didn’t
require any type of programming language. It is basically used to generating the outline of the
program before implementing the program. The sketch of the programs was designed with the
help of the algorithm.
Advantage of Pseudo Code:
- It was understood by all types of programmers.
- It can’t be compiled in the executable program.
- It enables the programmers to concrete on the part of the algorithm development code.
8 | P a g e

P2. Determine the operations of a memory stack and how it is used to implement
function calls in a computer.
Memory Stack: it is the container of the objects which is removed and inserted with the help of
the LIFO principle as Last-In-First-Out. It serves the collection of elements with 2 principle
operations such as push operation and pop operation. In each time, the element will be added,
and it will move to the top position of the stack and the top-most element will be removed in the
stack.
There are some features for Memory Stack:
- It is the LIFO structure and also called as FILO as First in Last Out.
- It is of similar data types in the ordered list.
- In stack, the pop function used for removing elements and push function is used for
adding elements.
- When the stack is full than it is in the Overflow state and when it is empty then it is in the
Underflow state.
- Insertion and deletion were done from the top of the stack only.
Some applications of Memory Stack are:
- Expression Conversion such as Postfix-Prefix & Infix-Postfix.
- Parsing
Stack Implementation
With the help of the linked list and the array, the stack will be implemented easily. Size of the
array is limited or fixed whereas the linked list size is not limited. There were 2 operations used
for implementing the stack data structure, such as PUSH and POP operations.
Figure 7: Stack Data Structure
9 | P a g e

(Source: Studytonight, 2019)
Algorithms of the Stack Operations:
- PUSH Operation:
 First, it will check that the stack was overloaded or not.
 If the stack is overloaded, then print overflow errors and exit running program.
 If stack not overloaded, then the top element will be increased with adding an
element.
- POP Operation:
 First, it will check where the space in the stack or not.
 If the stack is not overloaded, then-then it will print that the stack is underflow
and the program will be an exit.
 If the stack is overloaded, then it will print the top element.
10 | P a g e

M1. Illustrate, with an example, a concrete data structure for a First in First out
(FIFO) queue.
Queue: Queue is the linear type of where element insertion and the deletion activities were
performed in different endpoints. Both ends were known as FRONT and REAR, where, Front
end is used when the element is to be deleted and the Rear end is used when the element is to be
inserted in the queue formation. The queue is so similar with the stack, but the main difference is
that the Queue follows the FIFO (First In First Out) principle and the Stack follows the LIFO
(Last In First Out) principle.
In the queue, there were two functions used for inserting and deleting elements. The two
functions were enqueued () and dequeue ().
Figure 8: Queue Data Structure
(Source: Tutorialride, 2019)
- Enqueue: This function is used for inserting the data elements into the queue formation.
- Dequeue: This function is used for deleting the data elements from the queue formation.
Example of Queue Data Structure
The best or the live example for queue formation is the line of the students in the schools,
colleges or any other educational places. The line formation will work on the one on one process
where the first person will be treated first and the last one will be treated as last. It uses the FIFO
principle where the first person is treated at the very beginning and the last will be treated as the
last person.
11 | P a g e

M2. Compare the performance of two sorting algorithms.
The sorting algorithm is the algorithm which is used for rearranging the data elements that were
listed with the help of array according to the operators. The operators for comparison was used
for deciding the new or the latest order of the elements in the other data structure. The order was
sorted with the help of ASCII values.
There were many kinds of sorting algorithms such as:
- Selection sort: This sorting algorithm considers only ascending order where it finds the
smallest element in the array.
- Insertion sort: This sorting algorithm works like sorting the cards while playing.
- Bubble sort: This sorting algorithm consider the swapping the elements for arranging in
the correct order.
- Merge sort: This sorting algorithm used the principle as “Divide & Conquer” where the
array was divided into two parts while arranging elements.
- Heap sort: This sorting algorithm finds the largest element in the array and places it to
the last position or end of the array.
Table 1: Comparison between Selection sort and Heapsort
Type of
Comparison
Selection Sort Heap Sort
Basic In this, the element will be first
selected and then swapped in
ascending order.
In this, it will select the largest
element and then place it to the last
position.
Efficiency No Yes
Stability Yes No
Method Selection Heap
The time
complexity of
the best case
O (n2) O (n2)
12 | P a g e