Name: Abdullahi Muhammad

Student ID:10207036

Course Name: CMP 202

Assignment question: 2
 Introduction

Graphs and hashing are fundamental concepts in computer science, each serving distinct
purposes.

A graph is a data structure composed of vertices (or nodes) and edges that connect pairs of
vertices. Graphs can be directed, where edges have a direction, or undirected, where edges do
not. They model relationships and structures in various applications, such as social networks,
transportation systems, and biological networks. Graph algorithms, like Depth-First Search
(DFS) and Breadth-First Search (BFS), are essential for navigating and analysing these
structures.

Hashing is a technique used to efficiently map data of arbitrary size to fixed-size values, called
hash codes, using a hash function. This enables fast data retrieval, insertion, and deletion in
structures like hash tables. Hash functions are designed to distribute data uniformly across the
hash table to minimize collisions, where different inputs produce the same hash code. Hashing is
widely used in applications like databases, caching, and cryptography for its speed and efficiency
in data management.
 Part I

Overview of single and double linked list

A linked list is a data structure consisting of nodes, each containing data and a reference (or link)
to the next node in the sequence. In a single linked list, each node has a single link pointing to
the next node. This structure allows for efficient sequential access and insertion but limits
traversal to one direction (forward).

A double linked list extends this concept by including an additional reference in each node that
points to the previous node. This bidirectional linking enables traversal in both directions
(forward and backward), which provides more flexibility for certain operations, such as reverse
traversal or deletion of a node. However, it requires more memory to store the additional link and
can be slightly more complex to implement.

Insert operation in double linked list

In a double linked list, the insert operation involves adjusting the pointers of the neighbouring
nodes and the new node. For instance, to insert a new node between two nodes, you update the
previous node's next pointer and the next node's previous pointer to link to the new node, and
vice versa.

Traversal operation in single linked list

Traversal in a single linked list involves visiting each node starting from the head and following
the next pointers sequentially until reaching the end of the list (where the next pointer is null).
During traversal, operations such as accessing or processing data at each node can be performed.
This linear progression ensures that each node is visited once, making traversal straightforward
but limited to forward direction only.
 Part II

Overview of BFS graph

Breadth-First Search (BFS) is a graph traversal algorithm that explores vertices level by level,
starting from a given source node. It uses a queue to track the next vertex to visit, ensuring that
all neighbours of the current vertex are explored before moving to the next level.

[Link] Network In a social network graph, where nodes represent users and edges represent
friendships, BFS can find the shortest path between two users. Starting from a user, BFS
explores all direct friends first, then friends of friends, and so on. This helps determine the
degrees of separation between two users.

2. Web Crawling: Web crawlers use BFS to index pages. Starting from a seed URL, BFS
explores all hyperlinks on the current page before moving to links on the next level. This ensures
that pages are indexed in a systematic manner, layer by layer, providing a comprehensive and
structured way to map the web.

3. Shortest Path in Unweighted Graph

In an unweighted graph, BFS can find the shortest path between two nodes. For instance, in a
maze represented as a grid, BFS starts at the entry point and explores all possible paths level by
level until the exit is reached. Each level corresponds to a step, ensuring the shortest path is
found efficiently.

Overview of DFS graph

Depth-First Search (DFS) is a graph traversal algorithm that explores as far down a branch as
possible before backtracking. It's used to search through graphs or trees efficiently. Here are
three examples:

[Link] Solving: In a maze represented as a graph, DFS starts from the entry point and explores
as far as possible along each path until reaching a dead end or the exit. By backtracking when
necessary, it systematically explores all possible paths until finding a solution.

2. Topological Sorting: DFS can be used to perform topological sorting in directed acyclic
graphs (DAGs). By traversing the graph and recording the order in which vertices are visited,
DFS can determine a valid linear ordering of the vertices, which represents a sequence of tasks
with precedence constraints.

3. Cycle Detection: DFS can detect cycles in a graph. By maintaining a list of visited nodes and
checking for back edges during traversal, DFS can identify if there are any cycles present in the
graph.
 Part III

Hash concept

Hashing is a technique to map data of arbitrary size to fixed-size values using a hash function.
For instance, in a hash table, a hash function converts keys into array indices. If a phone book is
stored in a hash table, the hash function maps names to indices for fast retrieval.

Various techniques of Hashing

Various hashing techniques include:

1. Division Method: Hash function computes the remainder when key is divided by table size.

2. Multiplication Method: Utilizes fractional part of key multiplied by table size.

3. Universal Hashing: Randomly selects hash function from a family of hash functions.

4. Double Hashing: Uses secondary hash function to resolve collisions.

5. Perfect Hashing: Guarantees no collisions in a hash table.

6. Cryptographic Hashing: Irreversibly transforms input data into fixed-size output, commonly
used for secure data storage.

These techniques are employed based on specific requirements such as collision resolution,
performance, and security.

Collision handle while addressing

Collisions in hashing occur when two different keys map to the same hash value. Collision
resolution techniques handle this issue. Common methods include chaining and open addressing.
In chaining, each hash table entry holds a linked list of elements with the same hash value. Open
addressing, on the other hand, involves finding an alternative location (probe sequence) within
the hash table when a collision occurs. Techniques like linear probing, quadratic probing, and
double hashing are used to find these alternative locations. These approaches ensure efficient
storage and retrieval of data even in the presence of collisions.
 Conclusion

In conclusion, understanding graph traversal algorithms like Breadth-First Search (BFS) and
Depth-First Search (DFS) is crucial for navigating complex networks efficiently. Additionally,
hashing techniques play a vital role in data storage and retrieval, ensuring fast access to
information by mapping keys to fixed-size values. Various hashing methods, including division,
multiplication, and open addressing, address collision issues efficiently. Both graphs and hashing
are foundational concepts in computer science, enabling the development of efficient algorithms
for a wide range of applications, from social networks to database management systems.
References
[Link], T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). *Introduction to
Algorithms*. MIT Press.

2. Sedgewick, R., & Wayne, K. (2011). *Algorithms*. Addison-Wesley.

3. Skiena, S. S. (2008). *The Algorithm Design Manual*. Springer.