Data Structures and Algorithms Report: A Comprehensive Analysis

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

Contents
Introduction......................................................................................................................................2
LO1..................................................................................................................................................3
P1.................................................................................................................................................3
P2.................................................................................................................................................5
M1................................................................................................................................................6
M2................................................................................................................................................7
D1................................................................................................................................................9
LO2................................................................................................................................................10
P3...............................................................................................................................................10
M3..............................................................................................................................................11
D2..............................................................................................................................................12
LO3................................................................................................................................................12
P4...............................................................................................................................................12
P5...............................................................................................................................................12
M4..............................................................................................................................................12
D3..............................................................................................................................................13
LO4................................................................................................................................................14
P6...............................................................................................................................................14
P7...............................................................................................................................................15
M5..............................................................................................................................................16
D4..............................................................................................................................................17
Conclusion.....................................................................................................................................18
References......................................................................................................................................19

Figure 1: Chart of singly linked list.................................................................................................4
Figure 2: Data flow diagram of SMS..............................................................................................5
Figure 3: BFS.................................................................................................................................11
Figure 4: DFS................................................................................................................................12
Figure 5: Floyd-Warshall algorithm..............................................................................................13
Figure 6: Dijkstra’s Algorithm......................................................................................................14
Figure 7: Abstract data type...........................................................................................................15
Figure 8: Encapsulation.................................................................................................................17
Figure 9: Information Hiding.........................................................................................................18
Figure 10: Error handling example................................................................................................19
Figure 11: Stack Abstract data type Array implementation..........................................................20
Figure 12: Stack Abstract data type Linked list implementation..................................................20
Figure 13: Queue Abstract data type array implementation..........................................................21
Figure 14: Queue Abstract data type linked list implementation..................................................21
Figure 15: Complexities of different algorithms...........................................................................22

Introduction
The report is based on the discussion on data structures as well as on C#. For every part, there
are different discussions that have made for the understanding of the user. The report contains all
the part of the assessment so as to gain a distinction in the assessment. Data structures like
queue, arrays, stacks and other points are covered. The abstract data type is discussed in detail.
The discussion on asymptotic notation is also made and the program is also created with the help
of c# sharp and id discussed with proper explanation.

LO1
P1
Data structures are considered as the collection and organization of data or information in which
the operations are performed in an attractive and efficient way.
For the purpose of design specification, the used data structures are implementation of the link of
a stack, singly linked list, implementation of linked of a queue. We use these data structures for
the SMS's data because it is easy and uncomplicated for implementation.
Singly linked list: Singly linked list contains the list which has two different data fields' nodes:
next and info. The important thing for the user is the info field because it stores the information.
The next field is generally linked up with the successor and all the link up should be in the
sequence.
The figure shows a linked list of integer:
Figure 1: Chart of singly linked list
Stack:
A stack is referred to as the linear data structures which can be accessed from the end point of
nodes and used for the sorting and data retrieving. The addition of the elements has only
occurred on the top of the stack and it generally, follows the data structure LIFO.
Queue:

A queue is considered as the waiting line which increases with the addition of the elements to the
nodes and all the elements are added up from the front. It uses both th4e nodes in which one is
used for the addition and another one for the removing of the elements.
Advantages of singly linked list:
Adding and removing elements can do easily.
According to the requirements, the size can be increase and decrease.
Space is also saved because it is used according to the necessities.
For the insertion and removing, the movement of elements is not required.
Figure 2: Data flow diagram of SMS
DFD:
It shows the whole process of the system, it starts with ordering the product through the
customers and then the manager will check out whether the product is available or not. The

admin of the system maintains the system regularly and if the product is available, it sends out to
the customer with the proper billing and at last the customer also checks the bill there.

P2
Memory stacks are used to store the data in the system and the data structures are linear. The
data should always be of the same type in the stack.
Operations involved in memory stack are:
 The PUSH operation
The push operation is used for the addition of the information items in the stack. The
overflow condition has come in existence when the stack is overloaded. The data inserted
first is become the last one for the stack.
 The POP operation
The pop operation is used to deleting the data from the overloaded stack. The elements
can be continuously popped out through the memory when the items from the bottom
continually pushed upper elements to be removed.
 The Peek operation
The addition and deletion of the items are not performed in this operation. It is generally
used to demand the address position of any records from the stack.
 The Search operation
In accordance with the location of the topmost items from the stack, it also establishes the
position.
Example of stack implementation:
Operation Stack contents Return
Create
Push(55)
Push(-7)
Push(16)
Pop
Push(-8)
Push(23)
Pop
0
(55)
(-7,55)
(16,-7,55)
(-7,55)
(-8,-7,55)
(-8,-7,55)
(-7,55)
1
1
1
16
1
0
-8

Pop
Pop
Pop
(55)
0
0
-7
55
101

M1
It is the representation of the settled solution, a single domain concept that is an oriented data
type. Instead of its particular use, the data can be used further on the different instant of time. It
can also be mixed up with different data types and make a system of huge data types. It can also
be introduced through the data constructor it can be possible that they focused on the
parameterized data type for some definite condition.
For example Bool, tree string, etc
Concrete data structures are referred as the structures of an event which are generated by the
combination of two things, one is a cell which is referred as the static part and another one is the
value which is referred as the dynamic part. The main motivation of using the concrete data
types is that in lithe structure, it examines the notion for the process of explicit through the
processors which are explicit through the mapping of cells.
The cds Bool = ({B}; {V; F}; {BV; BF}; { B}) and Nat = ({N}; N; {Nn | n∈ N}; { N}) generate
the flat domains of booleans and naturals, respectively:
BF BV N0 N1 Nn …
↑ ↑
∅ ∅
The cds Vnat = (N; { }; {n | n∗ ∗ ∈ N}; { 0}∪{n n + 1}) generates the domain of lazy∗
naturals:
{n | n∗ ∈ N}
. . .
↑
{0 ; 1 }∗ ∗
↑

{0 }∗
↑
∅

M2
BFS and DFS:
BFS algorithm:
The breadth-first search is referred to as the traversal algorithm for the graphs in which the
traversing is starting from the main root and covers all the neighboring ends. And, then proceed
with the close node and transverse through the rest of the nodes. The algorithm remains the same
for the whole process to transverse up all close nodes up to reaching the nodes.
This algorithm is best for queue operations. The process of algorithm is starting from the main
root A and then proceeds in accordance with the neighboring elements. Further, close elements
of the end A discover and the process remains to continue and stops whenever finds the goal.
The evaluation of each node is only done once.
Algorithm of BFS:
Step 1: SET STATUS = 1 (State ready)
For each node of G
Step 2: Starts enqueuing from node A
Set its STATUS = 2
Step 3: Repeat steps 4 and 5
QUEUE is empty
Step 4: Dequeuing of node N
Set its STATUS = 3
Step 5: Enqueuing of all neighbors which are in ready state
Set their STATUS = 2
[LOOP END]

Step 6: EXIT
Figure 3: BFS
DFS algorithm:
Depth-first search is the algorithm that initiates from the end G. and then goes into the depth of
the neighbors until it reaches the goal, it means up to the state where the children of the nodes are
not found. Then it comes across the other node which is not explored and then proceeds with the
same process.
This algorithm is mainly used in the stack structure. It is too much similar to the BFS. Discovery
edges are that in which the edges are leading with the un-traversing nodes and block nodes are
those in which the edges are traversed.
Algorithm of the DFS:
Step 1: SWET STATUS = 1(state ready)
For each node of G
Step 2: push node A(starting)
Set its STATUS =2
Step 3: repetition of step 4 and 5