Data Structures & Algorithm

UNIT NO. & TITLE: Unit No.19 Data Structures & Algorithms


QUALIFICATION: BTEC Level 5 HND Computing


YEAR: 2019-2020


PREPARED BY: Siddhesh Raje


REPORT


SUBMITTED ON:




1

, INDEX
Sr Topic Page
No. No.
1. LO1: Examine abstract data types, concrete data
structures and algorithms.
P1: Create a design specification for data structures 3
explaining the valid operations that can be carried out on
structures.
P2: Determine the operations of memory stack and how it 7
used to implement function calls in a computer.
M1: Illustrate, with an example, a concrete data structure 12
for a First in First out (FIFO) queue.
M2: Compare the performance of two sorting algorithms. 16
2. LO2: Specify abstract data types and algorithms in a
formal notation.
P3: Using an imperative definition, specify the abstract 22
data type for a software stack.
M3: Examine the advantages of encapsulation and 24
information hiding when using an ADT.
3. LO3: Implement complex ADT data structure and
algorithms.
P4: Implement a complex ADT and algorithm in an 28
executable programming language to solve a well-defined
problem.
P5: Implement error handling and report test results. 33
M4: Demonstrate how the implementation of 36
ADT/algorithm solves a well-defined problem.
4. LO4: Assess the effectiveness of data structure and
algorithms.
P6: Discuss how asymptotic analysis can be used to assess 40
the effectiveness of an algorithm.
P7: Determine two ways in which the efficiency of an 43
algorithm can be measured, illustrating your answer with
an example.
M5: Interpret what a trade-off is when specifying an ADT 49
using an example to support.
5. Reference 52




2

,LO1: Examine abstract data types, concrete data structures and algorithms.


P1: Create a design specification for data structures explaining the valid
operations that can be carried out on structures.


Operation that can be carried out on the structured are as follows:


What is Array: An array is a collection of items stored at contiguous
memory locations. We can say these arrays has adjacent memory locations to
store values. Since array provides a convenient structed for representing data.
Accessing each value of array, we need to access with their index number, in
array the index number start with 0 till the nth number.
Syntax for declaring array are:
data_type array_name [array_size];


What is Stack: Stack is an abstract data types with a predefined capacity.
Stack allows adding and removing elements in a particular order. Every time an
element is added, it goes on the top of the stack and the only elements that can
be removed is the element that is at the top of the stack we can say just like a
pile of object.




Stack is used for three primary operation:
push(): Pushing an element on the stack which is shown in the above image

3

, pop(): Removing an element from the stack which is shown in the above
image.
peek(): This method is used to retrieve the first element of the stack or we can
say the element which is present at the top of the stack. The element retrieved
does not get deleted or removed form the stack


Syntax for declaring array are:
Stackname.push() { \\syntax for push\\
}
Stackname.pop () { \\syntax for pop\\
}
What are Queues: Queue is an abstract data structure we can say somewhat
similar to stacks. In this the first element is inserted from one end called the
REAR and the removal of existing element takes place from the other end qw
called FRONT
This makes queue as FIFO (First in First Out) data structure, which means that
element inserted first will be removed first.




Enqueue(): Operation for adding an element into queue which is shown in the
above image
Dequeue(): Operation for removing an element from queue which is shown in
the above image


Syntax for declaring array are:


4