Data Structures and Algorithms Project: Semester 1

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

Data Structures and Algorithms

Table of Contents
Introduction................................................................................................................................3
LO1............................................................................................................................................4
P1. Create a design specification for data structures explaining the valid operations that can
be carried out on the structures...............................................................................................4
P2. Determine the operations of a memory stack and how it is used to implement function
calls in a computer..................................................................................................................5
M1. Illustrate, with an example, a concrete data structure for a First In First Out (FIFO)
queue.......................................................................................................................................8
M2. Compare the performance of two sorting algorithms...................................................11
LO2..........................................................................................................................................19
P3. Using an imperative definition, specify the abstract data type for a software stack......19
M3. Examine the advantages of encapsulation and information hiding when using an ADT.
..............................................................................................................................................21
LO3..........................................................................................................................................22
P4. Implement a complex ADT and algorithm in an executable programming language to
solve a well-defined problem...............................................................................................22
P5. Implement error handling and report test results...........................................................27
M4. Demonstrate how the implementation of an ADT/algorithm solves a well-defined
problem.................................................................................................................................31
LO4..........................................................................................................................................32
P6. Discuss how asymptotic analysis can be used to assess the effectiveness of an
algorithm...............................................................................................................................32
P7. Determine two ways in which the efficiency of an algorithm can be measured,
illustrating your answer with an example.............................................................................35
M5. Interpret what a tradeoff is when specifying an ADT using an example to support your
answer...................................................................................................................................36
Conclusion................................................................................................................................37

Reference..................................................................................................................................37
List of tables
Figure 1: stack............................................................................................................................8
Figure 2: queue.........................................................................................................................11
Figure 3: Program menu...........................................................................................................28
Figure 4: Job insertion..............................................................................................................28
Figure 5: Removing of job.......................................................................................................29
Figure 6: Front job available....................................................................................................29
Figure 7: Rear job available.....................................................................................................30
Figure 8: Total number of jobs.................................................................................................30
Figure 9: Queue deletion..........................................................................................................31
Figure 10: omega notation.......................................................................................................34
Figure 11: theta notation..........................................................................................................34
Figure 12: big-oh notation........................................................................................................35

Introduction
Data structures are used mostly for storing the collected data in a predefined structure. It
allows the easy accessing of data and is easy to maintain. They are the basis for ADT
(abstract data type) which represents the data types’ logical form. Different types of data
structures exist including list, stack, queue, tree, and graphs, which are broadly classified into
two structures known as linear structures and non-linear structures. It is used in many areas of
computers like compiler design, operating system, graphics, artificial intelligence and many
more. Data structures play a significant role in enhancing software's or program's
performance. They make the searching of data easy, make multiple requests and by
decreasing the complexity, speed of the processor can become fast.

LO1
P1. Create a design specification for data structures explaining the valid
operations that can be carried out on the structures.
Data structures are used to store the data in an organized manner so that any operation
performed on these data structures can give efficient and exact results. Data structures are of
different types which are broadly divided into linear and non-linear data structures (Lafore,
2017). Linear data structures further divided into static and dynamic, static data structures
includes array while dynamic data structures include linked list, stack, and queue. In the
category of non-linear data structures, tree, and graph fall. Linear data structures are the
structures in which data is arranged in sequential order and in non-linear data structures, data
is not arranged in a linear way (Shavit and Taubenfeld, 2016). Data structures are used to
reduce the complexity of the data storage so that the processor speed can be reduced, makes
the searching of data less complex, and allows making multiple requests. There are a number
of operations that can be performed on data structures, these operations include:
 Insertion:
This operation is used to insert an element in the list.
 Deletion:
This operation is used to delete an element from the list.
 Merging:
This is used to combine two data structures of the same type.
 Traversing:
This is used to traverse the entire structure containing elements to perform some
operations like sorting and searching (Liu, et. al., 2017).
 Sorting:
This is the operation used to sort the elements in any specific order.
 Searching:
This is used to search an element in the given data structure.
Advantages of data structure:
 Efficiency
 Abstraction

 Reusability (Morisson and Thorne, 2016)

P2. Determine the operations of a memory stack and how it is used to implement
function calls in a computer.
The stack is a type of linear data structure in which data is stored in a sequential manner. It
uses the concept on Last in First out (LIFO). It refers to the Abstract data type (ADT). The
most common operations are Pop and Push.
 Pop():
It is used to remove an element from the stack (Sevenich, et. al., 2015).
 Push():
It is used to insert an element into the stack.
Other than push and pop operations, some more operations are used to make use of stack
efficiently (Emmi and Enea, 2016). These operations are:
 isFull():
It is used to check the fullness of the stack before inserting an element into it.

 isEmpty():
It is used to check the emptiness of the stack before returning an element from the stack
(Gill, et. al., 2019).
 peek():
It used to return the element which is on the top of stack without its actual removal.
Applications:
 Used in recursions.
 Used in tree traversals
 Used in browsing
 Used in parsing (Kazim, 2017).

Figure 1: stack

M1. Illustrate, with an example, a concrete data structure for a First In First Out
(FIFO) queue.
The queue is a type of linear data structure in which operations are performed form both
ends. One end is used for the insertion of data called the front end and the other end is used to
remove the data from the queue and is called the rear end (Rejas, et. al., 2015). It follows the
concept of FIFO (First In First Out). Basic operations that could be performed on the queue
are:
 enqueue():
It is used to insert an element in the queue. The insertion takes from the rear end always.
 dequeue():
It is used to delete an element from the queue. The deletion or removal of an element from
the queue always takes from the front end (Marszalek, 2017).
 isFull():

This operation is used to check the fullness of the queue before making insertion (Numes,
et. al., 2018).
 isEmpty():
This operation is used to check the emptiness of the queue (Faujdar and Ghrera, 2015).
 peek():
It is used to return the element from the element without its actual removal (Marszalek,
2018).
Application:
 Used in the operating system
 Used in the media players to maintain the playlist.
 Used as buffers in applications.
 Used commonly used in the data transfers that are asynchronous (Abdulla, 2016).

Figure 2: queue