Data Structure and Algorithm: Buddhi Raj Gurung

2020 Data Structure and

Algorithm
Buddhi Raj Gurung

HND/ Third Semester Sec-B)

Data Structure and Algorithm 2020
Table of Contents
P1 Create a design specification for data structures explaining the valid operations that
can be carried out on the structures......................................................................5
Introduction:.......................................................................................................................................5
My Role as System Software Developer............................................................................................6
Data Structure.....................................................................................................................................8
Types of data structures.............................................................................................................9
Advantages of data structure...........................................................................................................9

Disadvantages of data structure....................................................................................................10
P2 Determine the operations of a memory stack and how it is used to implement
function calls in a computer................................................................................10
Memory Stack:....................................................................................................10
The operations of a memory stack................................................................................................10
LIFO (Last In First Out)...............................................................................................................10
Stack Operations...............................................................................................................................11
The Push Operation......................................................................................................................11

The Pop Operation........................................................................................................................11
The Peek Operation......................................................................................................................11
The Search Operation...................................................................................................................12
How it is used to implement function calls in a computer stack memory in computers..................12
Stack memory implements function call in computer..................................................................14

M1 Illustrate, with an example, a concrete data structure for a First In First out (FIFO)
queue...................................................................................................................16
First in First out (FIFO) Queue:.......................................................................................................16
FIFO Queue basic operations:......................................................................................................16

Dequeue Operation.......................................................................................................................17
Example........................................................................................................................................18
M2 Compare the performance of two sorting algorithms..................................20
Buddhi Raj Gurung (HND/ Third Semester Sec-B)

2
Bubble Sort.......................................................................................................................................20
Example of bubble sort:................................................................................................................20

Selection Sort....................................................................................................................................22
Example of selection sort:.............................................................................................................23

Comparison between bubble sort and selection sort:.......................................................................25
Network shortest path algorithms:....................................................................................................26
1. Bellman-Ford Algorithms.....................................................................................................26
2. Dijkstra’s Algorithm..............................................................................................................28
P3 Using an imperative definition, specify the abstract data type for a software stack.
............................................................................................................................34
ADT for software stack:.............................................................................................................34
Specify the abstract data type for a software stack.......................................................................34

M2 Examine the advantages of encapsulation and information hiding when using an
ADT....................................................................................................................36
Advantages of encapsulation............................................................................................................36
D2 Discuss the view that imperative ADTs are a basis for object orientation and, with
justification, state whether you agree.................................................................36

3

4
P1 Create a design specification for data structures explaining the valid

operations that can be carried out on the structures.
Scenario
The Shop-Now is an online Ecommerce Platform (B2C) business to costumer. The company owns
several sales outlets linked to a central warehouse where stocks are maintained and deliveries start
from. The company requires a software system that has the following features.
 The orders are collected locally at the sales outlets.

 They are transmitted to the warehouse, where the delivery procedure should be managed.
 An account of the delivery must be sent back to the sales outlets for following through the
client's order.

5
My Role as System Software Developer

For the development of this project, I have to work with my colleagues as part of a development
team.
Class MyT<T>
- In Java 5, generics are included in the concept. "Generics" means parameterized data types.
Parameterized data type is very important in coding because it allows us to create and use a class,
interface, method with many different types of data. With the help of generics, an Linked List object

6
is created which contains elements of type T. Type <T> is understood as an Object of the Java
runtime. It is a represent of an object will be specified when using.
My<T> is considered as a node.
+ info: T - object data carried by this node, could be any types.
+ next: My<T> - reference to the next node in the list, or maybe null.
- More information about nodes in Linked List will be provided in section II.1.C
Class MyLinkedListT<T>
- This class is implemented as a Linked List Class from scratch in Java. This program does not use
the stuff in the standard library. The point of constructing this class is to understand how things
work, and understanding linked lists through important steps by steps and understanding more
complex in data structures.
- MyLinkedListT<T> is a list containing MyT<T> node, a collection of node is stored in this class, it
begins with a head and ends with tail.
- More information about Linked List will be provided in section II.1
Class MyStackT<T> and MyQueueT<T>
- This class is implemented as a Stack Class and Queue Class from scratch in Java.
- More information about Stack and Queue will be provided in section II.2 and II.3
Class Product
- Contain information of one Product. It has 5 values:
 code: string - the code of the product (this should be unique for the product).
 pro_name: string - the name of the product.
 quantity: i integer - the number of products with the same code in a shop at beginning of a
day.
 saled: integer - the number of products with the same code, which are saled in the day.
Condition - saled ≤ quantity.

7
 price: double - The price of the product.
Class Customer
- Contain information of one Customer. It has 5 values:
 code: string - the code of the customer (this should be unique for the customer).
 cus_name: string - the name of the customer.
 phone: string - The phone number of the customer (must contain digits only).
Class Ordering
Contain information of one Ordering. It has 3 values:
 pcode (string) - the code of the product to be ordered.

 ccode (string) - the code of the customer.
 quantity (integer) - the number of ordered products.
 total (double) - total value.
Class OrderingList, CustomerList and ProductList
- These classes contain main () function to run the application. The research of Searching, Sorting
and Recursion is come from these classes.
Design Specification Case Study
Module-order DEFINITIONS
AUTOMATIC TAGS::= BEGIN
Order::= SEQUENCE{
header Order-header items SEQUENCE OF Order-line
}
Order-header::= SEQUENCE{
number Order-number, date Date, client Client, payment Payment method
}
Order-number::= NumberString|SIZE((2))
Date::=NumericString|SIZE((8))-MMDDYYYYY
Client::=SEQUENCE{

8
Name PrintableString|SIZE((1.20)), street Printable

String|SIZE((1.50)) OPTIONAL postcode NumericString|SIZE((5)), town Printable
String(SIZE)
}
Default-country PrintableString::=”Nepal”
Payment-method::=CHOICE{
Check NumericString(SIZE((5))’ credit-card Credit-card, cash NULL
}
Credit-card::=SEQUENCE{
Type Card-type, number NumericString|SIZE((20)),
expiry-date NumericString|SIZE((6))MMDDYYYY-
}
Card-type::=ENUMERATED{
Cb(0), visa(1), Eurocard (2), dinners(3), America-express(4)
}
Order-line::=SEQUENCE{
Item-code Item-code, label Label, quantity Quantity, price Cents
}
Item-code::=NumericString|(SIZE((7))
Label::=PrintableString|SIZE((1.30))
Quantity::=CHOICE {unites INTEGER, millimeters INTEGER, milligrammes INTEGER }
Cents::=INTEGER
Delivery-report::=SEQUENCE{ Order-code Order-number, delivery SEQUENCE OF Delivery-

line} Delivery-line::=Sequence(item Item-code, quantity Quantity}
END

9
Data Structure
Data Structure is a concrete implementation of data types. It is possible to analyze the time
complexity and memory of the Data Structure but not from the data type. Data structures can be
implemented in a number of ways and their implementation may vary from language to language.
Data structure is a specific way to organize your data in a computer so that it can be used effectively.
For example, we can store a list of items that have the same data type using a uniform data structure.
At the backbone of every program or piece of software are two entities: data and algorithms.
Algorithm transform data into something a program can effectively use. Besides, data structures are
computer programs that optimize the way that the information management process calculates
information in memory. Data structures often build each other to create new structure and those
structure are applied to a certain data access pattern. Choosing the most efficient data structure for
the job greatly improves algorithms performance, helping to speed up application processing. This
allows computer systems to efficiently manage massive amounts of data within large- scale indexing,
massive databases, and structure data in big data platforms. In other words, data structure would be
that there are basically different ways of sorting data con your computer.
Types of data structures
Data structures are divided into two categories, includes, Primitive Data and Non-primitive:
1. Primitive Data Structures
These are supported structures at the machine level, which can be used to create non-primitive
data structures. This is indispensable and pure in form. They have predetermined behavior and
specifications. For example: Integer, Float, Character, and Pointer. However, pointer does not
hold a data value, instead, they keep memory addresses of data values. This is also called the
reference data type.
2. Non-Primitive Data Structures
Non-primitive data structures can be implemented without the original data structure. Although
they are also provided by the system themselves, they are data structures of origin and cannot be
formed without using primitive data structures. Non- primitive data structures are divided into
two types: Simple data structures and Compound data structures.

10
Advantages of data structure

 Data structures allow the storage of information on hard drives.
 provides a way to manage large datasets such as databases or internet indexing services.
 Is there a need for efficient algorithm design?
 allowing secure storage of information on your computer. This information can then be used
for later use and can be used by various programs. In addition, the information is protected
and should not be lost (especially if it is stored on magnetic tape).
 allowing data to be used and processed on software systems.
 Enables easier data processing.
 Using the internet, we can access data at any time from any connected machine (computer,
laptop, tablet, phone, etc.)
Disadvantages of data structure

 Only sophisticated users can make changes to the data structure
 Any problem involving the data structure requires the help of a specialist, which is that basic
users cannot help themselves.
P2 Determine the operations of a memory stack and how it is used to

implement function calls in a computer.
11
Memory Stack:
The operations of a memory stack
Stack memory is a memory usage mechanism that allows the system memory to be used as
temporary data storage that behaves as a first-in, last-out buffer. An example of a stack is illustrated
on the below:
Figure 1 Example of stacks / queues
Items in a stack are inserted or removed in a linear order and not in any random sequence. As in any
queue or collection that is assembled, the data items in a stack are stored and accessed in a specific
way. In this case, a technique called LIFO (Last In First Out) is used. This involves a series of
insertion and removal operations which we will discuss in the following section.
LIFO (Last In First Out)

When a stack is accessed (there are inserted or deleted items), it is done in an orderly manner by
LIFO. LIFO stands for Last In First Out. Computers use this method to request service data that the
computer's memory receives. LIFO dictates that data is last inserted or stored in any particular stack,
must be the first data to be deleted. If that applies to our queue for movies in Figure 1 above, there
will be chaos! The operations on the stack are discussed in the following sections with image on the
below:

12
Figure 2 : Last in First out
Stack Operations
The Push Operation
Push operation involves inserting data items into a stack. Let us check our restaurant plate dispenser
in Figure 9. Operation pushes additional plates (data items) into the plate dispenser (stack). The first
plate is pushed down to the bottom of the stack with all subsequent plates in the following order after
it. The first inserted data item is the most inaccessible and is located at the bottom of the stack.
The Pop Operation

Pop operation involves removing data items from the loaded stack. In our plate distributor
illustration, the last sheet (data item) added is placed at the top of the stack. This data item is turned
off the stack as the first item is deleted. Think of the spring loading system in the base of the plate
distributor. It pushes the stack on top each time you remove the plate. In memory, items continue to
be turned on in that order.
The Peek Operation

In this operation, no data items are added or deleted from the stack. The snapshot operation only
requires the address location of the data item at the top of the stack (the last item is pushed).

13
The Search Operation

In this operation, it does not have any data items are added or deleted from the stack. The search
operation requires that geographical local of any data items in the stack. It located the item at the top
of the stack.
How it is used to implement function calls in a computer stack memory in computers
The stack memory is a special kind of memory that is used to store information temporarily, when
we want to read the information correctly in the opposite direction to the recorded memory, without
caring about the organization data addressing. Stack memory is sequential memory with specify
access restrictions that allow writing and reading information to or from only one location in this
memory called the top of the stack. The stack memory acts as a queue where data can be written to
the top of the stack, while changing all the information stored in subsequent locations in a location
according to the depth of the queue. this. Can only read from the stack from the top of the stack.
Reading makes information from the top of the stack removed and a new information is recorded in
its place from the depth of the stack with the displacement of all information stored in one position to
the top. of stack. Then the queue is the last type to enter first. The stack memory works in the same
way as the rifle magazine, in which the introduction of a new bullet box pushes all the remaining
cartridges into the depths of the magazine and the use of cartridges (one shot) makes The top
cartridge is removed and replaced with the first cartridge under the used one. Three instructions are
used to manipulate the stack are push (write data into the stack), read stack (read the top of the
stack), pop (delete data from the top of the stack with a shift of its contents up). Sometimes,
symmetric operations involve the top two positions of the stack used as arguments and positions for
the results. After pure operation, pop operation is performed and results are available at the top of the
stack.

14
Figure 3 Stack functioning principles
The first stack deployment is based on the use of registers, in which data is moved in a parallel
manner during Push and Pop operations. Modern stack deployment is based on the main memory
usage supported by special registers that make it easy to access and manage the stack. A stack is
reserved by the operating system, sequences of consecutive memory locations. The boundary of the
stack is determined by two special registers - the stack base register and the stack limit register hold
the address of the stack top and lower boundary positions. The address space between these
addresses is excluded from other uses than the stack implementation. The top of the stack is
determined by keeping the address in the third register called the stack pointer register. Before the
computer starts executing the program, the top of the stack register is set to the contents of the stack
base register. After each Push operation, the contents of the stack pointer register are changed
according to the number of bytes corresponding to the stack in the stack limit direction. After each
Pop operation, the content of the stack pointer is changed in the direction of the stack base.
Figure 4 Stack implementation the computer- the top of the stack in the memory.
The figure above shows the organization of the stack in the main memory, in which the top of the
stack is accessed only in memory. Another solution, shown in the figure below, assumes that the top

15
of the stack and the position just below the top, is stored in special processor registers: the top of the
stack register and the top register -first.
Figure 5 Stack implementation in the computer- the top of the stack in registers..
Stack memory implements function call in computer

Among the instructions that control computers, we can find subroutine call instructions with the
acronym "Call" and instructions for returning subroutines with the acronym "Ret". A subroutine is a
series of instructions that end with the "Ret" return command. In the subroutine the subroutine
always has the address of the first instruction in a subprogram called the subroutine address.
Mechanism of subroutine calls and the execution of the "Call" i "Ret" commands based on the use of
the stack. Execute the "Call" subroutine command including:
3. stored in the stack of the program counter's current content (ie, the return address executes
the next instruction after the call) with the "Push" operation,
4. write to the program that accesses the embedded address in the "Call" guide,
5. take the next tutorial according to the new content of the program counter.
The address written to the stack will be used by the "Ret" return command to automatically return
from the subroutine to the next command.
Instructions "Call".
1. The return execution from the "Ret" subcommand includes:

16
2. Read from the top of the stack of the return address (to successfully instruct the "call"
command),
3. write this address to the program counter,
4. perform the "Pop" operation on the stack,
5. Fetch a new guide according to the new content of the program counter.
The address written to the stack in a subroutine call is sometimes called a trace and the subroutine
call is called a hop with a trace. Often use nested subroutine calls, in which during subroutine
execution, new subroutine is called from its body. The mechanism of returning from trace
subroutines stored in the stack allows to automatically return the next program call context with the
correct return order preserved. The figure below shows actions related to nested subroutine calls
from a top program thread. In the subroutine call 1 (Call 500 is stored at address 100), the return
address 101 is stored in the stack. In the call of subprogram 2 (Call 900 is written at address 600), the
return address 601 is saved in the stack. When returning from sub-program 2, address 601 is taken
from the stack. When returning from subroutine 1, address 101 is taken from the stack.
Figure 6 The use of stack in subroutine calls

17
M1 Illustrate, with an example, a concrete data structure for a First In First

out (FIFO) queue.
First in First out (FIFO) Queue:
A Queue is a linear structure which follows a particular order in which the operations are performed.
The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a
resource where the consumer that came first is served first. The difference between stacks and
queues is in removing. In a stack we remove the item the most recently added; in a queue, we
remove the item the least recently added.
Figure 7 FIFO Queue
FIFO Queue basic operations:

Linear operations may involve starting or defining a queue, using it, and then deleting it completely
from memory. Here we will try to understand the basic operations of a line -
enqueue () - add (save) items to a queue.
dequeue () - removes (access) items from the queue.
Enqueue Operation

18
o Queue maintains two data pointers, font and rear

o The following steps should be taken to enqueue (insert) data into queue:
Step 1: Check if queue is full
Step 2: if queue is full
Produce overflow error and exit
Else
Increment rear pointer to point next empty space and add data element to
The queue location, where rear is pointing.
Step 3: Return success.
Dequeue Operation
Accessing data from queue is a process of two steps
 Access the data from where font is pointing.

 And remove the data after access.
The following steps are taken to perform dequeue operation
Step 1: Check is queue is empty.

Step 2: if queue is empty
Produce underflow error and exit
Else

19
Access data where font is pointing, increment font pointer to point next available data
element.
Step 3: Return success.
Some more functions are needed to make the above-mentioned queue operations effective. This is:
peek () - Gets the element in front of the queue without removing it.
isfull () - Check for full rotation.
isempty () - Check if the line is empty.
Example
FIFO is an abbreviation for first in, first out. It is a method for handling data structures where
the first element is processed first and the newest element is processed last.
In this example, following things are to be considered:

20
 There is a ticket counter where people come, take tickets and go.
 People enter a line (queue) to get to the Ticket Counter in an organized manner.
 The person to enter the queue first, will get the ticket first and leave the queue.
 The person entering the queue next will get the ticket after the person in front of him
 In this way, the person entering the queue last will the tickets last
 Therefore, the First person to enter the queue gets the ticket first and the Last person to enter
the queue gets the ticket last.
M2 Compare the performance of two sorting algorithms

Bubble Sort
Bubble Sort is a basic calculation used to manage or arrange a lot of n elements in an array with n
quantities of elements. Sort Bubble to analyze all the elements individually and compose them by
their qualities. In the event that the given array should be organized in ascending order, at that point
the bubble type will begin by contrasting the main component of the array with the subsequent
component, if the primary component is bigger than the subsequent component, it will change the
two elements, and afterward proceed onward to think about the second and third elements, and so on.
In the event that we have a sum of n elements, at that point we have to rehash this procedure for n-
multiple times. This is known as a bubble type, on the grounds that with each total emphasis of the
biggest component in a given array, it bubbles towards the last spot or most noteworthy index.
The bubble sort algorithm is performed using the following steps:
Step 1: Starting with the first element (index = 0), compare the current element with the next element
in the array.
Step 2: If the current element is larger than the next element in the array, swap it.
Step 3: If the current element is less than the next element, move to the next element. Repeat Step 1.
Example of bubble sort:

Consider an array with values:
1st iterations:

21
6 2 7 3 5 4
As you can see the number on the above the number are not sorted. So we are going to sort it from
ascending to descending.
6 2 7 3 5 4
We can starts with first two element 6 > 2, 2 is small, so swap the value.
2 6 7 3 5 4
7 > 3, 3 is small, so swap the value
2 6 3 7 5 4
After we swap 7 with 3, now we can see that we can still swap the 7. 7 > 5, 5 is small so we can
swap the value
2 6 3 5 7 4
Next, 7 > 4, 4 is small so we can swap the value.
2 6 3 5 4 7
So, this is the results of 1 st iteration which is 2, 6, 3, 5, 4 and 7. We can see the number still not
sorted in ascending order so we have to do the 2nd iteration.
2
nd
iterations:
2 6 3 5 4 7
Now we can start from the second two element which is number 6. 6 > 3, 3 is small so we have to
swap the value.
2 3 6 5 4 7

22
Next, 6 > 5, 5 is small so we will swap the value
2 3 5 6 4 7
6 > 4, 4 is small so we have to swap the value
2 3 5 4 6 7
Now, after the 2nd iteration we almost reach it, we can see the number almost in order except for
number 4. So to make sure have the perfect order, we will continue by 3rd iteration.
3
rd
iterations:
2 3 5 4 6 7
5 > 4, 4 is small so we will swap the value
2 3 4 5 6 7
Now, the number in every element is in the correct place. So once we get the perfect ascending order
we will stop now. So, the 3rd iteration the ascending order is 2, 3, 4, 5, 6 and 7. But keep in mind you
still did not sorted the number you have to continue by 4th iteration.
Selection Sort
Selection sort is the simplest conceptual sorting algorithm. This algorithm will begin to find the
smallest element in the array and replace it with the element in the first position, then it will find the
second smallest element and swap it with the element in the second position, and it will continue to
do this until the entire array is sorted. It is called a selection sort because it repeatedly selects the next
smallest element and moves it to the right place. The Selection Sort Algorithm is used to organize the
list of elements in a particular order (Ascending or Descending). The type of selection, the first
element in the list is selected and it is compared repeatedly with all the remaining elements in the
list. If any element is smaller than the selected element (for Ascending order), both are changed so
that the first position is filled with the smallest element in the sort order. Next, we select the element
in the second list and compare it to all the remaining elements in the list. If any element is smaller
than the selected element, then both are changed. This procedure is repeated until the entire list is
compiled.
23
The selection sort algorithm is performed using the following steps:
Step 1: Select the first element in the list (that is, Elements in the first position in the list).
Step 2: Compare selected elements with all other elements in the list.
Step 3: In each comparison, if any element is found to be smaller than the selected element (for
Ascending order), then both are changed.
Step 4: Repeat the same procedure with the element in the next position in the list until the whole list
is sorted.
Example of selection sort:

Consider the following unsorted list of elements:
15 20 10 30 50 18 5 45
1 iteration:
st
5 20 15 30 50 18 10 45
2
nd
iteration:
Select the second position element in the list, compare it with all other elements in the list and
whenever we found a smaller element than the element at first position then swap those two
elements.
5 10 20 30 50 18 15 45
3
rd
iteration:
Select the third position element in the list, compare it with all other elements in the list and
elements.
5 10 15 30 50 20 18 45

24
4
th
iteration:
Select the fourth position element in the list, compare it with all other elements in the list and
elements.
5 10 15 18 50 30 20 45
5
th
iteration:
Select the fifth position element in the list, compare it with all other elements in the list and
elements.
5 10 15 18 20 50 30 45
6
th
iteration:
Select the sixth position element in the list, compare it with all other elements in the list and
elements.
5 10 15 18 20 30 50 45
7
th
iteration:
Select the seventh position element in the list, compare it with all other elements in the list and
elements.
5 10 15 18 20 30 45 50
Final sorted list

25
Comparison between bubble sort and selection sort:
Bubble sort Selection sort
Adjacent element is compared Largest element is selected and swapped with the last element
and swapped (in case of ascending order).
Time complexity is O(n) Time complexity is O(n2)
Inefficient Improved efficiency as compared to bubble sort
It is stable It is not stable

Exchanging method Selection method
It is slow Fast as compared to bubble sort
In the bubble sort, each element and the adjacent element are compared and swapped as needed. On
the other hand, the selection sort works by selecting the element and replacing the specific element
with the last element. The selected element can be the largest or the smallest depending on the order,
ascending or descending. The complexity of the worst case is the same in both algorithms, namely,
O (n2), but the best complexity is different. Bubble arrays take n time sequences while selection
types use n2 sequences. Bubble sort is a stable algorithm, in contrast, selection sort is unstable. The
selection algorithm is fast and efficient compared to very slow and inefficient bubble sort. The
bubble sort algorithm is considered to be the simplest and inefficient algorithm, but the selection sort
algorithm is more efficient than the bubble sort. Bubble sort also use extra space to store temporary
variables and require more swaps.

26
D1 Analyze the operation, using illustrations, of two network shortest path

algorithms, providing an example of each.
Network shortest path algorithms:

1. Bellman-Ford Algorithms
Bellman-Ford algorithm solves the problem of single source in the general case, in which edges can
have negative weights and oriented graphs. If the graph is not guided, it will have to be modified by
including two edges in each direction to make it oriented. Bellman-Ford has assets that can detect
negative weight cycles accessible from the source, which means that no shortest path exists. If there
is a negative weight cycle, a path can run indefinitely on that cycle, reducing the path cost down.
Without a negative weight cycle, Bellman-Ford returned the weight of the shortest road along the
same road.
How the Bellman-Ford Algorithms work?
The Bellman Ford algorithm works by overestimating the length of the path from the starting peak to
all other vertices. After that, it repeats those estimates by finding new paths shorter than previously
overestimated paths. Like other dynamic programming problems, the algorithm calculates the
shortest path in a bottom-up way. First, it calculates the shortest distance that has at most one edge in
the path. Then it calculates the shortest path with up to 2 edges, etc. After the iteration of the external
loop, the shortest path with at most i edges is calculated. There may be a maximum | V | - 1 edge in
any simple path, that's why the outer loop runs | v | - 1 times. The idea is, assuming that there is no
negative weight cycle, if we have calculated the shortest paths with most edges i, then repeating on
all edges ensures the shortest path to be given the most edges (i + 1). Below are the detailed steps
used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices
in the given graph. Given a graph and a source src peak in the graph, find the shortest path from src
to all vertices in the given graph. The chart may contain negative weight edges.

27
Algorithm
 Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest
path tree, i.e., whose minimum distance from source is calculated and finalized. Initially,
this set is empty.
 Assign a distance value to all vertices in the input graph. Initialize all distance values as
INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
 While sptSet doesn’t include all vertices
 Pick a vertex u which is not there in sptSet and has minimum distance value.
 Include u to sptSet.
 Update distance value of all adjacent vertices of u. To update the distance values,
iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance
value of u (from source) and weight of edge u-v, is less than the distance value of v,
then update the distance value of v. To better understand how it works as well as the
algorithm of the Bellman Ford Algorithm, we will provide you with an example. Set
the source vertex given to 0. Initialize all distances as infinite, except the distance to
the source itself. The total number of vertices in the graph is 5, so all edges must be
processed 4 times.
Let all edges be processed in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), ( B,
C), (E, D). We get distance after all edges are processed for the first time. The first row in the
original distance. The second row shows the distance when the edges (B, E), (D, B), (B, D) and (A,
B) are processed. The third row displays the distance when (A, C) is processed. The fourth row
displayed when (D, C), (B, C) and (E, D) are processed.

28
The second iteration ensures that all the shortest paths are at most 2 edges long. The algorithm
handles all edges 2 more times. The distance is minimized after the second iteration, so the third
iteration and the fourth time do not update the distance.
2. Dijkstra’s Algorithm
Dijkstra's algorithm uses the first width search (not the single-source shortest path algorithm) to
solve a single source problem. It places a constraint on the graph: it cannot have negative weight
edges. However, with one limitation, Dijkstra significantly improved the running time of Bellman.
Dijkstra's algorithm is sometimes also used to solve the shortest path problem of all pairs by simply
running it on all internal vertices. Again, this requires all edge weights to be positive. Dijkstra's
algorithm allows you to calculate the shortest path between a node (you choose which button) and
every other node in the graph.
How Dijkstra's Algorithm works
Djkstra's algorithm works on the basis that all B -> D paths of the shortest path A -> D between
vertices A and D are also the shortest path between vertices B and D.

29
Djikstra used this property in the opposite direction, that is, we overestimate the distance of each
vertex from the start. Then we visit each of its nodes and neighbors to find the shortest path to those
neighboring nodes. The algorithm uses a greedy approach in the sense that we find the next best
solution in the hope that the end result is the best solution for the whole problem. For instances,
calculate the shortest path between node C and the other nodes in the chart below:
During the execution of the algorithm, we will mark every node with the minimum distance to the C
button (our selected node). For node C, this distance is 0. For the rest of the nodes, since we still
don't know the minimum distance, it starts with infinity (∞):
We will also have an existing node. Initially, we set it to C (our selected button). In the picture, we
mark the current button with a red dot. Now, we check the neighbors of our current node (A, B and

30
D) in no particular order. Let's start with B. We add the minimum distance of the current node (in
this case 0) with the weight of our current connection node with B (in this case 7) and them I have 0
+ 7 = 7. We compare that value to the minimum distance of B (infinity); the lowest value is the
remaining value is the minimum distance of B (in this case, 7 is smaller than infinity):
As far as possible. Now, check neighbors A. We add 0 (the minimum distance of C, our current
node) with 1 (the weight of our current connected node with A) to get 1 We compare 1 with the
minimum distance of A (infinity) and leave the smallest value:
Repeat the same process for D:
Then, we checked all neighbors of C. Because of that, we marked it as accessed. Please indicate the
buttons accessed with a green check mark:
31
Now we need to select a new existing node. The button must be an unwanted node with the smallest
minimum distance (so the node has the smallest number and no check marks). That is A. Please mark
it with a red dot:
And now we repeat the algorithm. We check our current node's neighbor, ignoring the accessed
buttons. This means we only test B. For B, we add 1 (minimum distance of A, our current node) to 3
(weights of edges A and B) to get 4. We compare 4 with minimum distance of B (7) and leave the
smallest value: 4.

32
Then we marked A as visited and selected a new existing node. D, which is the non-access node with
the smallest current distance.
We repeat the algorithm again. This time, we checked B and E. For B, we get 2 + 5 = 7. We compare
that value to the minimum distance of B (4) and leave the minimum value (4). For E, we obtain 2 + 7
= 9, compare it with the minimum distance of E (infinity) and leave the smallest (9). We marked D
as accessed and put our current button into B.
So, we just need to check E. 4 + 1 = 5, smaller than the minimum distance of E (9), so we leave 5.
After that, we marked B as accessed and set. E is the current node.

33
Since no buttons are not provided, we are done! The minimum distance of each node now actually
represents the minimum distance from that node to the C button (the button we chose as the original
button)
P3 Using an imperative definition, specify the abstract data type for a

software stack.
ADT for software stack:
Specify the abstract data type for a software stack

A software stack is a set of programs that work together to produce a result, typically an operating
system and its applications. For example, a smartphone software stack comprises the operating
system along with the phone app, Web browser and other basic applications. A software stack may
also refer to any group of applications that work in sequence toward a common result or any set of

34
utilities or routines that work as a group. See stack, application stack and protocol stack. In addition,
to allow them to work together, the required abstract data types such as Stack (LIFO) and Queue
(FIFO).
So, in order to better understand the software stack, we find out about stack operation on Android
device. For each application running on an Android device, the runtime system will maintain an
active Stack. When an application is executed, the application's first operation is started to be placed
on the stack. When a second operation is started, it is placed on the top of the stack and the previous
activity is pushed down. Operation at the top of the recommended stack is active (or running). When
the operation is exited, it is turned off the stack by the running time and the operation is located just
below it in the stack to become the current activity. Operations at the top of the stack can, for
example, just exit because the stack it is responsible for has been completed. In addition, the user
may have selected the Back on screen button to return to the previous activity, causing the current
activity to be disconnected from the stack by the runtime system and therefore destroyed. A visual
representation of the Android Activity Stack is illustrated in Figure below:
As show in the diagram, new activities are pushed on to the top of the stack when they are started.
The current actiive activity is located at the top of the stack until it is either pushed down the stack
by a new activity, or popped off the stack when it exits or the user navigates to the previous activity.
In the event that resources become constrained, the runtime will kill activities, starting with those at
the bottom of the stack. The Activity Stack is what is referred to in programming terminology as a

35
Last- In- First- Out (LIFO) stack in the last item to be pushed onto the stack is the first to be popped
off.
M2 Examine the advantages of encapsulation and information hiding when

using an ADT.
Encapsulation is one of the basic concepts in object-oriented programming (OOP). This concept is
also often used to hide internal representations, or conditions, of objects from the outside. This is
called hiding information. It hides internal conditions and requires that all interactions take place
through object methods known as data encapsulation, the basic principles of object-oriented
programming. encapsulation is the process of grouping or packing data and the function to perform
actions on data into a single unit. Single units are called classes. Such encapsulation is enclosed in a
capsule. It attaches operations and data associated with the object to the object. It stores data and
codes securely from external interruptions. The need for encapsulation is to protect or prevent code
(data) from accidental bribery because of the silly little mistakes we all tend to make. In object-
oriented programming data Objects are considered as critical elements in program development and
data is closely packed with the functions that operate on it and protects it from accidental
modification of external functions. Encapsulation provides a way to protect data from accidental
corruption. Instead of defining data in the public form, we can declare that field as private. Personal
Data is indirectly manipulated in two ways. Let's look at some examples of programs in C # to show
Encapsulation by both methods. The first method uses a pair of conventional accessories and mutator
36
methods. Another method is to use the named property. Regardless of our method the goal is to use
data without any damage or alteration.
Advantages of encapsulation
Data encapsulation, sometimes referred to as data hiding, is the mechanism whereby the
implementation details of a class are kept hidden from the user. The user can only perform a
restricted set of operations on the hidden members of the class by executing special functions
commonly called methods. The actions performed by the methods are determined by the designer of
the class, who must be careful not to make the methods either overly flexible or too restrictive. This
idea of hiding the details away from the user and providing a restricted, clearly defined interface is
the underlying theme behind the concept of an abstract data type.[ CITATION Don96 \l 1033 ]
The advantage of using data encapsulation comes when the implementation of the class changes but
the interface remains the same. For example, to create a stack class which can contain integers, the
designer may choose to implement it with an array, which is hidden from the user of the class. The
designer then writes the pus() and pop() methods which puts integers into the array and removes
them from the array respectively. These methods are made accessible to the user. Should an attempt
be made by the user to access the array directly, a compile time error will result. Now, should the
designer decide to change the stack's implementation to a linked list, the array can simply be
replaced with a linked list and the push() and pop() methods rewritten so that they manipulate the
linked list instead of the array. The code which the user has written to manipulate the stack is still
valid because it was not given direct access to the array to begin with.[ CITATION Don96 \l 1033 ]
 To sum up, the advantages of data encapsulation and information hiding are:
 Protecting an object from unwanted access by client.
 Allowing access to a level without revealing the complex details below that level
 Reducing human errors.
 Simplifies the maintenance of the application
 Making the application easier to understand.
Conclusion:
Encapsulation is the first step towards object-oriented programming. Using the pointer and mutator
method we can encapsulate. Another method is to use the named property. The advantage of this is
that your object users can manipulate internal data points using a single named item.
37
D2 Discuss the view that imperative ADTs are a basis for object orientation
and, with justification, state whether you agree.
Almost people known that Object-orientation programming based on the concepts of “objects”,
which can contain data, in the form fields (attributes), and code, in the form of procedures. But the
reality when we look at the development process of the development process is that we can see the
emergence of programming structures, firstly linear programming, to structural programming,
abstraction. turn data into object-oriented programming. We see the appearance of fear of data
abstraction appearing before the opposite programming. As everyone knows, structured
programming has a lot of weaknesses, so the birth of object-oriented programming is to overcome
those weaknesses and at the same time incorporate the character of data abstraction. Data into it,
create a complete programming structure. Object-oriented programming is built on the basis of
structured programming and data abstraction. The fundamental change is that an object-oriented
program is designed around data that we can work on, rather than following the function of the
program itself. This is completely natural once we understand that the goal of the program is to
process data. After all, the work that computers perform is often called data processing. Data and
manipulation are linked at a basic level (also called a low level), each of which requires a specific
goal, object-oriented programs to explicitly relationship. this. Object-oriented programming links the
data structure to operations, in a way that all often think about the world around them. We often
associate certain activities with a certain type of activity and put our assumptions on relationships.
Data abstraction acts on data as well as functional abstraction. When data abstraction, data structures,
and elements can be used without bothering with specific details. For example, floating point
numbers have been abstracted in all programming languages. We don't need to care about which
exact binary representation for the number of floating points when assigning a value, nor need know
the abnormality of binary multiplication when multiplying floating point values. It is important that
floating point numbers work properly and understand. In general, an ADT is a type of data that can
be represented in a computer, basically defined on that type, and can be customized with packaging
and hiding information using public keywords, protected and private in class declarations. For
example, a stack can be treated as an object when processed as an array or linked with push () or pop
() customizations and hide information.

38
From that point on, object-oriented programming achieves abstraction of data using procedural
abstraction, while abstract data types depend on type abstraction. In addition, objects are focused on
functions that create data abstraction, while ADT is organized around operations.
Object-oriented programming has the following characteristics:
 Abstraction: This is the ability of the program to ignore or ignore certain aspects of
information that it is working on directly, which means it has the ability to focus on the core
elements. Each object can complete internal tasks, report, change state and communicate with
other objects without knowing how the object performs the operation. Abstraction is also
expressed by the fact that an initial object may have some common characteristics, such as its
extension but the original object may not be the method to execute.
 Encapsulation: This property does not allow users to change the state of the object. Only the
object's internal methods allow it to change its state. Allow the external environment to affect
the internal data of an object in any way completely dependent on the encoder. This is the
assurance of the integrity of the object.
 Polymorphism: Expressed by sending messages. Send a comparable message to the function

of an object. The method used to reply to the message will depend on the object to which the
message is sent will respond differently. Programmers can define an attribute for a series of
objects close together, but when executed, they use the same name, automatically execute
each object according to the characteristics of each object without being mistaken. mixed.
 Inheritance: This property allows the object to have available properties that other objects
have inherited. This attribute allows the object to share or expand existing allocations without
specifying.

39
From these characteristics, object-oriented programming has the basic characteristics of ADTs (data
abstraction), and it also adds polymorphism and inheritance. Therefore, it is said that ADT (abstract)
is the foundation of OOP and the remaining principles derive from it to complement it

40

Data Structure and Algorithm: Buddhi Raj Gurung

Uploaded by

Copyright:

Available Formats

Data Structure and Algorithm: Buddhi Raj Gurung

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structure and Algorithm: Buddhi Raj Gurung

Uploaded by

Copyright:

Available Formats

2020 Data Structure and

HND/ Third Semester Sec-B)

My Role as System Software Developer............................................................................................6

Types of data structures.............................................................................................................9

Advantages of data structure...........................................................................................................9

The Push Operation......................................................................................................................11

Stack memory implements function call in computer..................................................................14

FIFO Queue basic operations:......................................................................................................16

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

Example of bubble sort:................................................................................................................20

Example of selection sort:.............................................................................................................23

Network shortest path algorithms:....................................................................................................26

ADT for software stack:.............................................................................................................34

Specify the abstract data type for a software stack.......................................................................34

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

P1 Create a design specification for data structures explaining the valid

 The orders are collected locally at the sales outlets.

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

My Role as System Software Developer

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

My<T> is considered as a node.

+ info: T - object data carried by this node, could be any types.

- More information about Linked List will be provided in section II.1

Class MyStackT<T> and MyQueueT<T>

- Contain information of one Product. It has 5 values:

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

 price: double - The price of the product.

- Contain information of one Customer. It has 5 values:

Contain information of one Ordering. It has 3 values:

 pcode (string) - the code of the product to be ordered.

Class OrderingList, CustomerList and ProductList

Design Specification Case Study

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

Name PrintableString|SIZE((1.20)), street Printable

Delivery-report::=SEQUENCE{ Order-code Order-number, delivery SEQUENCE OF Delivery-

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

Types of data structures

1. Primitive Data Structures

2. Non-Primitive Data Structures

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

Advantages of data structure

Disadvantages of data structure

P2 Determine the operations of a memory stack and how it is used to

Figure 1 Example of stacks / queues

LIFO (Last In First Out)

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

Figure 2 : Last in First out

The Pop Operation

The Peek Operation

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

The Search Operation

How it is used to implement function calls in a computer stack memory in computers

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

Figure 3 Stack functioning principles

Buddhi Raj Gurung (HND/ Third Semester Sec-B)

Stack memory implements function call in computer

1. The return execution from the "Ret" subcommand includes:

Buddhi Raj Gurung (HND/ Third Semester Sec-B)