NAME REG NUMBER
Anesu B Chinake R2211008H
QUESTION 1
The operations that can be performed on data structures depend on the type of data structure
being used. Here are some common data structures and their associated operations:
1. There are common operations that can be performed on structures. These operations
include traversing which involves printing all elements one by one. For example on arrays
traverse operation is used to print all elements on an array one by one. Arrays are collections
of elements of the same data type, stored in contiguous memory locations. There is also
insertion of element at a given index. Elements in an array can also searched using the given
index. Operations performed on arrays can also be performed on linked lists. Sorting is also
another operation that is performed on data structures. Sorting involves arranging the data in
ascending or descending order. This can be performed on arrays and linked lists
2. Another operation that can be performed in data structures includes pushing elements and
popping elements. These operations are performed on stacks where data is removed and
added in a last-in, first out order. There is popping up of elements off the stack and peeking
at the top element of the stack. Pushing is when elements are pushed onto the stack.
3. Queues are collections of elements that are added at the back and removed from the front
in a first-in, first-out (FIFO) order. Common operations on queues include adding elements
to the back of the queue, removing elements from the front of the queue, and peeking at the
front element of the queue.
4. Trees are hierarchical structures made up of nodes, where each node has a parent node
and child nodes. Common operations on trees include adding or removing nodes, traversing
the tree. Traversing the tree involves visiting all the nodes of a tree and prints their values.
Traversing is done is three forms which is in-order traversal, post-order traversal and pre-
order traversal. A search operation is used when searching a particular node. Nodes can be
removed or added to the tree. These operations can be also performed on graphs.
5. Hash tables are collections of key-value pairs, where the key is used to look up the
corresponding value. Common operations on hash tables include adding or removing key-
value pairs, looking up values by key, and iterating over the key-value pairs. These are just a
few examples of the many data structures and operations that can be performed on them.
The specific operations that can be performed on a data structure will depend on the
particular type of data structure and the programming language being used.
2. Approaches for developing an algorithm
There are several approaches that can be used in the development of an algorithm which
includes brute force, divide and conquer, dynamic programming and greedy algorithm.
Divide and conquer strategy involves breaking down a problem into smaller, more
manageable steps that a computer can execute. You need to understand the problem first
then divide the problem into smaller sub problems that can be solved independently and
then combine it to solve the actual problem. Brute force involves checking every possible
solution the problem. Dynamic programming involves breaking a problem into smaller sub
problems and storing the solution to those sub problems in tables to avoid redundant
calculations, while greedy algorithm make the locally optimal choice at each step in the
hope of finding a global optimum. Therefore design an algorithm after choosing the right
strategy, implement it in a programming language. Then test the algorithm to make sure it is
correct and running properly. These are just some general steps to developing an algorithm.
The specific approach you take will depend on the problem you are trying to solve and your
level of expertise in algorithm design.
3. Why do we use stacks in algorithms
Stacks are commonly used in algorithms because they provide a simple and efficient way to
manage data that needs to be processed in a last-in, first-out (LIFO) order. Here are some
reasons why stacks are useful in algorithms:
1. Function calls: Many programming languages use a call stack to manage function calls.
When a function is called, its arguments and local variables are pushed onto the stack. When
the function returns, the stack is popped, and control is returned to the calling function.
2. Expression evaluation: Stacks can be used to evaluate expressions in a postfix notation. In
postfix notation, operators are placed after their operands, and the expression is evaluated
from left to right. Stacks can be used to push operands onto the stack and pop them off when
operators are encountered.
3. Backtracking: Some algorithms, such as depth-first search, use backtracking to explore all
possible paths in a search tree. Stacks can be used to keep track of the nodes that have been
visited and the path that has been taken, allowing the algorithm to backtrack when necessary.
4. Parsing: Stacks can be used to parse and evaluate programming language constructs such
as parentheses, brackets, and braces. Each time an opening bracket is encountered, it is
pushed onto the stack. When a closing bracket is encountered, the stack is popped, and the
brackets are matched.
5. Undo/Redo: Stacks can be used to implement undo/redo functionality in software
applications. Each time a user performs an action, it is pushed onto the stack. When the user
chooses to undo an action, the stack is popped, and the previous action is undone. Stacks are
a simple and powerful data structure that can be used in many different contexts to manage
data in a LIFO order.
4. Outline the concept at tree traversal
Tree traversal is the process of visiting and processing every node in a tree data structure.
There are two main approaches to tree traversal: depth-first traversal and breadth-first
traversal. In depth-first traversal, we start at the root of the tree and visit as far down the tree
as possible before backtracking and visiting the next branch. There are three common
strategies for depth-first traversal which are pre-order traversal, in-order traversal and post
order traversal. In-order traversal, we start by visiting the right side then the root and finally
the left side. Pre-order traversal we start by visiting the root then the right side and finally the
left. Post order traversal, we start by the left then right then finally the root. Breadth-first
traversal is when we visit all the nodes at a given level of the tree before moving on to the
next level. Breadth-first traversal is typically implemented using a queue data structure to
keep track of the nodes to be visited. Tree traversal is a fundamental operation in tree-based
algorithms, such as searching, inserting, and deleting nodes in a tree. The choice of traversal
strategy will depend on the specific problem being solved and the properties of the tree being
traversed.
QUESTION 2
1. Inserting keys into a binary search tree:
- The first key "A" is inserted as the root of the tree.
- The second key "S" is inserted to the right of "A".
- The third key "D" is inserted to the left of "S".
- The fourth key "F" is inserted to the right of "D".
- The fifth key "G" is inserted to the right of "F".
- The sixth key "H" is inserted to the right of "G".
- The seventh key "J" is inserted to the right of "H".
- The eighth key "K" is inserted to the right of "J".
- The ninth key "L" is inserted to the right of "K".
The resulting binary search tree would look like this:
A
s
D
F
G
H
J
K
L
2. Inserting keys into a 2-3 tree:
- The first key "A" is inserted as a 2-node.
- The second key "S" is inserted to the right of "A", creating a 3-node.
- The third key "D" is inserted to the left of "S", creating a 2-node.
- The fourth key "F" is inserted to the right of "D", creating a 3-node.
- The fifth key "G" is inserted to the right of "F", creating a 2-node.
- The sixth key "H" is inserted to the right of "G", creating a 3-node.
- The seventh key "J" is inserted to the right of "H", creating a 2-node.
- The eighth key "K" is inserted to the right of "J", creating a 3-node.
- The ninth key "L" is inserted to the right of "K", creating a 2-node.
The resulting 2-3 tree would look like this:
```
[S]
[A] [F, J]
[D] [H, K]
[G, L]
2. The output of this program will be:
The area = 16
Is it a square? true
The area = 700
Is it a square? false
NAME REG NUMBER
Anesu B Chinake R2211008H
QUESTION 1
The operations that can be performed on data structures depend on the type of data structure
being used. Here are some common data structures and their associated operations:
1. There are common operations that can be performed on structures. These operations
include traversing which involves printing all elements one by one. For example on arrays
traverse operation is used to print all elements on an array one by one. Arrays are collections
of elements of the same data type, stored in contiguous memory locations. There is also
insertion of element at a given index. Elements in an array can also searched using the given
index. Operations performed on arrays can also be performed on linked lists. Sorting is also
another operation that is performed on data structures. Sorting involves arranging the data in
ascending or descending order. This can be performed on arrays and linked lists
2. Another operation that can be performed in data structures includes pushing elements and
popping elements. These operations are performed on stacks where data is removed and
added in a last-in, first out order. There is popping up of elements off the stack and peeking
at the top element of the stack. Pushing is when elements are pushed onto the stack.
3. Queues are collections of elements that are added at the back and removed from the front
in a first-in, first-out (FIFO) order. Common operations on queues include adding elements
to the back of the queue, removing elements from the front of the queue, and peeking at the
front element of the queue.
4. Trees are hierarchical structures made up of nodes, where each node has a parent node
and child nodes. Common operations on trees include adding or removing nodes, traversing
the tree. Traversing the tree involves visiting all the nodes of a tree and prints their values.
Traversing is done is three forms which is in-order traversal, post-order traversal and pre-
order traversal. A search operation is used when searching a particular node. Nodes can be
removed or added to the tree. These operations can be also performed on graphs.
5. Hash tables are collections of key-value pairs, where the key is used to look up the
corresponding value. Common operations on hash tables include adding or removing key-
value pairs, looking up values by key, and iterating over the key-value pairs. These are just a
few examples of the many data structures and operations that can be performed on them.
The specific operations that can be performed on a data structure will depend on the
particular type of data structure and the programming language being used.
2. Approaches for developing an algorithm
There are several approaches that can be used in the development of an algorithm which
This is because the program creates two My Rectangle objects, m1 and m2, with different
lengths and widths. Then, it calculates the area of each rectangle and checks if it is a square
using the is Square() method. In this case, m1 is a square with an area of 16 while m2 is not a
square and has an area of 700.
