Higher Nationals

Internal verification of assessment decisions – BTEC (RQF)

INTERNAL VERIFICATION – ASSESSMENT DECISIONS

Programme title Higher National Diploma in Computing

Assessor Internal Verifier

Unit 19 – Data Structures and Algorithms
Unit(s)
Specification, Implementation, and Assessment of Data Structures for a sample
Assignment title
scenario.

Gavindya sasanthi wanniarachchi

Student’s name

List which assessment criteria Pass Merit Distinction

the Assessor has awarded.

INTERNAL VERIFIER CHECKLIST

Do the assessment criteria awarded match

those shown in the assignment brief? Y/N

Is the Pass/Merit/Distinction grade awarded

justified by the assessor’s comments on the
Y/N
student work?

Has the work been assessed

Y/N
accurately?
Is the feedback to the student:
Give details:
• Constructive?
• Linked to relevant assessment criteria? Y/N
• Identifying opportunities for Y/N
improved performance? Y/N
• Agreeing actions? Y/N
Does the assessment decision need
Y/N
amending?

Assessor signature Date

Internal Verifier signature Date

Programme Leader signature (if required)
Date
 Confirm action completed
Remedial action taken

Give details:

Assessor signature Date

Internal Verifier
Date
signature
Programme Leader
Date
signature (if required)
Higher Nationals - Summative Assignment Feedback Form
Student Name/ID COL/E-011789
Unit Title Unit 19: Data Structures and Algorithms

Assignment Number 1 Assessor

Date Received 1st
Submission Date submission
Date Received 2nd
Re-submission Date submission
Assessor Feedback:
LO1 Examine different concrete data structures and it’s valid operations.
Pass, Merit & P1 P2 M1 M2 D1
Distinction Descripts

LO2 Discuss the advantages, complexity of Abstract Data Type and importance concepts of
Object orientation.

Pass, Merit & P3 M3 D2

Distinction Descripts

LO3 Implement, Demonstrate and evaluate complex ADT algorithm.

Pass, Merit & P4 P5 M4 D3

Distinction Descripts

LO4 Examine the advantages of Independent data structures and discuss the need of
asymptotic analysis to assess the effectiveness of an algorithm.
Pass, Merit & P6 P7 M5 D4
Distinction Descripts

Grade: Assessor Signature: Date:

Resubmission Feedback:
 Grade: Assessor Signature: Date:
Internal Verifier’s Comments:
Signature & Date:
* Please note that grade decisions are provisional. They are only confirmed once internal and external moderation has taken place and
grades decisions have been agreed at the assessment board.

Assignment Feedback
Formative Feedback: Assessor to Student

Action Plan

Summative feedback

Feedback: Student to Assessor

Assessor signature Date

Student signature Date

Pearson Higher Nationals in

Computing
Unit 19: Data Structures & Algorithms
Assignment 01
General Guidelines

• A Cover page or title page – You should always attach a title page to your assignment. Use previous
page as your cover sheet and make sure all the details are accurately filled.

• Attach this brief as the first section of your assignment.

• All the assignments should be prepared using a word processing software.

• All the assignments should be printed on A4 sized papers. Use single side printing.

• Allow 1” for top, bottom , right margins and 1.25” for the left margin of each page.

Word Processing Rules

• The font size should be 12 point, and should be in the style of Time New Roman.

• Use 1.5 line spacing. Left justify all paragraphs.

• Ensure that all the headings are consistent in terms of the font size and font style.

• Use footer function in the word processor to insert Your Name, Subject, Assignment No, and
Page Number on each page. This is useful if individual sheets become detached for any reason.

• Use word processing application spell check and grammar check function to help editing your
assignment.

Important Points:

• It is strictly prohibited to use textboxes to add texts in the assignments, except for the compulsory
information. eg: Figures, tables of comparison etc. Adding text boxes in the body except for the
before mentioned compulsory information will result in rejection of your work.
 • Carefully check the hand in date and the
instructions given in the assignment. Late
submissions will not be accepted.

• Ensure that you give yourself enough time to complete the assignment by the due date.

• Excuses of any nature will not be accepted for failure to hand in the work on time.

• You must take responsibility for managing your own time effectively.

• If you are unable to hand in your assignment on time and have valid reasons such as illness, you
may apply (in writing) for an extension.

• Failure to achieve at least PASS criteria will result in a REFERRAL grade .

• Non-submission of work without valid reasons will lead to an automatic RE FERRAL. You will then
be asked to complete an alternative assignment.

• If you use other people’s work or ideas in your assignment, reference them properly using
HARVARD referencing system to avoid plagiarism. You have to provide both in-text citation and
a reference list.

• If you are proven to be guilty of plagiarism or any academic misconduct, your grade could be
reduced to A REFERRAL or at worst you could be expelled from the course
Student Declaration

I hereby, declare that I know what plagiarism entails, namely to use another’s work and to present it as
my own without attributing the sources in the correct form. I further understand what it means to copy
another’s work.

• I know that plagiarism is a punishable offence because it constitutes theft.

• I understand the plagiarism and copying policy of Edexcel UK.
• I know what the consequences will be if I plagiarise or copy another’s work in any of the
assignments for this program.
• I declare therefore that all work presented by me for every aspect of my program, will be my own,
and where I have made use of another’s work, I will attribute the source in the correct way.
• I acknowledge that the attachment of this document signed or not, constitutes a binding
agreement between myself and Pearson, UK.
• I understand that my assignment will not be considered as submitted if this document is not
attached to the assignment.

Student’s Signature: Date:

(Provide E-mail ID) (Provide Submission Date)
Higher National Diploma in Business
Assignment Brief
Student Name /ID Number
Unit Number and Title Unit 19 : Data Structures and Algorithms
Academic Year 2021/22
Unit Tutor
Assignment Title Specification, Implementation, and Assessment of Data Structures for a
sample scenario.
Issue Date
Submission Date
IV Name & Date

Submission format

The submission should be in the form of a report, which contains code snippets (which must
be described well), text-based descriptions, and diagrams where appropriate. References to
external sources of knowledge must be cited (reference list supported by in-text citations)
using the Harvard Referencing style.

Unit Learning Outcomes:

LO1. Examine abstract data types, concrete data structures and algorithms.
LO2. Specify abstract data types and algorithms in a formal notation.
LO3. Implement complex data structures and algorithms.
LO4. Assess the effectiveness of data structures and algorithms.

Assignment Brief and Guidance:

Scenario
ABC Pvt Ltd organizing Car Racing event across western province and they decided to have
maximum of 6 cars(participants) to compete.
There are totally 3 Rounds and at the end of each round lowest rank car will be eliminated
from the Race.
Each car has unique number, brand, sponsor and driver details.

In order to manage this particular event ABC Pvt Ltd decided to develop an Application.
Application functions are listed down.

[Link] Car Details

[Link] a car
[Link] 3 Rounds Results.
[Link] out the winners (1st,2nd,3rd)
[Link] for a particular car

Task 1: Examine and create data structure by simulating the above scenario and explain the
valid operations that can be carried out on this data structure.
Determine the operations of a queue and critically review how it is used to implement
function calls related to the above scenario.

Task 2: Implement the above scenario using the selected data structure and its valid
operations for the design specification given in task 1 by using java programming. Use
suitable error handling and Test the application using suitable test cases and illustrate the
system. Provide evidence of the test cases and the test results.

Task 3 : Registered Car details are stored from oldest to newest. Management of ABC Pvt Ltd
should be able to find from the newest to oldest registered car details. Using an imperative
definition, specify the abstract data type for the above scenario and implement specified ADT
using java programming and briefly discuss the complexity of chosen ADT algorithm. List
down the advantages of Encapsulation and Information hiding when using an ADT selected
for the above scenario.
“Imperative ADTs are basis for object orientation.” Discuss the above view stating whether
you agree or not. Justify your answer.

Task 4: ABC Pvt Ltd plans to visit all of these participants through the shortest path within a
day.
Analyse the above operation by using illustrations, of two shortest path algorithms, specify
how it operates using a sample graph diagram. Sort the cars based on numbers with two
different sorting algorithms and critically review the performances of those two algorithms
by comparing them.

Task 5: Evaluate how Asymptotic analysis can be used to assess the effectiveness of an
algorithm and critically evaluate the different ways in which the efficiency of an algorithm
can be measured.
Critically review the sort of trade-offs exists when you use an ADT for implementing
programs. You also need to evaluate the benefits of using independent data structures for
implementing programs.
Grading Rubric

Grading Criteria Achieved Feedback

LO1. Examine abstract data types, concrete

data structures and algorithms.

P1 Create a design specification for data

structures explaining the valid operations that
can be carried out on the structures.

P2 Determine the operations of a memory

stack and how it is used to implement
function calls in a computer.
M1 Illustrate, with an example, a concrete
data structure for a First In First out (FIFO)
queue.

M2 Compare the performance of two sorting

algorithms.
D1 Analyse the operation, using illustrations,
of two network shortest path algorithms,
providing an example of each.

LO2. Specify abstract data types and

algorithms in a formal notation.

P3 Using an imperative definition, specify

the abstract data type for a software stack.

M3 Examine the advantages of

encapsulation and
information hiding when using an ADT.

D2 Discuss the view that imperative ADTs are

a basis for object orientation and, with
justification, state whether you agree.
LO3. Implement complex data structures and
algorithms.

P4 Implement a complex ADT and algorithm

in an executable programming language to
solve a well-defined problem.

P5 Implement error handling and report test

results.

M4 Demonstrate how the implementation of

an ADT/algorithm solves a well-defined
problem.
D3 Critically evaluate the complexity of an
implemented ADT/algorithm.
LO4. Assess the effectiveness of data
structures and algorithms.
P6 Discuss how asymptotic analysis can be
used to assess the effectiveness of an
algorithm.

P7 Determine two ways in which the

efficiency of an algorithm can be measured,
illustrating your answer with an example.
 M5 Interpret what a trade-off is when
specifying an ADT using an example to
support your answer.

D4 Evaluate three benefits of using

implementation independent data
structures.

Table of Contents

Abstract Data Types ................................................................................................................................ 28

ADT stands for Abstract Data Type, which is a type (or class) for objects whose behavior is specified by
a collection of values and actions. .......................................................................................................... 28
array ........................................................................................................................................................ 29
 Introduction to Arrays ............................................ 30
Array’s size.................................................................................................. 31
Types of indexing in an array: ........................................................................................................ 31
Advantages of using arrays: ............................................................................................................ 32
Disadvantages of using arrays: ....................................................................................................... 32
Java Array List .................................................................................................................................... 34
Syntax ................................................................................................................................................. 35
The Structure of an Array in Memory is depicted in this diagram. .................................................... 35
data structures ........................................................................................................................................ 36
1. List ADT ......................................................................................................................................... 36
Representing Link list ................................................................................................................................. 40
Basic Procedures ......................................................................................................................................... 41
Insertion Operation ..................................................................................................................................... 41
Deletion Operation ...................................................................................................................................... 42
Revers Operation ........................................................................................................................................ 42
2. Stack ADT ...................................................................................................................................... 44
Stack Representation ................................................................................................................................... 46
The Stack is used for the two basic processes listed below. ....................................................................... 46
Push Operation ............................................................................................................................................ 47
Pop Operation ............................................................................................................................................. 48
Peek () Operation ........................................................................................................................................ 50
Is Full () Operation...................................................................................................................................... 50
IsEmpty () Operation .................................................................................................................................. 50
3. Queue ADT ..................................................................................................................................... 51
Queue Representation ................................................................................................................................. 54
Basic Operation........................................................................................................................................... 55
Enqueue Operation...................................................................................................................................... 56
Dequeue Operation ..................................................................................................................................... 57
3. Doubly Linked List ......................................................................................................................... 60
Basic Operations ......................................................................................................................................... 61
Insertion Operation ..................................................................................................................................... 62
Deletion Operation ...................................................................................................................................... 63
 Insertion at the End of an Operation ...................... 64
Advantages over singly linked list ........................ 65
Disadvantages over singly linked list ........................................................................................................ 66
Tree ......................................................................................................................................................... 66
Representing Tree ............................................................................................................................... 67
Tree Terms .......................................................................................................................................... 67
Binary Tree ......................................................................................................................................... 69
Advantages .......................................................................................................................................... 69
There is some type of binary tree. ....................................................................................................... 69
Why we use binary tree....................................................................................................................... 70
Unbalanced Tree ................................................................................................................................. 70
Implementing the binary tree .............................................................................................................. 72
The Node classes......................................................................................................................................... 72
The Tree Class ............................................................................................................................................ 72
The Tree app Class...................................................................................................................................... 73
Finding a Node............................................................................................................................................ 74
Inserting a Node .................................................................................................................................. 75
Advantages of Tree ............................................................................................................................. 76
Disadvantages of tree .......................................................................................................................... 77
Graph ...................................................................................................................................................... 78
Types of Graph ........................................................................................................................................... 79
Directed Graph.......................................................................................................................................... 82
Undirected Graph ..................................................................................................................................... 83
Other types of graphs ............................................................................................................................... 83
Differences between the Linear data structure and non-linear data structure. ............................................ 83
non-linear data structure. ............................................................................................................................ 84
(Anon., n.d.) ........................................................................................................................................ 85
Memory................................................................................................................................................... 85
How the Stack is working in a RAM .................................................................................................. 85
Why we need a RAM (Random Access Memory)...................................................................................... 85
Static Memory Layout ........................................................................................................................ 88
 Text/Code Segment ................................................ 90
Initialized Data Segment ........................................ 93
Uninitialized Data Segment (BSS) ............................................................................................................. 95
Dynamic Memory Layout ................................................................................................................... 96
Stack............................................................................................................................................................ 97
Stack Memory Layout............................................................................................................................... 104
Stack Error Conditions .............................................................................................................................. 106
Heap .......................................................................................................................................................... 108
What Is First In, First Out (FIFO)? .............................................................................................. 110
First In, First Out (FIFO) is an asset management and valuation strategy in which the first assets
created or acquired are sold, utilised, or disposed of. ....................................................................... 110
FIFO posits that the assets with the oldest expenses are included in the cost of goods sold on the
income statement for tax reasons (COGS). The remaining inventory assets are compared to the most
recently acquired or manufactured assets. ........................................................................................ 110
Advantages of FIFO ........................................................................................................................ 111
Disadvantages of FIFO ................................................................................................................... 111
Car application ...................................................................................................................................... 112
Cord................................................................................................................................................... 112
ADT Immolation ............................................................................................................................... 135
pest plan ............................................................................................................................................ 138
test case ............................................................................................................................................. 139
Abstract Data Types .............................................................................................................................. 142
Stack.................................................................................................................................................. 143
Data Structure - Stack ....................................................................................................................... 143
peek() ........................................................................................................................................................ 144
Push Operation .......................................................................................................................................... 145
Pop Operation ........................................................................................................................................... 146
Queue ................................................................................................................................................ 148
List .................................................................................................................................................... 148
Specifications of the ADT................................................................................................................. 148
 Specification of SDL ............................................ 149
Encapsulation .............................................................................................. 150
Encapsulation Advantages ........................................................................................................................ 150
Encapsulation Disadvantages .................................................................................................................... 151
Data Hiding ....................................................................................................................................... 151
Advantages of Data Hiding ....................................................................................................................... 152
Disadvantages of Data Hiding .................................................................................................................. 153
Benefits of ADTs .............................................................................................................................. 153
What is object-oriented programming (OOP)?..................................................................................... 155
Object ................................................................................................................................................ 155
Class .................................................................................................................................................. 155
Object-Oriented Programming and its correlation with ADT? ......................................................... 156
Correlation between OOP and ADT ......................................................................................................... 159
Performance of different sorting Algorithms ....................................................................................... 160
Operations of Shortest Path Algorithm ................................................................................................ 162
Types of Shortest Path Algorithms ....................................................................................................... 164
Algorithms ............................................................................................................................................. 166
Bellman-Ford algorithm............................................................................................................................ 166
Dijkstra's algorithm ................................................................................................................................... 167
topological sort.......................................................................................................................................... 167
Floyd-Warshall algorithm ......................................................................................................................... 168
Johnson's algorithm................................................................................................................................... 168
Comparison of Algorithms ....................................................................................................................... 169
sorting algorithm ............................................................................................................................... 170
types of sorting algorithms ........................................................................................................................ 170
What is ASN.1 .................................................................................................................................. 172
Abstract Data types ........................................................................................................................... 173
Specifying abstract data types for a software stack .......................................................................... 174
Efficiency of an algorithm ................................................................................................................ 175
Method for determining Efficiency........................................................................................................... 176
 Space-Time tradeoff ............................................. 177
Asymptotic Analysis ............................................. 177
Asymptotic Notations ....................................................................................................................... 178
Common Asymptotic Notations ............................................................................................................... 181
Abstract data types ............................................................................................................................ 182
What is trade-off when specifying ADT ........................................................................................... 182
Benefits of using implementation independent data structures ......................................................... 183
Time-Space Trade-Off in Algorithms ............................................................................................... 183
Exception Handling .......................................................................................................................... 186
Java exceptions come in several forms. ............................................................................................ 186
Which data structure can be used, when simulating the above scenario? ......................................... 188
What are the valid operations that can be carried out on this data structure? ................................... 188
Demonstrate how the implementation of an ADT/algorithm solves the above problem. ................. 188
An object orientation is a tool that allows a computer program to interact with the so-called modes of
other objects to generate the program's behavior. It simplifies, reads, and programmable
programming. Object orientation is the basis for a variety of ADTs. Do you agree? Justify ........... 189
Last out (LIFO) ......................................................................................................................................... 190
What sort of trade-offs exists when you use a ADT for implementing programs?........................... 191
Re-calculation of vision tables .................................................................................................................. 191
Compressed data ....................................................................................................................................... 192
Smaller code and loop unrolling ............................................................................................................... 192
Describe the benefits of using independent data structures for implementing programs. ................ 192
Benefit ....................................................................................................................................................... 192
Difficulties ................................................................................................................................................ 193
Conclusion ........................................................................................................................................ 193
References ............................................................................................................................................ 193

Figure 1 Abstract Data Types ....................................................................................................... 29

Figure 2 array ................................................................................................................................ 30

 Figure 3 array .................................................. 32

Figure 4 array EXAMPLE ............................................................................................................ 34

Figure 5 Array List........................................................................................................................ 35

Figure 6 Syntax ............................................................................................................................. 35

Figure 7 The Structure of an Array in Memory is depicted in this diagram. ................................ 36

Figure 8 List ADT ......................................................................................................................... 37

Figure 9 List ADT ......................................................................................................................... 38

Figure 10 list of ADT ................................................................................................................... 39

Figure 11 Representing Link list................................................................................................... 41

Figure 12 Insertion Operation ....................................................................................................... 42

Figure 13 Deletion Operation ....................................................................................................... 42

Figure 14 Revers Operation .......................................................................................................... 43

Figure 15 Stack ADT .................................................................................................................... 44

Figure 16 Stack ADT .................................................................................................................... 45

Figure 17 Stack Representation .................................................................................................... 46

Figure 18 Push Operation ............................................................................................................. 48

Figure 19 Pop Operation ............................................................................................................... 49

Figure 20 Peek () Operation .......................................................................................................... 50

 Figure 21 Is Full () Operation ......................... 50

Figure 22 IsEmpty () Operation .................................................................................................... 51

Figure 23 Queue ADT .................................................................................................................. 52

Figure 24 Queue ADT .................................................................................................................. 53

Figure 25 Queue ............................................................................................................................ 55

Figure 26 Enqueue Operation ....................................................................................................... 57

Figure 27 Dequeue Operation ....................................................................................................... 58

Figure 28 Doubly Linked List....................................................................................................... 60

Figure 29 Doubly Linked List....................................................................................................... 62

Figure 30 Insertion Operation ....................................................................................................... 63

Figure 31 Deletion Operation ....................................................................................................... 64

Figure 32 Insertion at the End of an Operation............................................................................. 65

Figure 33 Representing Tree ......................................................................................................... 67

Figure 34 The Node classes .......................................................................................................... 72

Figure 35 The Tree Class .............................................................................................................. 73

Figure 36 The Tree app Class ....................................................................................................... 74

Figure 37 Finding a Node ............................................................................................................. 75

Figure 38 Graph ............................................................................................................................ 79

 Figure 39 Types Graph ................................... 80

Figure 40 graph ............................................................................................................................. 81

Figure 41 graph ............................................................................................................................. 82

Figure 42 memory ......................................................................................................................... 88

Figure 43 Static Memory Layout .................................................................................................. 89

Figure 44 Static Memory Layout .................................................................................................. 90

Figure 45 Text/Code Segment ...................................................................................................... 92

Figure 46 Text/Code Segment ...................................................................................................... 93

Figure 47 Initialized Data Segment .............................................................................................. 94

Figure 48 Initialized Data Segment .............................................................................................. 94

Figure 49 Uninitialized Data Segment (BSS) ............................................................................... 95

Figure 50 Uninitialized Data Segment (BSS) ............................................................................... 96

Figure 51 Dynamic Memory Layout ............................................................................................ 97

Figure 52 Stack ............................................................................................................................. 98

Figure 53 Stack ............................................................................................................................. 99

Figure 54 stack ............................................................................................................................ 100

Figure 55 stack ............................................................................................................................ 101

Figure 56 stack ............................................................................................................................ 102

 Figure 57 stack .............................................. 103

Figure 58 stack ............................................................................................................................ 104

Figure 59 Stack Memory Layout ................................................................................................ 105

Figure 60 Stack Error Conditions ............................................................................................... 107

Figure 61 Heap ............................................................................................................................ 109

Figure 62 bbi 1 ............................................................................................................................ 112

Figure 63 bbl 2 ............................................................................................................................ 113

Figure 64 main 1 ......................................................................................................................... 114

Figure 65 main 2 ......................................................................................................................... 115

Figure 66 main 3 ......................................................................................................................... 116

Figure 67 main 4 ......................................................................................................................... 117

Figure 68 main 5 ......................................................................................................................... 118

Figure 69 quilksort 1 ................................................................................................................... 119

Figure 70 quicksort2 ................................................................................................................... 120

Figure 71 quicksort 3 ................................................................................................................. 121

Figure 72 quicksort 4 ................................................................................................................. 122

Figure 73 Queue 1 ....................................................................................................................... 123

Figure 74 Queue 1 ....................................................................................................................... 124

 Figure 75 Queue 2 ......................................... 125

Figure 76 Queue 3 ....................................................................................................................... 126

Figure 77 QueueOfStacks 1 ........................................................................................................ 127

Figure 78 QueueOfStacks2 ......................................................................................................... 128

Figure 79 QueueOfStacks 3 ........................................................................................................ 129

Figure 80 QueueOfStacks 4 ........................................................................................................ 130

Figure 81 QueueOfStacks 5 ........................................................................................................ 131

Figure 82 stack 1 ......................................................................................................................... 132

Figure 83 stack 2 ......................................................................................................................... 133

Figure 84 stack 3 ......................................................................................................................... 134

Figure 85 stack 4 ......................................................................................................................... 135

Figure 86 ADT Immolation ........................................................................................................ 136

Figure 87 ADT Immolation ........................................................................................................ 137

Figure 88 ADT Immolation ........................................................................................................ 137

Figure 89 ADT Immolation output ............................................................................................. 138

Figure 90 peek() .......................................................................................................................... 144

Figure 91 peek() .......................................................................................................................... 144

Figure 92 Algorithm of isfull() function ..................................................................................... 145

 Figure 93 Algorithm for PUSH Operation.... 145

Figure 94 Algorithm for PUSH Operation.................................................................................. 146

Figure 95 Algorithm for Pop Operation...................................................................................... 147

Figure 96 Algorithm for Pop Operation...................................................................................... 147

Figure 97 Performance of different sorting Algorithms ............................................................. 161

Figure 98Performance of different sorting Algorithms .............................................................. 162

Figure 99Operations of Shortest Path Algorithm ....................................................................... 163

Figure 100 Single-source ............................................................................................................ 165

Figure 101 All-pairs .................................................................................................................... 166

Figure 102 Johnson's algorithm .................................................................................................. 169

Figure 103 Comparison of Algorithms ....................................................................................... 169

Figure 104 Big Oh Notation, Ο................................................................................................... 179

Figure 105 Omega Notation, Ω................................................................................................... 180

Figure 106 Theta Notation, θ ...................................................................................................... 181

Figure 107 Common Asymptotic Notations ............................................................................... 182

Figure 108 Common Asymptotic Notations ............................................................................... 182

Table 1 Differences between the Linear data structure and non-linear data structure. ................. 85
 Table 2 pest plan ........................................... 139

Table 3 test case .......................................................................................................................... 140

Table 4 test case .......................................................................................................................... 140

Abstract Data Types

ADT stands for Abstract Data Type, which is a type (or class) for objects whose behavior is
specified by a collection of values and actions.

The definition of ADT merely specifies what operations are to be carried out, not how they will
be carried out. It makes no mention of how data will be stored in memory or which algorithms
will be employed to carry out the actions. It's named "abstract" because it provides a view that is
independent of implementation. Abstraction is the technique of delivering only the basics while
concealing the subtleties.
Figure 1 Abstract Data Types

The user of a data type does not need to understand how that data type is implemented; for
example, we have been using primitive values such as int, float, and char data types solely on the
basis of the fact that they can operate and be performed on without knowing how they are
implemented. As a result, a user just has to know what a data type can accomplish, not how it
will be used. Consider ADT as a black box that conceals the data type's underlying structure and
design. We'll now define three ADTs: List ADT, Stack ADT, and Queue ADT.

array
 Introduction to Arrays

A collection of objects stored in contiguous memory areas is known as an array. The concept is
to keep similar goods together. This simplifies the calculation of each element's position by
simply adding an offset to a base value, such as the memory address of the array's first member
(generally denoted by the name of the array). Index 0 is the starting point, and the offset is the
difference between the two. For the sake of simplicity, imagine an array as a flight of stairs with
a value (let's say one of your friends) on each level. You may use this to locate any of your pals
merely by knowing how many steps they have taken.

"The location of the next index is determined by the data type we employ," keep in mind.

Figure 2 array

The image above depicts a top-down perspective of a staircase from the bottom. The index of
each element in the array may be used to identify it (in a similar way as you could identify your
friends by the step on which they were on in the above example).
Array’s size

In the C programming language, an array has a fixed size, which means that once the size is set,
it cannot be modified, i.e. it cannot be shrunk or expanded. The rationale for this was because
while expanding, we can't always be sure (it's not always feasible) that we'll obtain the following
memory address as free. The shrinking won't work since the array is RAM statically allocated
when it's defined, and the compiler is the only one who can remove it.

Types of indexing in an array:

 0 (zero-based indexing): A subscript of 0 is used to index the array's initial element.

 1 (one-based indexing): The subscript 1 is used to index the array's initial element.

 n (n-based indexing): An array's base index can be arbitrarily selected. Negative index
values are usually allowed in programming languages that support n-based indexing, and
other scalar data types such as enumerations or characters can be used as array indexes.
Figure 3 array

Advantages of using arrays:

 Arrays provide access to items at random. This allows for easier access to components
based on their location.
 Arrays provide improved cache locality, which improves speed significantly.
 Arrays use a single name to represent numerous data elements of the same kind.

Disadvantages of using arrays:

  Because of static memory allocation, you
cannot modify the array's size once it has been declared. Because
the pieces are stored in successive memory regions, insertions and deletions are tough,
and shifting is also expensive.
 There are some evident flaws in the implementation of the data structure Stack utilizing
array.
 Take a look at the stack's POP operation. This is the way the algorithm would work.

1. Look for a stack overflow.

2. Reduce the top by one.

So what we're doing is decrementing the pointer to the topmost element, which means we're
merely bounding our view, but that element is still there, occupying memory space. It would be
fine if you had a simple datatype, but the object of an array would consume a lot of RAM.

Examples –
Figure 4 array EXAMPLE

A string is often used to refer to an array of characters, whereas an array of ints or floats is
simply referred to as an array. (Anon., 2021)

Java Array List

The ArrayList class, which is part of the [Link] package, is a resizeable array.

The distinction between a built-in array and an ArrayList in Java is that an array's size cannot be
changed (you must construct a new array if you wish to add or remove members from it). An
ArrayList can have elements added or deleted at any time. (Anon., n.d.)
Figure 5 Array List

Syntax

Figure 6 Syntax

The Structure of an Array in Memory is depicted in this diagram.

Figure 7 The Structure of an Array in Memory is depicted in this diagram.

Basic Procedures

 Insertion creates a new element at the specified index.

 Deletion removes an element from the list at the specified index.
 Searches for an element using the specified index or value.

data structures

1. List ADT
 The data is usually saved in a list with a head structure that includes a count, pointers,
and the location of the comparison function that is used to compare the data in the list.
  A linked list's link can hold data called element.
 Next In a linked list, each link carries a link to the next link, which is called next.
 Linked List -A linked list is made up of connections that lead to the first link, which is
referred to as first.

Figure 8 List ADT

 The data node carries a data structure pointer as well as a self-referential pointer to the
next node in the list.
Figure 9 List ADT

 The following is a list of ADT functions:

Figure 10 list of ADT

A list is made up of components of the same kind that are sorted in a logical order, and it may be
used to accomplish the following actions.

 get() — Returns a specific element from a list at a specific point.

  insert() — Add a new entry to the list at any location.

 remove() – From a non-empty list, delete the first occurrence of any element.

 removeAt() – From a non-empty list, remove the entry at the provided place.

 replace() — Substitute another element for an element at any point.

 size() - Return the number of entries in the list using.

 isEmpty() – If the list is empty, this function returns true; otherwise, it returns false.

 isFull() – If the list is full, return true, otherwise false.

Representing Link list

Figure 11 Representing Link list

Basic Procedures

 Insertion inserts a new element at the start of the list.

 Deletion removes an element from the list the start of the list

 Displays the whole list of options.

 Searches for a certain element the key that has been provided

 Deletes an element with the Delete command provided the key

Insertion Operation
Figure 12 Insertion Operation

Deletion Operation

Figure 13 Deletion Operation

Revers Operation
Figure 14 Revers Operation

The following are some key considerations.

A link element named first appears in a Linked List.

 Each link has one or more data fields as well as a next link field.

 Using its next link, each link is connected to the next link.

 To indicate the conclusion of the list, the last link has a null link.
 2. Stack ADT

 Instead of storing data in each node, the pointer to data is saved in the Stack ADT
implementation.
 The software sets aside memory for the data and passes the address to the stack ADT.

Figure 15 Stack ADT

 The ADT encapsulates both the head node and the data nodes. Only the stack
pointer is visible to the calling function.
 A reference to the top of the stack and a count of the number of elements
presently on the stack are also included in the stack head structure.
Figure 16 Stack ADT
 Stack Representation

Figure 17 Stack Representation

Array, Structure, Pointer, and Linked List can all be used to create a stack. A stack can be either
fixed in size or dynamically resized. We'll use arrays to implement stack here, making it a fixed-
size stack implementation.

The Stack is used for the two basic processes listed below.

1. Push() — Pushing an element to the stack is what this function does.

2. Pop() removes an element from a list.
 the pile of things

 A Stack is a collection of components that are all of the same kind and are ordered in a
logical sequence. All actions are conducted at one end of the stack, which is the top of the
stack, and the following operations are possible:

 push() - Push an element to the top of the stack using the method.
 pop() - If the stack is not empty, removes and returns the element at the top.
 peek() - If the stack is not empty, returns the element at the top without deleting it.
 size() – Returns the stack's size in items.
 isEmpty() – If the stack is empty, this function returns true; otherwise, it returns false.
 If the stack is full, return true; otherwise, return false.

Push Operation

A Push Operation is the act of adding a new data piece to the stack. A multitude of stages are
involved in a push operation.

Step 1: Determines whether the stack is full.

Step 2: If the stack is full, an error is generated and the program is terminated.

Step 3: If the stack isn't yet full, increment top to point to the next available spot.

Step 4: Adds a data element to the stack's top position.

 Step 5 returns a positive result.

(Anon., n.d.)

Figure 18 Push Operation

Pop Operation

A Pop Operation occurs when you access stuff while it's being removed from the stack. Instead
of removing the data element, top is decremented to a lower place on the stack to refer to the
next item in an array implementation of pop(). Pop(), on the other hand, removes data elements
and dealslocates memory space in linked-list implementations.

The following are possible steps in a Pop operation:

 Checks to see if the stack is empty in the first
step.

Step 2: If the stack is empty, an error is generated and the program is terminated.

Step 3: If the stack isn't empty, it accesses the data element pointed to by top.

Step 4: Lowers top's value by one.

Step 5 has a positive outcome.

Figure 19 Pop Operation

 Peek () Operation

Figure 20 Peek () Operation

Is Full () Operation

Figure 21 Is Full () Operation

IsEmpty () Operation
Figure 22 IsEmpty () Operation

3. Queue ADT

 The queue abstract data type (ADT) is based on the stack abstract data type's fundamental
architecture.
Figure 23 Queue ADT

 Each node has a void reference to the data as well as a link pointer to the next queue
member. It is the job of the software to allocate memory for data storage.
Figure 24 Queue ADT

 A Queue is a collection of components of the same kind that are organized in a logical
sequence. Insertion occurs at the back end, whereas deletion occurs at the front. It is
possible to carry out the following actions:

 enqueue() - adds a new element to the queue's end.

 dequeue() - If the queue isn't empty, removes and returns the first entry.
  peek() - If the queue is not empty, returns the
queue's element without deleting it.

 size() - returns the queue's size in items.

 isEmpty() – If the queue is empty, this function returns true; otherwise, it returns false.

 If the queue is full, return true; otherwise, return false.

The specifications do not describe how these ADTs will be represented or how the operations
will be performed, as can be seen from these definitions. An ADT can be implemented in a
variety of methods, such as utilizing arrays, a singly linked list, or a doubly linked list. Arrays or
linked lists can also be used to implement stack ADT and Queue ADT.

(Anon., 2019)

Queue Representation

As we now know, we access both ends of the queue for various reasons. The diagram below
attempts to illustrate queue representation as a data structure.
Figure 25 Queue

As an illustration, consider the following queue.

A queue may be built with Arrays, Linked-lists, Pointers, and Structures, just like stacks. We'll
make queues out of a one-dimensional array for simplicity's sake.

Basic Operation

Initializing or establishing the queue, using it, and ultimately wiping it from memory are
examples of queue operations. We will attempt to comprehend the basic procedures related with
queues in this section.

1. enqueue() adds a new item to the queue (stores it).

2. remove(access) an item from the queue with dequeue().
 To make the above-mentioned queue action
more efficient, a few extra functions are necessary. This is the case.

peek() retrieves the first piece in the queue without deleting it.

isfull() determines whether or not the queue is full.

isempty() determines whether or not the queue is empty.

We always dequeue (or access) data in the queue using the front pointer, and we use the rear
pointer to enqueue (or store) data in the queue.

Let's start with the queue's supported functions.

Enqueue Operation

Front and back data pointers are maintained in queues. As a result, compared to stacks, its
activities are more challenging to implement.

To enqueue (insert) data into a queue, perform the following steps:

Step 1: Make sure the line isn't too long.

Step 2: If the queue is full, leave with an overflow error.

Step 3: If the queue isn't yet full, move the back cursor to the next available spot.

Step 4: Add a data element to the queue's back end.

 Return success in the fifth step.

Figure 26 Enqueue Operation

Dequeue Operation

Accessing data from the queue entails two steps: first, access the data where the front is pointing,
and then, following access, delete the data. To carry out a dequeue operation, complete the
following steps:
Check to see if the line is empty in the first place.

Step 2: If the queue is empty, leave with an underflow error.

Step 3: If the queue is not empty, access the data indicated by the front arrow.

Step 4: Move the front pointer to the next data element that becomes accessible. (Anon., n.d.)

Return success in step five.

Figure 27 Dequeue Operation

To do a dequeuer action, follow the procedures below:

1. Make sure the queue isn't full.

2. Produce an underflow error and quit if the queue is empty.

3. Access the data where front is pointing if the queue is not empty.

4. Move the front pointer to the next data element that is accessible.

5. Make a successful return.

To complete the above-mentioned queue process, a few more functions are necessary.

efficiency.

Peek() — Gets the element at the front of the queue without having to wait for it.
Getting rid of it

1. isFull() — Determines whether the queue is full.

2. isEmpty() – Determines whether the queue is empty.

3. Doubly Linked List

In comparison to Single Linked List, Doubly Linked List is a version of Linked List in which
navigation is easy in both directions, either forward or backward. The terminology used to
comprehend the notion of a doubly linked list are listed below.

 A linked list's links can each store an element, which is a kind of data.
 Next is a link to the next link in a linked list.
 Prev is a link to the previous link in a linked list.
 A Linked List is a collection of links that connect the first and final links.

Figure 28 Doubly Linked List

 Basic Operations

 Insertion adds a new element to the top of the list.

 Deletion removes an element from the list's beginning.

 Insert Last adds a new element to the list's end.

 Delete Last removes an element from the list's end.
 Insert After adds an element after a list item.
 Deletes an element from the list based on the key.
 Displays the entire list in a forward direction.
 Backward display shows the entire list in reverse order.
(Anon., n.d.)
Figure 29 Doubly Linked List

Insertion Operation
Figure 30 Insertion Operation

Deletion Operation
Figure 31 Deletion Operation

Insertion at the End of an Operation

Figure 32 Insertion at the End of an Operation

Advantages over singly linked list

 A DLL may be walked through both forward and backward.

 If a reference to the node to be destroyed is provided, the delete operation in DLL is more
efficient.
  Before a given node, we may rapidly insert a
new [Link] remove a node from a singly linked list, a reference to
the preceding node is required. The list is occasionally explored to acquire this preceding
node. Using the previous pointer in DLL, we can access the previous node.

Disadvantages over singly linked list

 Each and every DLL node Extra space is required for a preceding pointer. Although it is
feasible to implement DLL with a single pointer, it is not recommended (See this and
this).
 All actions need the maintenance of a prior pointer.

Tree

The edges connecting to the edges are reflected in the tree. We'll talk about binary trees,
sometimes known as binary search trees.

The binary tree is a type of database that is used to store data. A binary tree has a specific
location at either end that can have up to two offspring. A binary tree is made up of a sorted
sequence and the advantages of a linked list, such as a sorted queue search, the ability to insert or
remove items fast, and the fact that it is stored in a linked list.
 Representing Tree

Figure 33 Representing Tree

Tree Terms

 The succession of nodes along the edges of a tree is referred to as a path.

 Root refers to the node at the very top of the tree. Each tree has only one root and only
one path from the root node to any other node.
 Any node except the root has one edge that points upward to a node named parent.

 The node below a particular node that is related to it by its edge downward is referred to
as its kid node.

 The leaf node is defined as a node that does not have any children.

 Subtree A node's descendants are represented by a subtree.

 When control is on a node, visiting refers to examining the value of the node.

 Traversing involves going from one node to the next in a certain order.

 The generation of a node is represented by the level of a node. If the root node is at level
0, then its next child node is at level 1, and so on.

 Keys A key represents a node's value, on which a search operation for that node is to be
performed.
 Binary Tree

The nodes of a tree are a mixture. Each node is linked to the next. It's like to being a part of a
family. There are numerous persons in that family, all of them are nodes with similar
relationships. Nodes with the same relationship join together in this way.

Advantages

 The structural linkages in the data are reflected in the form of trees.

 To represent hierarchies, trees are utilized.

 Trees make insertion and searching more efficient.

 Trees are extremely adaptable data, allowing you to move subtrees around with ease.

There is some type of binary tree.

 Binary Tree.
 Fully (Perfect) Binary Tree.
 Complete Binary Tree.
 Balanced Tree.
  Unbalanced Tree.

Why we use binary tree

The binary tree has two major advantages.

 An Orders Array is a collection of orders.

 List of linked items

As a result, a linked list can be inserted and deleted quickly, and an ordered array may be
searched quickly.

Unbalanced Tree

 The majority of their nodes are on either side of the root.

 Unbalanced subtrees are also possible.

  Binary Search Trees (BSTs) are used to
swiftly determine whether or not an element is in a set.

 Heap sort uses a type of tree called a heap.

 Modern routers store routing information using Tries, a modified version of tree.

 B-Trees and T-Trees, which are variations of the tree structure we utilize, are used by the
majority of popular databases.

 discovered how to save their data in the preceding paragraph

 Every program you write is checked for syntax using a syntax tree by compilers.
Implementing the binary tree

The Node classes

Figure 34 The Node classes

These objects include information on the items being stored as well as pointers to the node's two
children.

The Tree Class

Figure 35 The Tree Class

This is the object that contains all of the nodes.

It simply contains one field: a Node variable that stores the root of the tree.

The Tree app Class

Figure 36 The Tree app Class

Finding a Node
Figure 37 Finding a Node

Inserting a Node

To add a node, we must first determine where it will be placed. This is quite similar to the
procedure outlined in the "Find the Node" section for trying to locate a node that does not exist.
We'll go from the root to the proper node, which will be the new node's parent, by following the
route.
 60 60
00

Before insertion after insertion after

40
insertion 40

30
50 30 50

45

Advantages of Tree

Error detection: With a tree structure, error detection becomes easier. The center hub connects all
of the nodes in this design. Because all information transferred by the nodes flows through the
hub, the hub can readily discover the node with an error. The defective node may be readily
changed by simply replacing the problematic node.

Sturdiness: In tree topology, if a single node fails, the remaining nodes are unaffected. The
primary backbone cable serves as the foundation for the whole tree topology network. As a
 result, the failure of one node will have no
effect on the other nodes, and they will continue to operate normally. The
network's performance is unaffected by the loss of any node.

Simple expansion: Expansion of tree topology is a simple way. Even if there isn't enough room,
it can be enlarged. Because this topology follows a hierarchy structure, it may accommodate a
large number of secondary nodes. The growth won't be a problem as long as there are enough
hubs and cables accessible.

Device support: When it comes to adding additional devices, a tree topology is one of the finest
solutions. Various manufacturers promote this network because of its hybrid approach. It also
enables manufacturers to have quick access to networked devices for maintenance and other
tasks.

Installation of a tree topology does not necessitate the use of any wires. There is a single cable
that serves as the network's backbone, and it connects all of the network's segments together. A
point-to-point wiring is assigned to each tree network. The network's point-to-point connectivity
ensures high bandwidth and minimal latency.

Disadvantages of tree

Tree topology's applications are restricted owing to its complicated installation method. The
functions of both bus and star topology are combined in tree topology. As a result, a tree
topology's cabling requirements are enormous. As a result, the process of implementing this
topology becomes costly and complex to manage.
 Tree topology is particularly insecure in terms
of security. All of the computers in a tree topology are connected to one
another. As a result, data passing over the network may be accessed by any computer on the
network. As a result, if a hacker succeeds to get control of a single workstation, they may swiftly
have access to all of the data, putting the entire network at risk.

The tree topology's backbone cable is the principal cable on which the whole network is
dependent. The entire network will collapse if the backbone cable becomes defective and
collapses. The degree of loss is also determined by the point where the breakdown occurs. If the
damage is limited to a single branch, all of the segments connected to that branch will have
issues operating. The components that aren't connected to it, on the other hand, will continue to
function normally.

The cost of a tree topology is also influenced by the wire length. By default, the cable length is
limited to a given point when constructing a point-to-point connection in tree topology. Later on,
this constraint poses problems since it makes it difficult to become connected. Regardless, if the
network wants to expand, there will be a lot more wiring, which will raise the overall cost.

Due to its vast size, tree topology maintenance and configuration becomes tough. Managing
point-to-point connections, individual star networks, and fault detection take up a lot of time.
One of the main reasons why large companies dislike tree topology is because of this.

(Prasanna, 2022)

Graph
A graph is a nonlinear data structure with a limited number of vertices and edges, with the edges
connecting the vertices. The edges represent the relationship between the vertices, while the
vertices are used to store the data elements. A graph is used in a variety of real-world situations,
including telephone networks, circuit networks, and social networks such as LinkedIn and
Facebook. A single person on Facebook is referred to as a node, and the connections between
users are referred to as edges.

Figure 38 Graph

Types of Graph
There are two sorts of graphs: directed and undirected. The diagram below will help you
understand it better. The direction is shown by the arrow in the illustration.
Figure 39 Types Graph

Graphs come in a variety of shapes and sizes. The directionality of its edges is the first attribute.
Unidirectional or bidirectional edges are possible. The graph is called a directed graph if they are
unidirectional. The graph is called an undirected graph if they are bidirectional (meaning they go
both ways). When some edges are directed and others are not, the bidirectional edges should be
replaced by two directed edges that provide the same purpose. That graph has now been
completely directed.
Figure 40 graph

The weights of the edges are the graph's second attribute. When edges have no weight, the graph
is said to be unweighted. The graph is considered to be weighted if edges contain weights.
There's one more caveat: graphs can have negative weight edges. Some shortest route methods
can't be used because of the negative weight edges.

The occurrence of cycles is the third feature of graphs that influences which algorithms may be
utilized. Any route pp across a graph, GG, that hits the same vertex, vv, more than once is called
a cycle. A graph is considered to be cyclic if it has any path that contains a cycle. Acyclic graphs,
or graphs with no cycles, provide you additional options when it comes to using algorithms.
Figure 41 graph

Directed Graph

A directed graph is a graph that consists of a collection of vertices connected by edges, each of
which has a direction.
 Undirected Graph

An undirected graph is one in which all of the edges are bidirectional and all of the nodes are
linked to one other. Undirected networks are a term used to describe this sort of graph.

Other types of graphs

 A graph with no edges is known as a null graph.

 Undirected graph with no loops or numerous edges is referred to as a simple graph.
 A graph containing several edges connecting the same set of vertices is known as a
multigraph. It's made up of loops.
 A graph with any two vertices connected by a route is known as a connected graph.
 A network in which any two vertices or nodes are connected by a route is known as an
unconnected graph.
 A graph that completes a cycle is known as a cycle graph.
 Complete Graph: A complete graph is one in which each pair of vertices is connected by
an edge.
 Planar graph: A planar graph is one in which no two edges of a graph overlap and all of
the vertices and edges are represented in a single plane. (Anon., n.d.)

Differences between the Linear data structure and non-linear data structure.
 Linear data structure non-linear data structure.

Basic The elements are joined to one The elements are organized
another and are placed hierarchically or non-linearly in
sequentially or linearly in this this structure.
framework.

Types A linear data structure includes A non-linear data structure is

arrays, linked lists, stacks, and made up of trees and graphs.
queues.

implementation They are simple to execute They are tough to adopt due to
because to the linear their non-linear arrangement.
arrangement.

Traversal Because a linear data structure A non-linear data structure's

has only one level, traversing data pieces cannot be retrieved
each data item needs only one in a single run. It necessitates
run. traversing many runs.

Arrangement Each data item is linked to the Each thing is linked to a slew of
one before it and the one after others.
it.
 Levels There is no hierarchy in this The data pieces are placed in
data structure, and all data various tiers in this method.
items are grouped on a single
level.

Memory utilization The memory use is inefficient Memory is used to its full
in this case. potential in this way.

Time complexity With increasing input size, the With increasing input size, the
temporal complexity of linear temporal complexity of non-
data structures increases. linear data structures frequently
stays the same.

Applications Linear data structures are Image processing and Artificial

mostly utilized in software Intelligence both employ non-
development. linear data structures.

Table 1 Differences between the Linear data structure and non-linear data structure.

(Anon., n.d.)

Memory

How the Stack is working in a RAM

Why we need a RAM (Random Access Memory)

 One of the most significant components in
influencing the performance of your computer is random access memory
(RAM). RAM provides a temporary storage and data access location for applications. It saves the
data that your computer is currently working with so that it may be accessed quickly.

You'll need more as your machine runs more apps. Solid state drives (SSDs) are also essential
components that will help your system function at its best.

The quantity of RAM you have installed has a direct relationship with your system's speed and
performance. It may be slow and sluggish if your PC lacks insufficient RAM. On the other hand,
too much might be installed with little or no advantage. There are several techniques to
determine whether your computer need additional memory and to ensure that the memory you
purchase is compatible with the rest of your system's components. Components are often built to
the greatest possible quality at the time of manufacturing, but with the understanding that
technology will continue to evolve.

Modules are physically distinct for each memory technology generation to prevent users from
introducing incompatible memory. These physical distinctions are common in the memory
business. Computer producers need to know the electrical properties and physical shape of the
memory that may be installed in their systems, which is one of the reasons for industry-wide
memory standardization. (Anon., n.d.)

Memories in Computers,

➢ User Space – Can be used by ordinary programs.

➢ Kernel Space – only operating system can use

User Space Memory,

➢ Stack Memory – Follow “First in last out” rule.

➢ Heap Memory – Can be allocated and released by programs.

➢ Program Memory – Store Programs.

Figure 42 memory

Static Memory Layout

Text/Code segment, Initialized, and Uninitialized (bss) Data Segment are the three segments of
the Static Memory layout. These three segments are copied straight from the main memory
layout to the final executable object file of the c program.
 The static memory layout of the c program
executable object file may be examined using the size tool.

Take a look at what we've got here:

Figure 43 Static Memory Layout

The static memory layout is provided when the size command is used to inspect the executable
object file.
Figure 44 Static Memory Layout

Text/Code Segment

The machine-level instructions for the final executable object file are contained in the Text or
Code Segment. Because it contains the program's fundamental logic, this portion is one of the
most important components of the static memory structure.

In the memory structure, the text segment lies below the heap and the data segment. If the stack
or heap overflows, this arrangement will protect the Text section from being overwritten.

We only have read and execute permissions in the text area of the final executable object file,
and no write permissions. This is done to avoid modifying the relevant assembly code by
accident.
 The objdump command can be used to dump
various portions of an executable object file. The Text/Code Segment will
be dumped using the objdump tool in this stage.

One thing to keep in mind is that the objdump command will only work on Linux and will not
work on any other operating system.
Figure 45 Text/Code Segment
Figure 46 Text/Code Segment

: 1129: f3 0f 1e fa endbr64 112d: 55 push %rbp 112e: 48 89 e5 mov %rsp,%rbp 1131: b8 00 00

00 00 mov $0x0,%eax 1136: 5d pop %rbp 1137: c3 retq 1138: 0f 1f 84 00 00 00 00 nopl
0x0(%rax,%rax,1) 113f: 00

We just need to view the main block, thus the output above has been condensed. The main block
in the above objdump output is the assembly code for the C Program's main function.

Initialized Data Segment

This section stores all initialized global and static variables.

Read and write rights are granted to the data segment. This enables the application to run and
alter the value of the data segment variable during runtime.

Let's add some global variables to the prior C program.

Figure 47 Initialized Data Segment

Compare the size of the cprogram. out with the previous size.

Figure 48 Initialized Data Segment

The data segment was previously 544 bytes in size, however it grew to 580 bytes when global
variables were initialized.
Uninitialized Data Segment (BSS)

The "bss" segment, often known as the "uninitialized data section," is called after an archaic
assembly operator that stands for "block began by the symbol."

All uninitialized global variables and static variables are found in the BSS Segment. In the
memory arrangement, this segment is located above the data segment.

The read and write permissions are also included in this portion.

Figure 49 Uninitialized Data Segment (BSS)

Compare the size of the [Link] with the previous size.

Figure 50 Uninitialized Data Segment (BSS)

Because we specified global variables but did not initialize them, the time size of the bss
segment rose from 8 to 24 bytes.

Dynamic Memory Layout

Figure 51 Dynamic Memory Layout

This is the process's runtime memory, which exists as long as the process is running.

Stack

It is possible to run a program without using heap memory, however it is not possible to run a
program without using a stack segment. This demonstrates how crucial stack memory is for
program execution.

The stack is a memory area in the virtual address space of a process where data is added or
withdrawn in Last-in-First-Out (LIFO) sequence.

When you call a new function, a new stack-frame is added to the stack memory. When the
function completes, the associated stack-frame is deleted.
 It's worth noting that each function has its own
stack-frame, which is also known as an activation record. Because the size
of local variables, arguments, and function calls affects the stack size, it is changeable. From a
higher to a lower address, the stack expands.

Each process has its own stack memory, which is either fixed or adjustable. When a process
ends, the OS reclaims the stack memory.

The maximum size of stack memory in the Linux system may be seen with the ulimit -s
command.

Figure 52 Stack

Use ulimit -a command to list all the flags for the ulimit command.
Figure 53 Stack

To find the limits of a running process in Linux, use cat /proc//limits command.
Create a C program with an infinite loop.
Figure 54 stack

Run the executable object file in the background; the process id will be shown. To determine the
process's limitations, use the process id.

Otherwise, the background running process will continue to operate indefinitely.

Figure 55 stack
Figure 56 stack

Let’s find the Stack Size using C Program.

Figure 57 stack
Figure 58 stack

Stack Memory Layout

A stack frame comprises four different sorts of data:

1. the parameters that were passed to the function (Reverse Order)

2. The caller function's return address.

3. The caller function's base pointer

4. The function's local variables

For 32-bit architecture, the return address and base pointer are 4 bytes, while for 64-bit
architecture, they are 8 bytes.

Figure 59 Stack Memory Layout

The following is a detailed representation of how the stack memory might look if we ran the
aforesaid C program.

The topmost frame in the stack is always the one that is being executed. The Frame Pointer,
often known as the Base Pointer, is the pointer to the stack's top-most frame. In the callee's stack
frame, when the caller's base pointer value is duplicated, the Base Pointer holds the beginning
address.

The Stack Pointer is the pointer to the top of the stack. The address at the top of the stack
memory is stored in the Stack Pointer.

For both allocation and de-allocation, the stack memory offers automated memory management.
The stack memory is out of the programmer's control. When creating a stack-frame, the
function's local variable is allocated and de-allocated when the stack-frame approaches the top of
the stack segment.

Stack Error Conditions

Stack Overflow

This error occurs when a program's stack increases above its fixed size due to a protracted
sequence of function calls, culminating in a stack overflow.

What creates the circumstance of stack overflow:

 1. Calls to recursive functions
2. Large array declarations

Because Stack Memory is restricted in capacity, it is not suited for storing huge things.

Stack Corruption

Stack corruption occurs when we copy more data than the available memory capacity, causing
the stack data to be corrupted.

Figure 60 Stack Error Conditions

 A name array of 10 bytes of the char data type
has been supplied in the copy function in the above code. We're also
copying data from the command-line parameter. The stack frame will overwrite another block if
the user supplies a string bigger than 10 bytes, resulting in stack corruption.

Heap

As we've seen, the stack has a fixed size that prevents us from working with large amounts of
data, and we have no control over it. Heap memory, a continuous section of virtual address space
where memory allocation and de-allocation may be done in real-time, solves this problem.

There is no automated memory management in heap memory, unlike stack memory, and the
allocation and de-allocation of heap memory is the major responsibility of the programmer. The
Glibc API, which offers methods to create and de-allocate heap memory, is required to use the
heap memory.

The malloc()/calloc() functions are used to assign memory blocks from the heap segment, and
the free() function is used to return the memory to the heap segment that the malloc()/calloc()
function assigned.

The malloc() and calloc() methods, respectively, allocate and de-allocate heap memory for a
process using the brk() and sbrk() system calls.

The header file stdlib.h defines these functions: malloc, calloc, realloc, and free.

It's important to remember that we can only access heap memory blocks with pointers.
Figure 61 Heap

The diagram above depicts how a heap of memory is accessed with the malloc() function call.
Although the image suggests that the value of integer 20 is stored in the 4 bytes of heap space
allocated by the malloc() method, this is not the case. The value is written or read in physical
 memory, i.e. the RAM, once the virtual address
of the heap segment is translated to the physical address using the MMU
(Memory Management Unit).

(Anon., n.d.)

What Is First In, First Out (FIFO)?

First In, First Out (FIFO) is an asset management and valuation strategy in which the first assets
created or acquired are sold, utilised, or disposed of.
FIFO posits that the assets with the oldest expenses are included in the cost of goods sold on the
income statement for tax reasons (COGS). The remaining inventory assets are compared to the
most recently acquired or manufactured assets.

 The accounting principle of first in, first out (FIFO) states that assets purchased or
acquired first are disposed of first.
 FIFO assumes that the remaining inventory is made up of the most recently acquired
products.
 LIFO is a technique of accounting that differs from FIFO in that assets purchased or
acquired last are disposed of first.
 In an inflationary market, the FIFO technique often assigns lower, older expenses to the
cost of items sold, resulting in a larger net income than if LIFO were utilized.

(SCOTT, 2021)
Advantages of FIFO

 It's simple to comprehend and apply—in fact, it's one of the most extensively used
accounting procedures in the United States and overseas.
 It's tough to falsify stats and profits since the cost associated with each unit sold is always
the oldest.
 It connects the predicted cost flow to the logical, physical flow of products (remember,
we sold our older muffins first), giving firms a more accurate view of inventory expenses.
 It's a better predictor of the value of the closing inventory since the balance sheet amount
is more likely to be close to market value.

Disadvantages of FIFO

Companies utilizing the FIFO technique to report COGS that do not represent what production
and materials actually cost at the time the financial statements are produced and presented in a
rising-price environment. Instead, lesser costs are ascribed to the products sold, leaving the
balance sheet with the newer, more costly inventory. As a result, FIFO can boost net income and
profits by using inventory that is several years old and was purchased or manufactured at a
cheaper cost to value your costs.

To put it frankly, FIFO makes it appear that corporations are generating more money than they
are, at least on paper. Of course, a larger-than-life profit means a higher tax burden—report more
profits on your tax return, and the IRS will naturally demand a greater portion.
 FIFO is particularly vulnerable during periods
of hyperinflation: when material prices rise fast and/or excessively, it
frequently fails to provide an accurate picture of costs. In this instance, matching the oldest
inventory with the most recent sales would be inappropriate and might skew the image by
inflating earnings. The same thing might happen during moments of high market volatility.

Car application

Cord
BBL

Figure 62 bbi 1
Figure 63 bbl 2

 Main
Figure 64 main 1
Figure 65 main 2
Figure 66 main 3
Figure 67 main 4
Figure 68 main 5

quicksort
Figure 69 quilksort 1
Figure 70 quicksort2
Figure 71 quicksort 3
Figure 72 quicksort 4

Queue
Figure 73 Queue 1
Figure 74 Queue 1
Figure 75 Queue 2
Figure 76 Queue 3

Queue Of Stacks
Figure 77 QueueOfStacks 1
Figure 78 QueueOfStacks2
Figure 79 QueueOfStacks 3
Figure 80 QueueOfStacks 4
Figure 81 QueueOfStacks 5

Stack
Figure 82 stack 1
Figure 83 stack 2
Figure 84 stack 3
Figure 85 stack 4

ADT Immolation
Figure 86 ADT Immolation
Figure 87 ADT Immolation

Figure 88 ADT Immolation

ADT Immolation output

Figure 89 ADT Immolation output

pest plan
Identify the errors in the ABC Pvt Ltd Car
Application

Out Range Proposal improvements

Time Frames Preparation

 Test cases

Execution

Evaluation

Documentation

Responsibilities Auditor – Create documentation

Tester – Test the system

Administrator –Access to the system

Developer – Enter the necessary coding

Tools Operating System [Link], Mac

Table 2 pest plan

test case

Project Name ABC Pvt Ltd Car Racing Event Application

Module Name Insert Data

 Created by Sasanthi wanniarachchi

Date of Creation 06/02/2022

Date of Review 09/02/2022

Table
Test 3 test case
Test Test Case Test Steps Test Data Expected Actual Status
No Scenari Output Output (Pass/Fa
Table 4 test case
o il)
Insert Insert Enter 1. Enter Valid data Insert Insert Pass
No1 data data for The data for brand, successful successf
brand, driverNO, ul
driverNo, sponsor,
driver No,driver
NIC,spons NIC
or, No
Abstract Data Types

An abstract data type, or ADT (not the security firm), is a type of object that contains certain
values and activities. It just specifies the What, not the How. Because it enables abstraction, the
abstract data type is an important part of object-oriented programming and design.

Abstraction is a concept that everyone should be familiar with. If you don't need to know how a
remote starter works, you should be able to start it by pressing a button. We typically use the
word interface to refer to the activity conducted while implementing abstract data types.

Between the key fob or your mobile app and the car's starter, there is an interface. You don't
need to know what the functions perform because they're contained in an abstract data type.

Let's look at where the abstract data type as a notion lies in the world of data structures to keep
us focused. Figure 1 depicts a high-level overview of the abstract data type notion.
There are a few other frequent instances of abstract data types besides the automobile starter.

 Stack
 Queue
 List
 Set

Many programming languages, such as C++, Java, and Python, can be used to accomplish each
of these. We won't go through the implementation specifics of these specific structures since we
want to keep this course focused on abstraction!

However, a programmer may build a Queue data type and have access to all of the methods
included inside it without knowing the code for those methods. (Gibbs, 2021)

Stack

 isFull(), This is used to determine whether or not the stack is full.

 isEmpry(), This is used to determine whether or not the stack is empty.
 push(x), This is used to place x at the top of the stack.
 pop(), This is used to remove one element from the stack's top.
 peek(), This is used to acquire the stack's topmost member.
 size() is a function that returns the number of elements in the stack.

Data Structure - Stack

 peek()

Figure 90 peek()

Example

Figure 91 peek()

Algorithm of isfull() function –

Figure 92 Algorithm of isfull() function

Push Operation
Algorithm for PUSH Operation

Figure 93 Algorithm for PUSH Operation

 Example

Figure 94 Algorithm for PUSH Operation

Pop Operation

Algorithm for Pop Operation

Figure 95 Algorithm for Pop Operation

Example

Figure 96 Algorithm for Pop Operation

 (Anon., n.d.)

Queue

 isFull(), This is used to determine whether or not the queue is full.

 isEmpry(), This is used to determine whether or not the queue is empty.
 insert(x), This is used to add x to the back end queue.
 delete(), This is used to remove one element from the queue's front end.
 size() is a function that returns the number of entries in the queue.

List

 size() is a function that returns the number of elements in a list.

 insert(x) is a function that is used to add one element to a list.
 remove(x) is a function that removes a specified element from a list.
 get(i) is a function that returns the element at location i.
 replace(x, y) is a function that replaces the value of x with the value of y.

Specifications of the ADT

 The program Abstract Data Types (ADTs) is a
means of isolating pieces of a bigger programming project that still needs
to be done. It enables for better architecture and makes it easier for several programmers to
collaborate on the same project. When performed properly, it is utilized to develop libraries that
can be attached to several libraries. The upper element and the stack are the two sections of a
string (the remaining elements)

A stack's elements can be of any type, but all of the items in the stack should be of the same type.
Summary data types are purely theoretical entities that may be used to define and assess data
structures, as well as the different types of computer languages.

ADT, on the other hand, may be implemented in a variety of methods, or data structures in a
variety of programming languages, or a correct specification in the language. Modules are
frequently used to implement ADTs: the block interface corresponds to ADT operations, with
comments describing controls. This information module concealment strategy conceals the
strategy, allowing the customer to change programs without difficulty. Many algebraic
structures, including as lattices, groups, and rings, use the compression data type as a common
technique. Summary data types are connected to the notion of data compression, which is meant
for object-oriented programming and software development using contractual approaches.

Specification of SDL
Objects are entered into the orientation according to a set of more or less well-defined rules.
SDL-related components can be found via popup menus. If there are several options, you'll know
what you're searching for, or you may check the "generic" entry, which will help you
comprehend what you're looking for. phase of object orientation and mapping to SDL
  Object
 Attributes
 Methods
 Contact Item
 Interfaces
 Class
 Class libraries
 Virtual classes

Encapsulation
One of the four basic OOP ideas is encapsulation. Inherited, polymorphic, and abstract are the
other three.

In Java, encapsulation is a way for encapsulating data (variables) and code that acts on the data
(methods) into a single unit. Encapsulation means that a class's variables are concealed from
other classes and can only be accessed via its own methods. As a result, data concealing is
another name for it.

In order to accomplish encapsulation in Java, you must:

1) Declare a class's variables to be private.

2) To alter and inspect the variables' values, provide public setter and getter methods.

Encapsulation Advantages
  Data security: The program runner won't be
able to view or identify which methods are in the code. As a result,
he or she has no opportunity to modify any specific variable or data, which might
obstruct the program's operation.
 Flexibility: Encapsulated code seems cleaner and more flexible, and it can be altered as
needed. By using getter and setter methods, we may make the code read-only or write-
only. If necessary, this also aids in troubleshooting the code.
 Reusability: The methods are changeable, and the code may be reused.

Encapsulation Disadvantages

 Code Length: In the case of encapsulation, the code length grows dramatically since we
must supply specifiers for every methods.
 Additional Instructions: As the size of the code grows, you'll need to supply more
instructions for each method.
 Increased code execution time: Encapsulation extends the time it takes for a program to
run. Because additional instructions are added to the code, it takes longer for the code to
run.

Data Hiding
 Data hiding is a software development method
used to hide internal object characteristics in object-oriented programming
(OOP) (data members). Data hiding guarantees that only class members have access to data and
maintains object integrity by limiting unintentional or intentional modifications.

By minimizing interdependencies between software components, data hiding minimizes system

complexity for enhanced resilience.

Data encapsulation or information concealing are other terms for data hiding.

Data hiding is a feature of the OOP paradigm, which divides a program into objects with distinct
data and functionalities. This strategy improves a programmer's ability to design classes with
distinct data sets and functionalities while avoiding unwanted program class infiltration.

There are few data concealing inconsistencies since software architecture strategies seldom
differ. Data encapsulation conceals class data parts and private methods, whereas data hiding
hides simply class data components.

Advantages of Data Hiding

Irrelevant data is isolated from the objects in the class.

It improves security against hackers who are unable to access sensitive information.

It protects programmers from linking to wrong data by mistake. If the programmer links this data
in the code, it will merely produce an error, showing that the mistake has been corrected.

As the fundamental idea of OOP, it separates objects.

 It protects sensitive data from harm by keeping
it hidden from the public eye.

Disadvantages of Data Hiding

It may occasionally necessitate the usage of additional code by the programmer.

The connection between visible and invisible data allows the objects to operate more quickly,
however data masking limits this connection.

Data hiding makes it more difficult for a programmer to generate effects in the concealed data
since they must write long codes.

Benefits of ADTs

1) ADT is built on Object Oriented Programming (OOP) and Software Engineering (SE)
concepts and is reusable and resilient.

2) An ADT can be reused in several places, reducing the number of encoding attempts.

3) Encapsulation protects data from being tampered with.

 4) Various integrations cannot be degraded by
the application software.

5) ADT guarantees a solid data structure.

6) The ADT notion of connection and synchronization is based on the SE principles of

connectivity and synchronization.

7) The merging property is determined.

8) How two different components of the software are combined

9) Changes to one portion of a software package have an impact on other sections.

10) Connectivity is kept to a bare minimum in well-designed software. ADT encourages a

shaky relationship.
 What is object-oriented programming
(OOP)?

Object-oriented programming (OOP) is a programming paradigm based on the notion of

"objects," which can include both data and code in the form of fields, which are commonly
referred to as attributes, and procedures, which are commonly referred to as methods. A human,
for example, is an item with particular qualities such as height, gender, age, and so on. It also
contains ways like moving, talking, and so on.

Object
This is the fundamental building block of object-oriented programming. That is, both data and
data-operating functions are grouped together as an object.

Class
When you create a class, you're essentially creating a blueprint for an item. This doesn't describe
any data, but it does define what the class name signifies, that is, what a class object will be
made up of and what actions can be done on it.

OOP is entirely built on four fundamental notions. Let's take a look at each one separately.

 It refers to merely delivering necessary information to the outside world while concealing
background facts. A web server, for example, hides how it processes data it receives; the
end user just hits the endpoints and receives the data.
 Encapsulation is the process of combining data members (variables, properties) with
member functions (methods) to form a single entity. It may also be used to limit access to
certain attributes or components. A class is the greatest illustration of encapsulation.
 Inheritance is defined as the ability to construct a new class from an existing one. We
may construct a Child class from a Parent class that inherits the parent class's properties
 and methods while also having its own new
properties and methods via inheritance. For example, if we have a
class Vehicle with characteristics like Color, Price, and so on, we may split it into two
classes, Bike and Vehicle, each with those two properties plus extra properties that are
unique to them, such as a car having numberOfWindows while a bike does not. The same
can be said for methods.
 Polymorphism is a term that refers to the fact that something exists in several forms.
Polymorphism usually arises when there is a hierarchy of classes that are connected
through inheritance. Polymorphism in C++ refers to the fact that depending on the kind
of object that calls a member function, a different function is run. (Anon., n.d.)

Object-Oriented Programming and its correlation with ADT?

OOP Concepts
One of the concepts of object-oriented programming is abstraction. It is used to show just the
most important and required elements of a thing to the outside world. To the outer world, it
means showing what is required and encapsulating what is not. The use of "private" access
modifiers can be used to conceal information.

Abstract Class

The abstract keyword is used to declare an abstract class.

Objects of the abstract class are not permitted to be created in C#. To put it another way, you
can't utilize the abstract class with the new operator directly.
 An Abstract Base Class is a class that has the
abstract keyword in some of its methods (not all-abstract methods).

Pure Abstract Base Class is a class that has the abstract keyword in all of its methods.

The abstract methods cannot be declared outside of the abstract class.

Encapsulation

In C#, encapsulation refers to an object's ability to hide data and behavior that isn't required by
its user. Encapsulation makes it possible to regard a set of attributes, methods, and other
elements as a single unit or object. (It's an OOP property)

The following are the benefits of encapsulation

 Protection against data corruption due to human error.

 The accessibility of each member of a class to code outside of the class is specified.
 Code flexibility and extension, as well as a decrease in complexity.
 Reduced connection between items, resulting in improved code maintainability.

Inheritance
 Inheritance is a crucial component of OOP
(Object Oriented Programming). It is the technique in C# that allows one
class to inherit from another.

another class's characteristics (fields and functions).

Important terminology

 Super Class: A super class is a class with inherited characteristics (or a base class or a
parent class).
 Subclass: A subclass is a class that inherits from another class (or a derived class,
extended class, or child class). In addition to the superclass fields and methods, the
subclass can add its own fields and methods.
 Inheritance provides the idea of "reusability," which is useful when we want to construct
a new class but there is already one.
 We can derive our new class from the old class if it has part of the code we desire. We're
utilizing the old class's fields and functions in this way.

Polymorphism

Encapsulation is the capacity of an item to hide data and behavior that isn't required by its user.
Encapsulation makes it possible to regard a set of attributes, methods, and other elements as a
single unit or object. (It's an OOP property)

1) Over loading
 2) Over riding

Overriding
Overriding is a feature that allows a subclass or child class to give a customized implementation
of a method that has already been proven by one of its super-classes or parent classes. A method
in a subclass is said to override a method in its super-class if it has the same name, parameters or
signature, and return type (or sub-type) as the method in the super-class.

Over loading
Programmers can utilize numerous methods with the same name when using method
overloading. The number and type of method parameters are used to differentiate the methods.
Polymorphism is a characteristic of object-oriented programming languages that allows for
method overloading.

Correlation between OOP and ADT

You may use ADT to generate events that have well-defined features and behaviors. Companies
can use abbreviations to arrange occurrences into groups that must consider one another's
common qualities. The combination of a data type and extensions that give functions for that
type is known as data abstraction. The occurrences of that ADT can be declared as a topic by
programs. This is the foundation of object-oriented programming. InADTs can be referred to as
classes because they are object-oriented. As a result, a class defines the attributes of objects in
the object context, which are instances. Object-oriented programming and ADT are two distinct
ideas. The idea of ADT is used by OOPs.
Performance of different sorting Algorithms
Figure 97 Performance of different sorting Algorithms
Figure 98Performance of different sorting Algorithms

(Anon., n.d.)

Operations of Shortest Path Algorithm

The shortest path problem is solved using a set of techniques known as shortest path algorithms.
Most people are familiar with the shortest path issue, which asks: given two places A and B,
what is the shortest path between them? However, in computer science, the shortest path issue
might take many distinct forms, necessitating the use of several methods to solve them all.
 Shortest route methods generally work on an
input graph, GG, for simplicity and generality. A set of vertices, VV, and
edges, EE, link the vertices in this graph. The graph is called a weighted graph if the edges
contain weights. When these edges are bidirectional, the graph is referred to be undirected. There
may even be cycles in the graph at times. Each of these small changes is what makes one
algorithm function better for a specific graph type than another. Below is an illustration of a
graph.

Figure 99Operations of Shortest Path Algorithm

 There are several sorts of shortest route
algorithms as well. You could need to discover the shortest path between
points A and B, but you might also need to find the shortest path between point A and every
other point in the graph.

Shortest route algorithms are useful in a variety of situations. As previously stated, shortest path
algorithms are used in mapping applications such as Google or Apple maps. They're also vital
for study on the road network, operations, and logistics. Computer networks, such as the Internet,
rely heavily on shortest path algorithms.

A shortest path algorithm is used by any program that assists you in choosing a route. For
example, Google Maps allows you to enter a beginning location and an ending point and it will
calculate the quickest journey for you.

Types of Shortest Path Algorithms

Single-source and all-pairs shortest route algorithms are the two most common forms. Both types
have algorithms that excel in their respective areas. Because of the extra complexity, all-pairs
algorithms take longer to run. Even though the return values differ in kind or form from
 algorithm to algorithm, all shortest path
methods produce values that may be utilized to calculate the shortest path.

Single-source

Single-source shortest path algorithms operate under the following principle:

Figure 100 Single-source

If the purpose of the method is to identify the shortest path between only two vertices, ss and tt,
the program can simply be terminated after that path has been identified. All algorithms that
solve for the shortest path between two given vertices have the same worst-case asymptotic
complexity as single-source shortest path algorithms since there is no mechanism to pick which
vertices to "complete" first.

The single-destination shortest route issue may also be solved using this approach. The single-
destination problem may be simplified to the single-source problem by reversing all of the edges
in a graph. As a result, given a destination vertex, tt, this method will identify the shortest routes
between tt and all other vertices.

All-pairs
 All-pairs shortest path algorithms follow this
definition:

Figure 101 All-pairs

The floyd-warshall method is the most often used algorithm for the all-pairs problem. This
technique outputs an MM matrix, with each column M i, jM i,j representing the shortest path
between vertex ii and vertex jj. It is feasible to recreate the actual path followed to reach the
shortest path, but this is not part of the basic method.

Algorithms

Bellman-Ford algorithm

In the broader scenario, when edges can have negative weights and the graph is directed, the
Bellman-Ford method solves the single-source problem. If the graph is undirected, it must be
updated by adding two edges in each direction in order to become directed.

Bellman-Ford has the virtue of being able to discover negative weight cycles that can be reached
from the source, implying that there is no shortest path. If there was a negative weight cycle, a
path might run indefinitely on it, lowering the path cost to - infty.
 Bellman-Ford returns the weight of the shortest
path together with the path itself if there is no negative weight cycle.

Dijkstra's algorithm

To tackle the single-source problem, Dijkstra's method uses breadth-first search (which is not a
single source shortest path algorithm). It does impose one restriction on the graph: no negative
weight edges are allowed. Dijkstra, on the other hand, vastly outperforms Bellman-Ford in this
one constraint.

By simply performing Dijkstra's algorithm on all vertices in VV, the all-pairs shortest route issue
may occasionally be solved. This, too, necessitates that all edge weights be positive.

topological sort

A highly valuable technique for determining shortest routes arises for graphs that are directed
acyclic graphs (DAGs). The shortest path problem may be solved in linear time by doing a
topological sort on the graph's vertices.

A topological sort is an ordering of all the vertices such that uu occurs before vv in the ordering
for each edge (u, v)(u,v) in EE. Even if there are negative weight edges, there can't be negative
weight cycles in a DAG, therefore shortest routes are always clearly defined.
Floyd-Warshall algorithm

The Floyd-Warshall method is used to solve the shortest route issue for all couples. It
accomplishes this with the use of dynamic programming. Floyd-Warshall might have a negative
edge weight.

The shortest road from A to C is either the shortest path from A to B plus the shortest path from
B to C, or it is the shortest path from A to C that has already been determined, according to
Floyd-Warshall. This may seem little, but it is what permits Floyd-Warshall to construct shortest
pathways from smaller shortest paths in the traditional dynamic programming manner.

Johnson's algorithm

While Floyd-Warshall excels in dense graphs (those with a lot of edges), Johnson's approach
excels at sparse graphs (meaning few edges). Johnson's approach has a faster asymptotic running
time than Floyd-Warshall in sparse graphs.

Johnson's approach makes use of the notion of reweighting, and after reweighting the edges, it
applies Dijkstra's algorithm to numerous vertices to determine the shortest path.
Figure 102 Johnson's algorithm

Comparison of Algorithms

Figure 103 Comparison of Algorithms

Choosing which method to utilize is frequently not a matter of personal preference; rather, it is a
function of the graph being worked on and the shortest path issue being addressed.

The single source shortest path issue requires Bellman-Ford to succeed for graphs with negative
weight edges. Floyd-Warshall should be utilized for thick graphs and the all-pairs issue.

There are, nevertheless, some minor distinctions. Johnson's approach may seem apparent for
sparse graphs and the all-pairs issue. If there are no negative edge weights, however, it is really
preferable to implement Dijkstra's method with binary heaps. A better result will be obtained by
running Dijsktra's from each vertex. (Anon., n.d.)

sorting algorithm

As I previously stated, sorting a vast list of data is usually an unpleasant and time-consuming
operation, which is why a computer software has been designed to help with this chore. Sorting
algorithms are the name for this type of computer software.

The sorting method may be used to rearrange the elements of a given list or array using
comparison operators. These operators are applied to the provided items to determine the new
element order in the data structure.

types of sorting algorithms

 Sorting Bubbles
It's one of the most basic techniques of sorting. The sorting process is carried out by consistently
pushing the higher items to the array's highest index in this sorting method. It essentially
compares comparable items to the neighboring element and replaces them as needed.

 Sort by selection

The smallest element is found and then placed at the beginning of the algorithm. The second
smallest element will then be discovered and placed in the second position. This operation will
continue until all of the array's items are moved to the specified location.

Sorting Made Simple It is thought to be the most efficient sort algorithm. This sorting algorithm
uses the divide and conquer strategy, just as the Merge sort. Furthermore, this method can sort
within O(n log n) comparisons.

 Sorting in a Bunch

The max heap and min heap will be maintained from the array items in this function. It also
depends on the array or list element that can sort the heap by eliminating the root items

 Sorting by insertion

It's used to arrange array elements where they're needed. Insertion sort is a basic sorting
procedure that is used to arrange the cards in the deck during bridge play.

 SortIt Merge
 follows the divide and conquer strategy, which
separates the array or list element into equal groups of elements. The
merge sort is then used to sort the half list. Finally, the list will be combined one again to create
the basic sorted array. (Anon., n.d.)

What is ASN.1

ASN.1 is a formal notation for defining data transferred through telecommunications protocols,
regardless of language implementation or physical representation, and regardless of the
application, whether sophisticated or simple.

The Abstract Syntax Notation Number One is a standard that establishes a framework for
specifying abstract data types.

There are a few pre-defined fundamental types in the notation, such as:

 integers (INTEGER),
 booleans (BOOLEAN),
 character strings (IA5String, UniversalString...),
 bit strings (BIT STRING),
 etc.,

and makes it possible to define constructed types such as:

  structures (SEQUENCE),
 lists (SEQUENCE OF),
 choice between types (CHOICE),
 etc.

Subtyping restrictions can be added to any ASN.1 type to limit the number of possible values.

Unlike many other syntaxes that promise to be extendable, ASN.1 allows extension that
addresses and supports the interoperability of previously deployed systems with later, updated
versions created years apart.

ASN.1 transfers information in any format (audio, video, data, etc.) to any location where digital
communication is required. Only the structural components of information are covered by ASN.1
(there are no operators to handle the values once these are defined or to make calculations with).
As a result, it isn't considered a programming language.

In contrast, the idea of "valid syntax" in ABNF, or the concept of "valid document" in XSD,
where the focus is solely on what are acceptable data encodings, with no regard for any meaning
that may be connected to such encodings. That is, without any of the required semantic
connections.

Abstract Data types

 ADT stands for Abstract Data Type, which is a
type (or class) for objects whose behavior is specified by a collection of
values and functions.

The ADT specification merely indicates what functions should be done, but not how these
functions should be performed. It makes no mention of how data is stored in memory or what
processes are employed to carry out tasks. This is why it's calle

d a "summary."

gives a perspective that is not dependent on the implementation. The practice of delivering only
the most important information while concealing the intricacies is known as summary.

Specifying abstract data types for a software stack

The following structure and functions describe the stack summary data type. The things are
added and withdrawn as a series of structured items from the end of the so-called "top," as
explained above. LIFO is used to organize layers. The roles of the layers are listed below.

 Push (item) - Pushes a new item to the layer's top. It necessitates the item and does not
provide any compensation.
 remove top item from layer () - Removes the top item from the layer. It returns the item
and does not require any inputs. The layer has been changed.
  peek () - returns the layer's top item without
removing it. It does not necessitate the use of parameters. There is
no modification to the layer.
 isEmpty () - Determines if a layer is empty. It returns a Boolean value and does not need
any arguments.

Efficiency of an algorithm

Computer resources are finite, therefore they must be used wisely. The quantity of computational
resources consumed by an algorithm is referred t

o as its efficiency. To determine the resource utilization of an algorithm, it must be evaluated.

The efficiency of an algorithm may be judged by looking at how it uses various resources.

We want to use as little resources as possible to maximize algorithm efficiency. Because crucial
resources like time and space complexity can't be simply compared, time and space complexity
might be taken into account for algorithmic efficiency.
 Method for determining Efficiency

An algorithm's efficiency is determined by how well it uses time and memory.

Different variables are used to evaluate an algorithm's time efficiency. Write a program for a
certain algorithm, run it in any programming language, and record the total time it takes to
complete. In this situation, the execution time you measure will be influenced by a variety of
factors, including:

 Speed of the machine

 Compiler and other system Software tools
 Operating System
 Programming language used
 Volume of data required

However, in order to establish how well an algorithm handles a particular problem, you must
first discover how the method's nature affects the execut

ion time. As a result, basic laws determining the efficiency of a program in terms of the nature of
the underlying algorithm must be developed.
 Space-Time tradeoff

A space-time or time-memory tradeoff is a method for solving a given algorithm in less time by
consuming more storage space, or in less time by spending more time.

Many alternative algorithms can be employed to tackle a specific programming challenge. Some
of these algorithms may be incredibly efficient in terms of time while others may be extremely
efficient in terms of space.

A time/space trade-off occurs when you may either reduce memory use at the expense of slower
program execution or increase memory usage at the expense of faster program execution.
(Anon., n.d.)

Asymptotic Analysis

The mathematical boundation/framing of an algorithm's run-time performance is defined by

asymptotic analysis. We can easily determine the best case, average case, and worst case
scenarios of an algorithm using asymptotic analysis.

Asymptotic analysis is input bound, which means that if the method has no input, it is assumed
to work in a constant time. Aside from the "input," all other variables are assumed to be constant.

Calculating the running time of any operation in mathematical units of computation is known as
asymptotic analysis. For example, one operation's running time is computed as f(n), whereas
another operation's running time is computed as g. (n2). This indicates that when n rises, the first
operation's running time will increase linearly, whereas the second operation's running time will
 climb exponentially. Similarly, if n is small
enough, the running time of both procedures will be roughly the same.

Typically, there are three categories of time required by an algorithm.

1) In the best-case scenario, program execution time is kept to a minimum.

2) The average case is when the software takes an average amount of time to complete.
3) In the worst-case scenario, the program's execution will take the maximum amount of
time.

Asymptotic Notations

 Ο Notation

 Ω Notation

 θ Notation

Big Oh Notation, Ο

The upper bound of an algorithm's execution time is expressed using the notation O(n). It
calculates the worst-case time complexity, or the time it will take an algorithm to finish.
Figure 104 Big Oh Notation, Ο

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

Omega Notation, Ω

The formal approach to indicate the lower bound of an algorithm's running time is to use the
notation (n). It calculates the best-case time complexity, or the shortest time an algorithm may
take to finish.
Figure 105 Omega Notation, Ω

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Theta Notation, θ

The formal approach to describe both the lower limit and upper bound of an algorithm's
execution time is the notation (n).
Figure 106 Theta Notation, θ

θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

Common Asymptotic Notations

Figure 107 Common Asymptotic Notations

Figure 108 Common Asymptotic Notations

(Anon., n.d.)

Abstract data types

What is trade-off when specifying ADT
An abstract data type's user has no idea how it's represented or processed, and they don't have the
ability to change the code to suit their needs. The modification with separate replaceable
modules is acquired at the price of expanding the capacity to modify the present function by
concealing the functionality of the data. If the user does not take into consideration the items
added to the queue, an array employing an abstract data type that is processed using a queue will
be overridden. As a result, ADT should incorporate this into the representation exception.

Benefits of using implementation independent data structures

The list ADT's functionalities are independent of whether the list is performed as a linked list or
as a row ADT, and the ability to edit it is limited by pre-conditions and back-conditions so that
users may know what they can safely change. With the flexibility of representation, the
algorithm's modularity grows. That is, distinct portions of a project are dependent on the
implementation of other components. The code will be less linked because each block is
independent of the others. In various applications, different implementations of the abstract data
type could perform differently. Each portion of a project is easy to use for its data types using
abstract data types, which may be particularly efficient in a specific application situation.

Time-Space Trade-Off in Algorithms

The Time-Space Trade-Off in Algorithms will be discussed in this article. A tradeoff occurs
when one item rises while the other lowers. It is a method of resolving an issue in:
  Either in less time and with greater room, or in both.
 By putting in a lot of effort and time, you can get a lot done in a small amount of space.

The optimal algorithm is one that aids in the solution of a problem that consumes less memory
and generates output in less time. However, achieving both of these characteristics at the same
time is not always attainable. A lookup table algorithm is the most typical condition. This means
that the answers to some queries may be put down for every conceivable value.

One solution is to write down the full lookup table; this will allow you to get answers fast but
will take up a lot of room.

Another option is to compute the answers without writing anything down; this saves space but
takes a long time. As a result, the more time-efficient algorithms you have, the less space-
efficient they are.

 Compressed or Uncompressed data

 Re Rendering or Stored images
 Smaller code or loop unrolling
 Lookup tables or Recalculation

Compressed versus uncompressed data: When it comes to data storage, a space-time trade-off
might be used. Uncompressed data takes up more space but takes less time to store. However, if
 the data is compressed, the decompression
procedure requires less space but more time to perform. It is feasible to
operate directly with compressed data in a variety of situations. In the

situation of compressed bitmap indices, where working with compression is faster than working
without it.

Re-displaying vs. Stored Images: In this situation, saving only the source and rendering it as an
image would use more space but take less time, i.e., storing an image in the cache is quicker than
re-rendering but takes up more memory space.

Smaller code, also known as Loop Unrolling, takes up less memory space but requires more
calculation time to return to the start of the loop at the conclusion of each iteration. Loop
unrolling improves execution speed at the expense of binary size. It needs less calculation time
but takes up more memory.

Lookup tables or recalculation: In a lookup table, an implementation might incorporate the

complete table, reducing processing time but increasing memory requirements. It can recalculate,
that is, compute table entries as needed, which increases computation time but decreases memory
needs.
 Exception Handling

Operating handling is one of the most powerful motions for addressing runtime problems while
keeping the application's usual flow. Learn the distinction between Java exceptions, their types,
and checked and unchecked exceptions in this work. Exemption handling is a framework for

dealing with a variety of operating system exceptions, including ClassNotFoundException,

IOException, SQLException, and RemoteException, among others. Exception Handling Mode
The key benefit of exception handling is that it keeps the application's usual flow. Understanding
error management may be shown in some of the sorts of mistakes, which can be identified in two
ways.

Errors happen at a specific moment - This is an issue that happens at a specific time. When you
try to compile your code, you get computer time or run time errors, which are issue solving
problems.

A specific category error consists of mistakes of a single kind, semantic, and logical, as well as
syntax errors that combine temporal errors.

Java exceptions come in several forms.

 Verifiable and unchecked exceptions are the
two sorts of exceptions. An mistake is seen as an uncommon choice in this
context. There are three sorts of exceptions, according to Oracle:

1) Exception in the test

2) An exception that hasn't been checked

3) Error number three

Java exceptions are a set of five terms that describe how Java handles exceptions.

The "Try" keyword is used to identify a package where an exception code should be placed. To
follow or to follow is an attempted succession. That is, we cannot rely just on volume.
  Catch - To handle the exception, the "Catch"
module is utilized. It must be preceded by an attempted set,
implying that lockable volumes cannot be used by themselves. Finally, you may pause it
at any time.
 Finally - "Finally" is used to run the block program's main code. Whether or not an
exception has been handled.
 Throw - To throw an exception, use the "throw" key.
 Throws - Exceptions are declared using the term "throws." This isn't an outlier. This
indicates that a system exception is possible. This is usually used in conjunction with a
signature.

Which data structure can be used, when simulating the above scenario?

What are the valid operations that can be carried out on this data structure?

Demonstrate how the implementation of an ADT/algorithm solves the above problem.

The data type in this situation is stack. Because this stack frame option has a unique method
associated with the same local variables and note variables, it is in memory where the stack is
 saved at a certain moment and in different stack
frames with all the data connected with it. The bank's hall reservation is at
the bottom of the page.

The items in the stack are added or deleted in a straight line, not in a row or in a collected
collection. The data in that stack is organized and retrieved in a certain way. A method known as
LIFO was applied in this situation (last-first). This consists of a succession of insertions and
removals.

An object orientation is a tool that allows a computer program to interact with the so-called
modes of other objects to generate the program's behavior. It simplifies, reads, and
programmable programming. Object orientation is the basis for a variety of ADTs. Do you
agree? Justify
It does not delve into the entire philosophy of object-oriented design in this work. In compressed
data types, we concentrate on the pre-cursor of OOP design (ADTs). The notion of compact data
types was instantly infused with a hypothesis for a fully object-oriented approach. A set of
functions or processes that operate data structure and data structure make up an abstract data
type. It is termed a class of operations and procedures and data structure and its methods, which
calls for ADTs, to arrange ourselves with the OOP theory. OOP, on the other hand, lacks the
whole set of abilities and classes required for theoretical classes. An object is an example of a
class.
Items are virtual representations of real-world objects that occur in programs as versions of the
variables specified by classes. In OOP design approaches, these phrases have the same meaning,
but there are other attributes such as the gene that they do not cover here. Material orientation is
a way of design. As a result, languages like C, Ada, and Pascal may be used to write OOP

programs. OO languages, such as C++ and Eiffel, give some compiler support for OO design,
which should be provided by programmers who are familiar with OOP languages and have a
good understanding of data structures and performance. ADT is a class in object-oriented design.
 ADTs are not frequently connected with classes
that have extra attributes (such as inheritance
and polymorphism). Frequently, programs deal with collections of goods.
These collections may be arranged in a variety of ways and represented using a variety of
program structures, but there will be a few common operations on each collection from an
abstract standpoint. These might include the following:
Destroyers and Analysts - Any compression data type routinely executes develop and destroy
procedures, which are typically referred to as controllers and destroyers.

Constructing a suitable specification is the first step in creating a short software model.

Methods - A method is a piece of code that is called by a name and is used to call the system's
name at any time (called)
Previous and post-conditions - Without prior and post-conditions, there is no meaningful
specification. This is a good technique to get the topic and the client to sign a contract.

As a result, I agree that for mandatory ADTs, persuasive orders are required. These OOP
comments for ADTs may be used to generate the index.

Last out (LIFO)

 When an item is inserted or withdrawn during a
stack access, LIFO is used correctly. This is an abbreviation for "first out
first." This method is used by the system to receive data requests. In every graphic, the data that
was most recently contributed or sorted should be eliminated first. Act on a stack is explained in
the next sections using Figure 2 below if you apply the packet to the gallery above in the queue.

What sort of trade-offs exists when you use a ADT for implementing programs?

The ADT algorithm requires less memory space and takes less time to execute or issue its
instructions for programs to solve a given problem. In practice, however, achieving these two
goals is not always achievable. As previously said, there might be more. more than one method
for resolving the same issue Such a strategy may necessitate greater room. However, it will take
less time to do its task. As a result, we must make a sacrifice. at each other's cost We can say that
the instructions are separated by a time interval. As a result, if space is a constraint, we must
select a program that takes less space. Higher operating times come at a cost. Furthermore, if we
have power over time, we must make a decision. program that consumes less space yet takes less
time to evaluate its assertions

Re-calculation of vision tables

An algorithm in a view table may include a full table, which reduces memory size, but increases
the required amount of memory or calculates entries in the required table, increases the system
time, but reduces memory needs.
 Compressed data
The problem of data storage may also be solved by transferring algorithms
in terms of place and time. Data that isn't saved takes up more room, but it takes less time to
access than compressed data. Data compression minimizes the amount of space it takes up, but
The decompression method takes a long time to complete. This is dependent on the exact
scenario. In practice, there is a problem and a practice. There are just a few cases when
compressed bitmap codes are used. There are times when you can deal directly with compressed
data, and other times when you can work with uncompressed data. compression is more efficient
than compression

Smaller code and loop unrolling

This strategy is widely used to employ the code for each cycle revision, but it saves the
computation time necessary to leap back to the start of the cycle at the conclusion of each
iteration. When executing the cycle, the larger the index size, the faster it may be exchanged.

Describe the benefits of using independent data structures for implementing programs.
In simple words, a data structure is a data framework that allows for efficient data usage.
Depending on the application, data structures may change. Algorithms, for example, employ
different data structures than compilers. The advantages and disadvantages of data structures are
outlined below.

Benefit
  Arrangements of Data structures make it
possible to collect information on a hard disk.
 Leads to extensive database management, such as databases or web coding services.
 The ability to design efficient systems is critical.

 Allows you to save data on the computer. The information may then be utilised at a later
time and by a variety of programs. Furthermore, the data is safe and cannot be lost,
particularly if it is kept on magnetic tapes.
 Software allows data to be used and processed on a computer system.
 Data processing is simple.
 Using the Internet, access data from a connected machine (computer, laptop, tablet,
phone, etc.).

Difficulties
 Advanced users' data structures are the only ones that may be changed.
 Any issues involving structural data structure need the assistance of a professional,
implying that novice users are unable to assist themselves

Conclusion

References
 Anon., 2019. geeksforgeeks. [Online]
Available at: [Link]
[Accessed 01 01 2022].

Anon., 2021. geeksforgeeks. [Online]

Available at: [Link]
[Accessed 01 01 2022].

Anon., n.d. [Online]

Available at: [Link]
memory-
do#:~:text=Computer%20random%20access%20memory%20%28RAM%29%20is%20one%20o
f,using%20so%20that%20it%20can%20be%20accessed%20quickly.
[Accessed 05 01 2022].

Anon., n.d. .tutorialspoint. [Online]

Available at:
[Link]
20Operation%201%20%E2%88%92%20Checks%20if%20the%20stack,where%20top%20is%2
0pointing.%205%20%E2%88%92%20Returns%20success.
[Accessed 11 01 2022].

Anon., n.d. brainkart. [Online]

Available at: [Link]
algorithm_37217/#:~:text=%20Efficiency%20of%20an%20algorithm%20%201%20Method,use
s%20meaningful%20statements%20about%20time%20and...%20More%20
[Accessed 12 01 2022].
 Anon., n.d. brilliant. [Online]
Available at: [Link]
[Accessed 06 01 2022].

Anon., n.d. byjus.. [Online]

Available at: [Link]
theory/#:~:text=%20Types%20of%20Graph%20%201%20Directed%20Graph.,graph%3A%20A
%20graph%20that%20is%20undirected...%20More%20
[Accessed 11 01 2022].

Anon., n.d. codeavail. [Online]

Available at: [Link]
[Accessed 11 01 2022].

Anon., n.d. enjoyalgorithms. [Online]

Available at: [Link]
[Accessed 07 01 2022].

Anon., n.d. hackthedeveloper. [Online]

Available at: [Link]
program/#:~:text=Program%20execution%20can%20take%20place%20without%20a%20heap,a
dded%20or%20removed%20in%20the%20Last-in-First-out%20%28LIFO%29%20order.
[Accessed 06 01 2022].
 Anon., n.d. javatpoint. [Online]
Available at: [Link]
structure#:~:text=Differences%20between%20the%20Linear%20data%20structure%20and%20n
on-linear,data%20stru%20...%20%205%20more%20rows%20
[Accessed 10 01 2022].

Anon., n.d. tutorialspoint. [Online]

Available at: [Link]
[Accessed 01 01 2022].

Anon., n.d. tutorialspoint. [Online]

Available at:
[Link]
[Accessed 10 01 2022].

Anon., n.d. tutorialspoint. [Online]

Available at: [Link]
OOP#:~:text=Object-
oriented%20programming%20%28OOP%29%20is%20a%20programming%20paradigm%20bas
ed,certain%20properties%20such%20as%20height%2C%20gender%2C%20age%2C%20etc.
[Accessed 11 01 2022].

Anon., n.d. tutorialspoint. [Online]

Available at:
[Link]
[Accessed 11 01 2022].
 Anon., n.d. tutorialspoint.. [Online]
Available at:
[Link]
[Accessed 01 01 2022].

Anon., n.d. w3schools. [Online]

Available at: [Link]
[Accessed 08 01 2022].

Gibbs, M., 2021. study.. [Online]

Available at: [Link]
[Accessed 11 1 2022].

Prasanna, 2022. aplustopper. [Online]

Available at: [Link]
disadvantages/#:~:text=Comparison%20Table%20for%20Advantages%20and%20Disadvantage
s%20of%20Tree,high-security%20threat%20...%20%201%20more%20rows%20
[Accessed 30 01 2022].

SCOTT, G., 2021. investopedia. [Online]

Available at:
[Link]
%2C%20First%20Out%20%28FIFO%29,a%20higher%20net%20income%20than%20if%20LIF
O%20
[Accessed 11 01 2022].