ASSIGNMENT 1 BRIEF
Qualification BTEC Level 5 HND Diploma in Business
Unit number Unit 19: Data Structures and Algorithms
Assignment title Examine and specify ADT and DSA
Academic Year Summer 2020
Unit Tutor Vu Thanh Hien
Issue date Submission date
IV name and date
Submission Format:
Format: The submission is in the form of an individual written report and a presentation. This should
be written in a concise, formal business style using single spacing and font size 12. You are
required to make use of headings, paragraphs and subsections as appropriate, and all work
must be supported with research and referenced using the Harvard referencing system. Please
also provide a bibliography using the Harvard referencing system.
Submission Students are compulsory to submit the assignment in due date and in a way requested by the
Tutors. The form of submission will be a soft copy in PDF posted on corresponding course of
http://cms.greenwich.edu.vn/
Note: The Assignment must be your own work, and not copied by or from another student or from
books etc. If you use ideas, quotes or data (such as diagrams) from books, journals or other sources, you
must reference your sources, using the Harvard style. Make sure that you know how to reference properly,
and that understand the guidelines on plagiarism. If you do not, you definitely get fail
Assignment Brief and Guidance:
Scenario: You work as in-house software developer for Softnet Development Ltd, a software body-shop providing
network provisioning solutions. Your company is part of a collaborative service provisioning development project
and your company has won the contract to design and develop a middleware solution that will interface at the
front-end to multiple computer provisioning interfaces including SOAP, HTTP, JML and CLI, and the back-end
telecom provisioning network via CLI .
Your account manager has assigned you a special role that is to inform your team about designing and implementing
abstract data types. You have been asked to create a presentation for all collaborating partners on how ADTs can
be utilised to improve software design, development and testing. Further, you have been asked to write an
Page 1
introductory report for distribution to all partners on how to specify abstract data types and algorithms in a formal
notation.
Tasks
Part 1
You will need to prepare a presentation on how to create a design specification for data structures, explaining the
valid operations that can be carried out on the structures using the example of:
1. A stack ADT, a concrete data structure for a First In First out (FIFO) queue.
2. Two sorting algorithms.
3. Two network shortest path algorithms.
Part 2
You will need to provide a formal written report that includes the following:
1. Explanation on how to specify an abstract data type using the example of software stack.
2. Explanation of the advantages of encapsulation and information hiding when using an ADT.
3. Discussion of imperative ADTs with regard to object orientation.
Learning Outcomes and Assessment Criteria
Pass Merit Distinction
LO1 Examine abstract data types, concrete data structures and
algorithms
D1 Analyse the operation, using
P1 Create a design M1 Illustrate, with an example, a illustrations, of two network
specification for data structures concrete data structure for a First shortest path algorithms,
explaining the valid operations In First out (FIFO) queue. providing an example of each.
that can be carried out on the M2 Compare the performance of
structures. two sorting algorithms.
P2 Determine the operations
of a memory stack and how it
is used to implement function
calls in a computer.
LO2 Specify abstract data types and algorithms in a formal notation
P3 Using an imperative M3 Examine the advantages of D2 Discuss the view that
definition, specify the abstract encapsulation and information imperative ADTs are a basis for
data type for a software stack. hiding when using an ADT. object orientation and, with
Page 2
justification, state whether you
agree.
Table of Contents
P1 Create a design specification for data structures explaining the valid operations that can be carried out on the
structures. .................................................................................................................................................................. 4
Definition ................................................................................................................................................................... 4
Linked List — Data Structure .................................................................................................................................. 6
Implementation ..................................................................................................................................................... 6
P2 Determine the operations of a memory stack and how it is used to implement function calls in a computer. ..... 9
LIFO Principle of Stack ............................................................................................................................................ 9
Basic Operations of Stack ..................................................................................................................................... 10
Working of Stack Data Structure .......................................................................................................................... 10
Applications of Stack Data Structure .................................................................................................................... 11
1. Abstract Data Type ........................................................................................................................................... 12
Definition: ........................................................................................................................................................ 12
Imperative-style definitions ............................................................................................................................. 12
Abstract variable .............................................................................................................................................. 12
2. Software stack .................................................................................................................................................. 13
Definition ......................................................................................................................................................... 13
Examples of software stacks: ........................................................................................................................... 14
Benefits and challenges of software stacks ...................................................................................................... 14
References ............................................................................................................................................................... 15
Page 3
P1 Create a design specification for data structures explaining the valid operations that can be carried
out on the structures.
Definition
The Data Type is basically a type of data that can be used in different computer program. It signifies the type
like integer, float etc, the space like integer will take 4-bytes, character will take 1-byte of space etc.
The abstract datatype is special kind of datatype, whose behavior is defined by a set of values and set of
operations. The keyword “Abstract” is used as we can use these datatypes, we can perform different
operations. But how those operations are working that is totally hidden from the user. The ADT is made of
with primitive datatypes, but operation logics are hidden.
Some examples of ADT are Stack, Queue, List etc.
Let us see some operations of those mentioned ADT −
• Stack −
o isFull(), This is used to check whether stack is full or not
o isEmpry(), This is used to check whether stack is empty or not
o push(x), This is used to push x into the stack
o pop(), This is used to delete one element from top of the stack
o peek(), This is used to get the top most element of the stack
o size(), this function is used to get number of elements present into the stack
• Queue −
o isFull(), This is used to check whether queue is full or not
o isEmpry(), This is used to check whether queue is empty or not
o insert(x), This is used to add x into the queue at the rear end
o delete(), This is used to delete one element from the front end of the queue
o size(), this function is used to get number of elements present into the queue
• List −
o size(), this function is used to get number of elements present into the list
Page 4
o insert(x), this function is used to insert one element into the list
o remove(x), this function is used to remove given element from the list
o get(i), this function is used to get element at position i
o replace(x, y), this function is used to replace x with y value
Linked List is an Abstract Data Type (ADT) that holds a collection of Nodes, the nodes can be accessed in a
sequential way. Linked List doesn’t provide a random access to a Node.
Usually, those Nodes are connected to the next node and/or with the previous one, this gives the linked
effect. When the Nodes are connected with only the next pointer the list is called Singly Linked List and
when it’s connected by the next and previous the list is called Doubly Linked List.
Image for post
The Nodes stored in a Linked List can be anything from primitives types such as integers to more complex
types like instances of classes.
Page 5
Linked List — Data Structure
Implementation
A Linked List can be implemented in different ways, this is my implementation and it’s used to explain the
concepts. The ADT defines what a Linked List should be able to do and the Data Structure is the
implementation.
The implementation could use Nodes with a previous and next pointers, the LinkedList could have a head to
keep track of the first element and a tail to keep track of the last element in the list. There’s a lot of
improvement points to this implementation, the focus here is to understand the basics of a Linked List.
Page 6
Page 7
Complexity
Page 8
Improvements
Using a Doubly Linked List would be possible to have an O(1) to pop method because we would have a
previous pointer that would optimize the process of finding the second-last element to pop .
Following the same implementation pattern, a Doubly Linked List would have a complexity similar to:
P2 Determine the operations of a memory stack and how it is used to implement function calls in a
computer.
Definition
A stack is a useful data structure in programming. It is just like a pile of plates kept on top of each other.
Think about the things you can do with such a pile of plates
• Put a new plate on top
• Remove the top plate
If you want the plate at the bottom, you have to first remove all the plates on top. Such an arrangement is
called Last In First Out - the last item that was placed is the first item to go out.
LIFO Principle of Stack
In programming terms, putting an item on top of the stack is called "push" and removing an item is called
"pop".
Page 9
Stack Push and Pop Operations
In the above image, although item 2 was kept last, it was removed first - so it follows the Last In First
Out(LIFO) principle.
We can implement a stack in any programming language like C, C++, Java, Python or C#, but the
specification is pretty much the same.
Basic Operations of Stack
A stack is an object or more specifically an abstract data structure (ADT) that allows the following
operations:
• Push: Add an element to the top of a stack
• Pop: Remove an element from the top of a stack
• IsEmpty: Check if the stack is empty
• IsFull: Check if the stack is full
• Peek: Get the value of the top element without removing it
Working of Stack Data Structure
The operations work as follows:
1. A pointer called TOP is used to keep track of the top element in the stack.
2. When initializing the stack, we set its value to -1 so that we can check if the stack is empty by
comparing TOP == -1.
Page 10
3. On pushing an element, we increase the value of TOP and place the new element in the position pointed to
by TOP.
4. On popping an element, we return the element pointed to by TOP and reduce its value.
5. Before pushing, we check if the stack is already full
6. Before popping, we check if the stack is already empty
Working of Stack Data Structure
Applications of Stack Data Structure
Although stack is a simple data structure to implement, it is very powerful. The most common uses of a
stack are:
• To reverse a word - Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you
will get the letters in reverse order.
• In compilers - Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9) by
converting the expression to prefix or postfix form.
• In browsers - The back button in a browser saves all the URLs you have visited previously in a stack. Each
time you visit a new page, it is added on top of the stack. When you press the back button, the current URL
is removed from the stack and the previous URL is accessed.
Page 11
P3 Using an imperative definition, specify the abstract data type for a software stack
1. Abstract Data Type
Definition:
An abstract type of data is characterized as a mathematical model of the data objects that make up a
category of data, as well as the functions that work on them. They are not defined by traditional
conventions. A broad distinction can be made between the concept types "imperative" and "functional".
Imperative-style definitions
An abstract data structure is conceived in the theory of imperative programming languages as an object
that is mutable — meaning that it can be present in various states at different times. Some operations may
alter the state of the ADT; therefore, the order in which operations are performed is important, and if
executed at different times, the same operation on the same entities can have different effects — just like
a computer 's instructions, or the commands and procedures of an imperative language. To underline this
view, it is customary to say that rather than being analyzed, the operations are performed or implemented.
When explaining abstract algorithms the imperative style is also used
Abstract variable
Imperative-style definitions of ADT often depend on the concept of an abstract variable, which may be
regarded as the simplest non-trivial ADT. An abstract variable V is a mutable entity that admits two
operations:
store(V, x) where x is a value of unspecified nature;
fetch(V), that yields a value,
with the constraint that
fetch(V) always returns the value x used in the most recent store(V, x) operation on the same variable V.
Page 12
As in so many programming languages, the operation store(V, x) is often written V ← x (or some similar
notation), and fetch(V) is implied whenever a variable V is used in a context where a value is required.
Thus, for example, V ← V + 1 is commonly understood to be a shorthand for store(V,fetch(V) + 1).
In this definition, it is implicitly assumed that storing a value into a variable U has no effect on the state of a
distinct variable V. To make this assumption explicit, one could add the constraint that
if U and V are distinct variables, the sequence { store(U, x); store(V, y) } is equivalent to { store(V, y);
store(U, x) }.
More generally, ADT definitions often assume that any operation that changes the state of one ADT
instance has no effect on the state of any other instance (including other instances of the same ADT) —
unless the ADT axioms imply that the two instances are connected in that sense. For example, when
extending the definition of abstract variable to include abstract records, the operation that selects a field
from a record variable R must yield a variable V that is aliased to that part of R.
The definition of an abstract variable V may also restrict the stored values x to members of a specific set X,
called the range or type of V. As in programming languages, such restrictions may simplify the description
and analysis of algorithms, and improve their readability.
Note that this definition does not imply anything about the result of evaluating fetch(V) when V is un-
initialized, that is, before performing any store operation on V. An algorithm that does so is usually
considered invalid, because its effect is not defined. (However, there are some important algorithms whose
efficiency strongly depends on the assumption that such a fetch is legal, and returns some arbitrary value
in the variable's range.
2. Software stack
Definition
A software stack is a collection of independent components that work together to support the execution of
an application. The components, which may include an operating system, architectural layers, protocols,
run-time environments, databases and function calls, are stacked one on top of each other in a hierarchy.
Page 13
Typically, the lower level components in the hierarchy interact with hardware, while the higher level
components in the hierarchy perform specific tasks for the end user. Components communicate directly
with the application through a series of complex instructions that traverse the stack.
Examples of software stacks:
LAMP (Linux, Apache, MySQL, PHP) - a well-known software stack for web development. The lowest layer
of the stack’s hierarchy is the Linux operating system. The highest layer of the hierarchy is the scripting
language -- in this case, PHP. (Note: the “P” may also stand for the programming languages Python or Perl).
LAMP stacks are popular because the components are all open source and the stack can run on commodity
hardware. Unlike monolithic software stacks, which are often tightly coupled and often built for a
particular operating system, a LAMP stack is loosely coupled. This simply means that while the components
were not originally designed to work together, they have proven to be complementary and are often used
together. Today, LAMP components are now included in almost all Linux distributions.
MEAN (MongoDB, Express, Angular and Node) - a stack of development tools known for helping to
eliminate the language barriers often experienced in software development. In a MEAN stack, the
foundation is MongoDB, which is a NoSQL document datastore. The HTTP server is Express and Angular is
the framework for front-end JavaScript. The highest layer of the stack is Node, a platform for server-side
scripting.
Benefits and challenges of software stacks
When stack components communicate through open and standard protocols and application program
interfaces, the components become interchangeable with other components that use the same APIs. This
makes it possible for a virtual machine (VM) running LINUX to run on the Windows operating system and
change from a LAMP stack to a virtual WAMP stack. When a stack is loosely coupled, however, it can be
challenging to optimize performance. Each component needs to be individually analyzed and tuned, which
calls for very particular skill sets.
Page 14
References
1. Magnum, L., 2020. #Sidenotes — Linked List — Abstract Data Type And Data Structure. [online]
Medium. Available at: <https://medium.com/@lucasmagnum/sidenotes-linked-list-abstract-data-
type-and-data-structure-fd2f8276ab53> [Accessed 14 August 2020].
2. Programiz.com. 2020. Stack Data Structure. [online] Available at:
<https://www.programiz.com/dsa/stack> [Accessed 14 August 2020].
3. En.wikipedia.org. 2020. Abstract Data Type. [online] Available at:
<https://en.wikipedia.org/wiki/Abstract_data_type#Imperative-style_definition> [Accessed 2 September 2020].
4. SearchAppArchitecture. 2020. What Is Software Stack? - Definition From Whatis.Com. [online] Available at:
<https://searchapparchitecture.techtarget.com/definition/software-
stack#:~:text=A%20software%20stack%20is%20a,each%20other%20in%20a%20hierarchy.> [Accessed 2
September 2020].
Page 15
