Scribd
Upload
5 views4 pages

Fish Tank Separation and Course Dependency Analysis

The document discusses a problem involving the separation of fish into two tanks based on fighting behavior, represented as a bipartite graph. It also includes a function for building an index of documents and addresses the challenge of analyzing course dependencies at the University of Zimbabwe, determining valid course order and identifying circular dependencies using graph algorithms. Key algorithms mentioned include BFS, DFS, and Kahn's Algorithm for topological sorting.

Uploaded by

broom094
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views4 pages

Fish Tank Separation and Course Dependency Analysis

The document discusses a problem involving the separation of fish into two tanks based on fighting behavior, represented as a bipartite graph. It also includes a function for building an index of documents and addresses the challenge of analyzing course dependencies at the University of Zimbabwe, determining valid course order and identifying circular dependencies using graph algorithms. Key algorithms mentioned include BFS, DFS, and Kahn's Algorithm for topological sorting.

Uploaded by

broom094
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

MODULE: HSE111\HCE111\HHE111

LECTURER: MR. S. ZVAKAFA

GROUP MEMBERS

TADIWANASHE D NYAPADI HHE R2420120

ASHLY M CHAMBE HCE R2420043

CHANTELLE NJANJI HSE R2420126

QUESTION 1
STEP 1: We are representing the problem as an undirected graph G = VE

Vertices/ nodes: Each represent a fish

Edges: each edge between 2 vertices means that fish a and b will fight if
placed in the same tank.

We have six fish A, B, C, D, E, F

A B

C D E

Tank 1: {A, D}

Tank 2: {B, C, E, F}

Step 2: Determining if fish can be separated without fighting.

The goal is to determine if we can split the fish into 2 groups(tanks) such that
no 2 connected fish are in the same tank. This is the same as checking
whether the graph is bipartite.

It is a graph whose vertices can be divided into 2 disjoint sets such that no 2
vertices within the same set are adjacent. We can assign one set of fish to
tank 1 and other set to tank 2 ensuring no fighting occurs.

We can use BFS or DFS to color the graph. Storing from any vertices, assign
it color 1 and its adjacent color 2 and do this for all vertices. If vertices need
to be colored with both colors then the graph is not bipartite, otherwise the
graph is bipartite and we can successfully separate the fish into 2 tanks.

QUESTION 2

def build_index(documents):

index = {}

for section, text in [Link]():

words = [Link]()

for word in words:

if word not in index:

index[word] = set()

index[word].add(section)

return index

QUESTION 3

PROBLEM: Faculty Course Dependency Analysis

At the University of Zimbabwe, faculties of multiple courses, some of which


depend on others (i.e a student must complete a prerequisite course before
taking an advanced course). The challenge is to determine:

 If a valid order exists for taking all courses


 Whether there are circular dependencies (e.g a course indirectly
requires itself)

Nodes (Vertices) : Represent courses

Edges (Directed) : An edges from Course A B meaning A must be


completed before B.

If a cycle exists in the graph the course structure is invalid.

Math101 Math102
Physics 101 Physics102

Engineering101

Math101 is a prerequisite for Math102 and Physic101. Physics 101 must be


taken before Physics 102 and Engineering101.

Algorithm we sued was Kahn’s Algorithm (BFS) or DFS based Topological


algorithm. If a graph contains a cycle, no valid course order exists.

Math101 musts be taken first.

Math102 must be taken after Math101.

Physics101 to follow after Math101.

Physics102 follows after both Math101 and Physics101.

Engineering follows after Physics101

You might also like