27/01/26

Chapter 5: abstract data structure

lesson: introduction to ADT

 Identify a situation that requires the use of recursive thinking

 Identify recursive thinking in a specified problem solution
 Trace a recursive algorithm to express a solution to a problem
 Describe the characteristics of a 2 dimensional array
 Describe the characteristics and application of a stack
 Construct an algorithm using the access method of a stack

Definition: abstract data types is a concept in a computer science that characterise a data type by its
functionality. This approach ignores the specifics of how data is organised internally and how the
operations are executed. It focuses instead on the perspective of what can be done with the data.

Properties and purpose of abstract data structures

 they are important in software development offering a blend in encapsulation

 offering a blend of encapsulation, abstraction and molecularity that aid in the design
implementation and maintenance

properties of ADT

1. operation and behaviour: ADT include a collection of operations that are allowed to be perform
on the data. For example, a queue ADT will allow operations such as enqueue, dequeue, isempty
and peek.
2. Abstraction: ADT focus on what operations are performed not how these operations are
implemented. This abstraction allows the user to use the data without understanding the
underlining complexities e.g you can use a queue without needing to worry about how it is
implemented
3. Encapsulation: ADT encapsulate the data, ensuring that it can only be accessed or manipulated
through its defined operations. This prevents external interfere and misuse of underlining data.
In the queue, you will the available operation but no other operation will be available

Purpose

 It is used for code reusability and maintenance

 It is used for improvement of code portability
 Used to felicitate data manipulation
  It is used for enhancement of design quality
 Used for simplification of complex system

Linked list

A linked list is a sequence of ADT consisting of a sequence of elements each contained in a note. Each
note contains a pointer to the next note in the sequence, forming a chain-like structure.

Advantages
 Unlike arrays links are dynamic in size meaning they can grow during the run time
 Efficient insertion and deletion, adding and removing elements is efficient because this
operation doesn’t require elements

02/02/2026

Key operations of link list

1. Insertion: In this link list operation, we create new notes and adjust pointers
2. Deletion: in this operation we can adjust pointers by removing notes
3. Traversal: in this operation we follow pointer from the head to the end
4. Search: in this operation we compare values while following pointers from head to the end

Application of a linked list

1 Dynamic memory allocation: unlike a static array a linked list does not require a contiguous block of
memory to be allocated. Each note is located dynamically from the heap memory as needed and link via
pointers

Aspect Array (static) Link list (dynamic)

Memory allocation Single fixed size block of Nodes allocate separately at run
compiled time time
Memory efficiency Can lead to memory wastage if Use memory proportionally to
too large or too low current data, no unuse
allocated space
Insertion or deletion Inefficient (o(n)) at item must Efficient (o(n)) at a known
be shifted to maintain order position as it only requires
changing pointers

2 Implementation of stacks and queues: linked link provide and underlining mechanism to implement
ADTs like stacks and queues. The pointers felicitate the specific access patterns which are LIFO (last-in
first-out) and FIFO ( first-in first-out)

a) Stack implementation (LIFO): the head pointer of the list server as the top of the stack. PUSH,
here a new node is created and set its next pointer to the current head. It updates the head to
 point to the new node. The time complexity is 0(1). POP, for the pop it stores the head node
data and then updates the head to the head it then disposes the old node
b) Queue implementation (FIFO): here two pointers are maintained, the front ( for dequeue) and
rear ( for enqueue). In the enqueue we create a new node, if the queue is empty, we set both
front and rear to it. In dequeue store date from the front node. Update front to front. If front
become null

3 undo functionalities in software: the undo feature can be implemented using a stack, which is
often build upon a linked list. Each user action is pushed onto to the stack

Trees

They are different types of trees. We have the most common one which is binary tree

1 binary search tree: a binary search is a node based binary tree data structure where each node has
unique key and at most two children with the following properties

- Left child property: the key in any node in the left subtree is less than the key in its parent and
any other nodes in the right subtree
- Right child property: the key in any node in the right subtree is greater than the key in its parent

Structure of a binary search tree

its structure is composed of the following properties

a) node structure : each node in a BST contain some key components which are key (the value or
data that is used to order the node within the tree) , left child (a pointer to the left child node which
contain the key less than the nodes key), right child (a pointer to the left child node which contain
the key greater than the nodes key), parent (some implementation also include the pointer to the
parent node for easier traversal and manipulation)

3 10

6
1 14

4 7 13
 b) root structure: the top-most node in a BST from which every node is accessible

c) leaf nodes: they are no nodes with no children and this marks the boundaries of the tree

properties of BST

A BST is optimised for binary search operation, insertion and deletion, and searching operations

1) Ordered structure: in a BST, for any given node (N) all elements in the N’s left subtree are less
than the N, and all elements’ N’s right subtree are greater than N. this ordering hold for every
node within the tree, ensuring the entire structure remain sorted
2) Dynamic size: BST are dynamically sized, allowing the addition (insertion) and removal (deletion)
of nodes. This adaptability makes the BST males the capable of adjusting to changes in the data
set size over time.

Construct a BST in integers. Enter a set of numeric in the BST and then sketch the resulting tree

Data set = 40,20,60,10,30,50,70

40

20 60

10 30 50 70
 03/02/25

Lesson: advanced data structure

Binary search tree

Enter the list of names in this data set into a BST and sketch the resulting tree

Data set: Emma, Noah, Olivia, Liam, Ava, Ethan, Sophia

Emma

Ava noah

liam olivia

ethan Sofia

Construct and apply sets as an ADT

A set is a collection of distinct elements or objects with no particular order and no duplicate entries.
In CSC , sets are used to efficiently store distinct elements and perform operations such as union,
intersection, difference and subset checks

In programming sets are often implemented to quickly test membership or add and remove
elements ensuring that each element appears only once within the collection. For example, a set
could hold the email address of all subscribers to the new letters, ensuring no duplicate address are
stored. In Python a set is commonly referred to a set while in java it is HashSet
 Example of creating a set in python

My_set = set ([1,2,3,4,5])

print (my_set)

My_set2 = {1,2,3,4,5}
print (my_set2)

empty_set = set( )

print (type (empty_set)

Explain the core principle of ADTs

hash table are fundamental data structure used in computing to store key-values pairs. They offer
efficient retrieval, insertion and deletion operation, typically with an average time complexity 0(1)

The underlining mechanism of hash table

The efficiency and performance of a hash table depend on three main aspects: the hashing function, the
collision resolution strategies, and load factor

- Hashing function: it is the backbone of the hash table. It takes a key as input and calculates an integer
index that determine where the key value pair should be stored in the table. A good hashing function
has a few essential characteristics

1. Efficiency: it computes the hash value quicky to speed up the access time. The choice of the
hashing function can significantly impact the performance of a hash table. It should minimize
collision and evenly distribute keys to utilise the table storage space effectively.
2. Uniform distribution: it spreads keys evenly across the tables, minimizing the likelihood of
collision
3. Deterministic: the same key always results in the same index

- Collison resolution strategies: a collision occurs when two keys hash to the same index. Since each slot
in the hash table can hold only one entry, the table must have a strategy for resolving this collision.
Those strategies include;

1. Separate chaining: this method stores multiple elements at the same index using a more
complex data structure such as link list or BST. Each cell of the hash table becomes a bucket that
holds multiple entries, which a searched sequentially to find a specific key
2. Open address: HW
- Load factor: the load factor of a hash table is a measure that indicates how full the table is. It is
represented by the character ⋋ It is defined as the ratio of the number of stored elements to the
number of slots available

Formula includes ;

number of enteries
⋋=
total number of buckets

Assignment
enter each data set into a BST and then sketch the resulting tree

Data set 1: 35,26,28,92,41,43,99,10

Data set 2: carol, farah, ben, claire, anaya, brian

Data set 3: managua, apia, Bishkek, muscat, , riga, accra, Paramaribo,

Data set 4: 1A91, 152E, 21CF, 10F8, 23BC

Data set 4 contains numerical values written in numerical form. What might you need to place these
hexadecimal numbers into a BST?

BST1
35

26 92

10 28 41 99

43
BST2

carol

ben farah

anaya brain claire

BST3 managua

apia muscat

riga
accra bishkek paramaribo

BST4
1A91

152E 21CF
 Convert hexadecimal
10F8 values to their decimal equivalents or 23BC
 Use a comparison function that correctly compares hexadecimal values numerically (base-16), not as
strings

05/02/25

Thinking recursively

Objectives

 Define recursion
 Identify a situation that recquires recursive thinking and identify recursive thinking in a specific
problem
 Trace a recursive algorithm to express a solution

Definition;

Recursion is when a method calls itself until some terminating condition is meet. This is accomplished
without any specific repetition construct such as a While or For loop. It follows one of the basic problem
solving techniques which is to break down the problem into smaller sub tasks. Any algorithm that may
be represented in a recursive can also be presented in an iterative manner.

Example 1: simple recursion (adding integers)

The following program use recursion to create the method addIntUpTo (n) for n>0 that will add all
numbers from and including n down to 1. For example, if addIntUpTo(4) is called the result will be
4+3+2+1 = 10

Pseudo code

Method addIntUpTo (n)

If (n==1) then

Return 1

Else

Return n + addIntUpTo (n-1)

Endif

End method
Method foo(n)

If (n<=1) then

Return

Else

Return foo (n-1) + foo (n-2)

Endif

End method

Output foo (5)

This example shows recursive function to calculate a value. In this specific case the algorithm for foo (n)

Is actually the formula for the Fibonacci sequence

Rules of the function (foo(n))

 Base case: if n is 1 or less, the answer is just 1

 The recursive step: if n greater than 1 the answer is foo(n-1) + foo(n-2)

foo(5-1) + foo(5-2) = 4 + 3

foo(5) = foo(4) + foo(3)

= foo(4-1) + foo(4-2) + foo(3-1) + foo(3-2)

=( 3 + 2 )+(2 + 1 )

= 5 + 3

= 8