Implementation and Analysis of Data Structures and Algorithms in C#

Desklib provides past papers and solved assignments for students. This report covers data structures and algorithms.

Data Structure and Algorithm

Contents
Introduction:...............................................................................................................................4
LO1:...........................................................................................................................................5
P1............................................................................................................................................5
P2............................................................................................................................................7
M1..........................................................................................................................................8
M2........................................................................................................................................10
LO2:.........................................................................................................................................11
P3..........................................................................................................................................11
M3........................................................................................................................................13
LO3:.........................................................................................................................................14
P4..........................................................................................................................................14
P5..........................................................................................................................................23
M4........................................................................................................................................25
LO4:.........................................................................................................................................26
P6..........................................................................................................................................26
P7..........................................................................................................................................28
M5........................................................................................................................................30
Conclusion:..............................................................................................................................31
References:...............................................................................................................................32
List of Figures
Figure 1: Queue structure...........................................................................................................5
Figure 2: a Stack structure..........................................................................................................6
Figure 3: Abstract dataType.....................................................................................................11
Figure 4: Stack Representation................................................................................................12
Figure 5: MainImplementQueue screenshot 1.........................................................................14
Figure 6: MainImplementQueue screenshot 2.........................................................................15
Figure 7: MainImplementQueue screenshot 3.........................................................................15
Figure 8: queue Screenshot 1...................................................................................................16
Figure 9: queue Screenshot 2...................................................................................................17
Figure 10: queue Screenshot 3.................................................................................................17
Figure 11: queue Screenshot 4.................................................................................................18
Figure 12: queue Screenshot 5.................................................................................................18

Figure 13: output screen 1........................................................................................................19
Figure 14: output screen 2........................................................................................................19
Figure 15: output screen 3........................................................................................................20
Figure 16: output screen 4........................................................................................................20
Figure 17: output screen 5........................................................................................................21
Figure 18: output screen 6........................................................................................................21
Figure 19: output screen 7........................................................................................................22
Figure 20: output screen 8........................................................................................................22
Figure 21: Worst case complexity............................................................................................27
Figure 22: graph for space requirement...................................................................................29
List of Tables
Table 1: Test cases table..........................................................................................................23

Introduction:
As the given scenario demands a well-designed and optimal code for their project that is
basically based on IOT i.e. Internet of things. So, as per the requirements are given by the
company of using less space as well as less time execution of the program, we are going to
use trade-offs such as space-time as well as time-memory trade-offs. We will also create our
own abstract data types to resolve the above problems. For the coding part, we are going to
create an Array List using Queue which further performs different operations. We will also
explain asymptotic notations and their types as well as use the best sorting algorithm to make
it optimal.

LO1:
P1
Data Structure: Data Structure is a technical way of storing and organizing the data so that
data can be used efficiently and easily whenever required. Examples of data structure can be
Linked-list, Arrays, Queue, Stack etc. Data Structures are used on a mass scale in nearly
every face of Computer Science i.e. Operating System, Compiler Design, Artificial
Intelligence, Graphics etc.
Queue: Data structure used in this case is Queue. We have used an Array List as a base Data
Structure and implemented a queue data structure. In Queue front, part is for deleting the
elements and rear part is to add the element in the queue. It mainly focusses on FIRST IN
FIRST OUT process. We can understand this with an example of people standing in a queue
for buying bus tickets at bus-stand. Common operations being performed in queue are
enqueue(), dequeue(), peek(), isFull(), isEmpty(), head(), size() and capacity().
Figure 1: Queue structure
(Source: GeeksforGeeks, 2019)
Stack: Stack is a popular data structure that is used in various data representation. It is open
from one end only that performs push() and pop() operations. The stack is capable of
performing multiple operations at one end only i.e. top of the stack. Push() operation used to
add data item in the queue and pop() operation used to remove the data item from the queue.
It is based on LIFO abbreviated as Last in first out.

Figure 2: a Stack structure
(Source: GeeksforGeeks, 2019)

P2
Stack is an abstract data type that works on the principle of LAST IN FIRST OUT. We can
understand it by a real-world example as a set of plates being placed on a table so the one
being kept at the last will be taken first. The two operations that are being performed in stack
are POP() and PUSH().POP() is being used to remove most current element in the stack
whereas PUSH() is being used to insert value in the stack.
Function call() is being made the function are entered on stack. These arguments further
indicated using base pointer. Then further, it returns its caller, arguments for returning
functions are being extracted from stack by using LIFO principle.

M1
FIFO is the principle of Queue where the elements entered first is being eliminated first from
the queue taking the real-world example for better understanding we can see that during a
traffic jam, the cars aligned first move first then the one aligned later. Now, let us understand
with an example –
In this example, we will see the creation code of queue. Also, we will see how to display the
elements and use the Count and Contain methods being used in the queue.

Explanation:
1. First step, I had declared the Queue formation. Here I have declared queue as variable to
clasp the variables of the Queue.
2. Then, we have added three variables to the Queue using the enqueue method.
3. We used an operation called count() to get the total number of elements in the Queue.
4. We also used an operation called contains() that returns either true or false as an output if
the given value is present or not in the queue.

M2
Sorting can be defined as a process of arranging items systematically. If we have a lot of data
that is kept unordered and we, therefore, aren’t able to get the data we need so to make it
easier to get the required data in time we go for sorting. There are different types of sorting
techniques that are being used such as Bubble sort, insertion sort, quick sort, Heap sort,
merge sort, Selection sort etc. Here we are asked to compare two sorting techniques that are
quicksort and bubble sort. Bubble sort is the technique of sorting in which two adjacent
elements are being compared and exchanged if they are out of order, this process goes on
until the array gets sorted whereas Quicksort is a sorting technique in which the complete
array gets decomposed into 2 parts, in the initial part all elements were equal or less than
pivot values and another part contains the values which are superior or equals to the pivot
values. Finally, sorting of both parts is being done recursively (Ilves, et al, 2015).
Comparison: Now, comparing the two algorithms on the basis of performance, Quicksort is
more efficient as compared to Bubble sort. It has a normal time complexity as O(n^2) which
can be explained as for 2 elements in the array 4 operations are needed to be performed, for 3
there would 9 operations and so on. This would become really hectic if the number of
elements in the array gets increased. Now, Quicksort has an average complexity of O(nlogn),
so it is much efficient than bubble sort, whereas if compared from the beginner’s point of view
bubble sort is much easier to use.

LO2:
P3
Abstract Data Type: Abstract Data Type (ADT) is a data type, just like any other primitive
data types. ADT consists of operations, values of underlying data as well as constraints of the
operation. Stack works on LIFO principle where the item pushed at last is being popped out
first. It basically has its own attributes and functions for its operations. The functions or we
can say the basic operations of stack are hidden from the main code of the program. Let us
understand it with an example like Push is used to push an element from the stack without
this function being defined inside the main function. Actually, it is the concept on which an
abstract data type works. So, stack, therefore, is an ADT (Fürst, et al, 2016).
Figure 3: Abstract dataType
(Source: Miller, B., et al., 2013)
Pages are being stored by the browser to remember and can be used when required and if we
press the back button it does not send the request to the server instead of it, it just see the
cache where the pages are being stored and the most importantly it uses LIFO principle so the
datatype being used is stack. As the operation suggests, the page is being shown on the screen
is pushed at the end so when we perform or click on back button, pop operation is performed
and we reach to the previous page.

Figure 4: Stack Representation
(Source: Btechsmartclass, 2019)
Software stack as an Abstract data type:
Stack is an ADT that contains a homogeneous type of data items in the data structure and all
the operations related to the stack are performed at the top of the stack. It is used for data
storage that stores data in a sequential manner. The operations specified for the Stack data
structure are:
 Push()- operation used for inserting data item from the stack.
 isEmpty()- returns true if stack is empty else return false.
 Pop()- operation used for removing a data item from the stack.
 isFull()- returns true if the stack is full else return false.