INSTITUTE OF ACCOUNTANCY ARUSHA

DEPARTMENT OF COMPUTER SCIENCE AND MATHEMATICS

INDIVIDUAL ASSIGNMENT GROUP 8

MODULE: DATA STRUCTURE AND ALGORITHMS

MODULE CODE: CYU 08104

FACILITATOR: ALMASI (Mr KABEYA)

SEMESTER: ONE

PROGRAMME NAME: BACHELOR IN CYBER SECURITY 3

ACADEMIC YEAR: 2024/2025

S/NO STUDENT’S NAME STUDENT’S REGISTRATION NUMBER

01 WALTER S MKINGILIMA BCSe-01-0059-2022

02 HONEST RUTAYEGA BCSe-01-0184-2022

03 KELVIN MWAIJEGA BCSe-01-0071-2022

04 KILASA EMMANUEL BCSe-01-0002-2022

05 BARAKA K RWECHUNGURA BCSe-01-0153-2022

06 ALLY HABIBU BCSe-01-0195-2022

07 ANTONY VEDASTUS BCSe-01-0034-2022

08 DAUDI KANONI BCSe-01-0215-2022

09 FADHILI KILEO BCSe-01-0183-2022

10 LAU NSYENGULA BCSe-01-0168-2022

11 ESTHER KACHINGWE BCSe-01-0087-2022

12 JASTINI C NGOGO BCSe-01-0066-2022

13 ANTONIA J LIMO BCSe-01-0236-2022

14 IKRAM IBRAHIM BCSe-01-0179-2022

15 ELIA MAHENGE BCSe-01-0076-2022

1
ANSWER TO QUESTION ONE

a. required to define graph, explain its components (vertices and edges) and difference between
directed and undirected graph:

i. Graph

Is a non linear data structure consisting of set of vertices and edges. The graph is denoted by G (V, E).

Example of graph

ii. Components of graph:

(a) Vertices

Are fundamental units of a graph representing objects such as people, cities, or devices.

(b) Edge
is a line between vertices. Represent relationships, links, or pathways.

.ii. Difference between directed and undirected graph

Terms Directed graphs Undirected graph
By definition Is a graph consisting edges that posses Graph where edges has no direction
direction goes away or toward vertex
Direction Edges connect vertex in one direction only Edges connect vertex bidirectional.
Degree of There are two types in-degree indicating Is the total number of edges connected to
vertex incoming edges and out-degree indicating vertices
outgoing edges from vertex

2
Diagram
examples

b. required to describe graph traversal algorithms (depth-first search and breadth-first search)
and how they operate within graph:
Graph Traversals
Are methods for visiting all vertices in a graph? The following are two basic graph traversal algorithms
and how they operate within graph:
i. Depth-first search algorithm (DFS)
Is the traversal algorithm that visits all vertices of a graph in decreasing order of a graph. It uses stack
data structure to keep track of all visited nodes. Algorithm starts in an arbitrary node (root node) and
explore as far as possible along each branch before backtracking.
How DFS operate within graph.
An algorithm start at root node of the tree, goes as far it can down a given path then backtrack until it find
an unexplored path and then explore it. The algorithm did this until whole graph explored.
Consider a graph below illustrating DFS algorithm

From the above graph:

The root node is node “A” we traverse in depth via node “B” followed by node “C”. Once we reach the
node we move up one level to node “B” and traverse through all other connected node in this case is node
“D” and “E”. Once we have covered all connected nodes we move again one level up to node “A” and
traverse to all other connected nodes in this case node “C”, as we traverse through deeper nodes we
traverse through nodes “F” and “G” covering all connected nodes.

3
ii. Breadth-first search algorithm (BFS)
Is a traversal algorithm that visits all vertices of a graph present at one level of depth of a graph before
moving to the next level of depth? BFS search a node that is closer to the source by using queue data
structure.
How BFS operate within graph.
BFS start by searching node, followed by its adjacent nodes then all nodes can be reached by a pass from
start node containing two edges, three edges and so on.

Consider a graph below illustrating BFS

From the graph above

Root node ‘A” we traverse in width through node “B” followed by node “C”. Once we have traversed
through all nodes in the firsrt depth level we move to the second depth level, starting with node “C” and
moving via node “D” “E” “F” and “G”

ANSWER TO QUESTION TWO

a. required to analyze time complexity of DFS and BFS in terms of number of vertices(V) and
edges(E) in the graph.
Time complexity
Is a measure of the amount of time an algorithm takes to complete as a function of the size of its input? It
helps evaluate and compare the efficiency of algorithms, especially as input sizes grow.
The time complexity of both DFS and BFS are O(V+E) where V is the number of vertex and E is the
number of edges in the graph. This is because every vertex(V) and every edge E is explored once.

4
b. required to discuss how the structure And density of the graph can impact the efficiency of
these search algorithm.
The efficiency of graph traversal algorithms, such as Depth-First Search (DFS) and Breadth-First Search
(BFS), is influenced significantly by the structure and density of the graph. The following are how these
factors affect the efficiency of these algorithms:
i. Graph Structure

(a) Directed and Undirected Graphs:

In a directed graph, each edge has a specific direction. Traversal algorithms must consider the direction,
meaning fewer edges are explored during traversal compared to an undirected graph.
In an undirected graph, edges are bidirectional, which means each edge connects two vertices
symmetrically. Traversal algorithms effectively process each edge twice (once from each vertex's
perspective).
(b) Connected vs. Disconnected Graphs:
In a connected graph, a traversal starting at any vertex can reach all other vertices. In a disconnected
graph, traversal algorithms might need to restart from multiple components to visit all vertices.
(c) Cyclic vs. Acyclic Graphs:
In cyclic graphs, cycles can cause redundant visits unless properly handled with a visited set, potentially
increasing the overhead. Acyclic graphs (like trees) are simpler for traversal since each edge is unique in
terms of connectivity.
ii. Graph density
Graph density describes the ratio of edges to vertices in a graph.

Effect on Algorithm Efficiency:

In dense graph where the number of edges is higher both BFS and DFS increases time complexity due to
higher number of edges that need to be explored this result longer traversal time hence slower efficient,
but in sparse graph where the number of edges are fewer the algorithm is more efficient.

ANSWER TO QUESTION THREE

a. required to explain how graph can model complex relationships within networked systems
such as connections between computers, servers and ip addresses:
Graphs are indispensable for modeling the structure and interactions within networked systems. They
allow administrators and researchers to analyze connectivity, optimize performance, and ensure reliability
in diverse domains, from local area networks to global-scale distributed systems. Algorithms like BFS,
DFS, and Dijkstra’s allow for efficient navigation and optimization of resources within the network:

5
Components of a Graph in Networked Systems
(a) Vertices (Nodes)
Represent entities in the system, such as Computers or devices, Servers, Switches or routers.
(b) Edges (Links)
Represent connections or interactions between nodes, such as Physical cables or wireless connections,
Data transfer paths and Relationships in protocols example https.
(c) Weights (Optional)
Numerical values assigned to edges, representing, Latency or bandwidth, Packet loss rates and Cost of
data transfer.
(d) Directed or Undirected Edges
Directed Graph Models systems with one-way interactions, like routing protocols or client-server
requests. Undirected Graph Models bidirectional interactions, like peer-to-peer connections.

Example: Modeling a Simple Network

From above Network:

Devices (Vertices): A, B, C, D, E and F
Connections (edges)
A ↔ B (5 ms latency), B ↔ C (10 ms latency), A ↔ D (20 ms latency) and B↔ E (5 ms latency)
Shortest Path Analysis:
To find the quickest path from A to E using Dijkstra's algorithm.
Paths: A → B ↔ C → E (20 ms) or A → B → E (10ms). Therefore the Optimal Path is A → B → E.

6
b. required to describe how graph algorithms can be used to detect unusual patterns , intrusion
or to identify path of potential malware spread in network.
Graph algorithms are invaluable for detecting unusual patterns, identifying intrusions, and analyzing the
potential spread of malware in networked systems as follows:
(a) Detecting Unusual Patterns
Graph algorithms can identify anomalies that deviate from typical network behavior. These anomalies
often indicate potential security threats. By using Clustering and Community Detection Algorithms.
Identify groups of nodes (example users, devices) with frequent interactions. Unusual nodes that do not
belong to any cluster or appear in multiple clusters may indicate compromised devices or unauthorized
access.
(b) Intrusion Detection
Graph-based intrusion detection systems (IDS) use algorithms to analyze the network for unauthorized
access or activities. By using Algorithms such as Dijkstra’s algorithm, Bellman-Ford and BFS.

(c) Identifying the Path of Potential Malware Spread

Graph algorithms are particularly useful in analyzing how malware propagates across a network and
predicting its potential impact. By using Breadth-First Search (BFS) Simulate the spread of malware from
an infected node.BFS explores all neighboring nodes level by level, identifying devices at risk in the
shortest number of hops.

ANSWER TO QUESTION FOUR.

a. required to discuss limitations of graph based-based approaches especially in defense
networks with high connectivity
Limitations of Graph-Based Approaches in High-Connectivity Defense Networks
In defense networks, where a large number of nodes (example servers, routers and workstations) are
densely connected, the limitations of graph-based methods become more pronounced. Below are the
limitations:
(a) Scalability
As network size increases, graph complexity can lead to exponential growth in cost, time and space
requirement for analysis, making real-time processing challenging.
(b) limited representation
Graph only represents relationship between objects but not their traits, it require full supply of
information to understand the data.

7
(c) lack of standardization
There are many different types of graph and each has its own strength and weekness hence make difficult
on selection the best.
(d) difficult in interpretations.
As size of graph increase managing and interpretations become challenging leading difficult in analysis
and comprehension.
(e) Complexity to design and implement
Designing a graph handling various algorithms require careful considerations and can result bugs and
errors hence poses maintenance challenges.
(f) Data Privacy and Confidentiality Concerns
Sensitive data needs to be protected, Sharing detailed graphs with too many entities or processing them
without sufficient security measures can reveal sensitive operational structures, potentially aiding
attackers.
b. required to suggest alternatives graph structures (eg. adjacency list, adjacency matrices and
optimization techniques eg dijikstra algorithm for shortest path detection that could enhance
search efficiency in cyber security applications requiring rapid analysis of complex networks:
Suggested Alternative Graph Structures and optimization techniques are:
(a) Graph neural Networks(GNNs).
These are deep learning models that operate directly on graph structure allowing for extraction of
complex patterns and relationships. These help in cyber security to enhance malware detection,
vulnerability assessment and enhance threat detection.

(b) Spanning Trees

Is a sub graph that includes all the vertices of the original graph with the minimum number of edge.
Connects all nodes in a network in an efficient manner. In cyber security help to Reduces complexity by
focusing on the essential connections and Helps in simplifying path finding algorithms, such as for
detecting malicious communication paths or unauthorized access across a network.

(c) Dijkstra’s Algorithm (Shortest Path)

Dijkstra’s algorithm finds the shortest path between a source node and all other nodes in a weighted
graph. In cyber security help for Path Optimization essential in identifying the shortest (or least costly)
path for intrusion attempts, lateral movement, or data ex-filtration across a network.
(d) Bellman-Ford Algorithm
Bellman-Ford is an algorithm for finding the shortest paths from a source node to all other nodes in a
graph, and it can handle negative edge weights. It's slower than Dijkstra but more flexible for dynamic
graphs where edge weights may change. In cyber security is helpful since used in Dynamic Environments

8
where the state of the network is constantly changing (e.g., new vulnerabilities or attacks may alter the
"weight" of edges.

(e) Graph Partitioning

Graph partitioning involves dividing a large graph into smaller, more manageable sub-graphs (or
partitions) for parallel or distributed processing. This is particularly useful for distributed systems or
large-scale network environments. This in cyber security help to Reduces the problem size by working on
smaller sub graphs, enabling faster local analysis.

(f) Heuristic Search Algorithms

Heuristic search algorithms, such as Greedy Search, Best-First Search, are used to explore graphs more
intelligently by estimating the cost or distance of reaching a goal node, leading to faster searches
compared to uninformed methods like BFS and DFS. This is important in cyber security since Heuristics
can focus the search on the most likely paths, reducing the number of nodes and edges explored and
Allows faster identification of attack paths or critical nodes in a network.
(g) Hybrid Techniques
Combining the strengths of different approaches can further optimize search efficiency in complex
networks. Example combining Graph + Machine Learning, Use machine learning to classify or predict
anomalous behavior based on graph features.

9
 REFERENCES
Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C.(2009).introduction to algorithms(3rd ed).the MIT
press.
Goodrich, M.T., Tamassia, R., & Goldwasser, M.H (2014). Data structure and algorithm in java (6th ed)
pg 594. John wiley & Sons.
https://www.totorialspoint.com
https://www.thedshandbook.com

10