answers

CITS2200 Lab 4: Genealogy

Name: Ajay Bisnath

Student Number: 24794543

Question 1 (1 mark)

Write a simple description of how you are going to represent the problem as a data structure.
Your description should justify how the representation is going to help you solve the problem within the target complexities.

The genealogy can be represented as a tree using two dictionaries, a parent map and a children map. The parent map stores each individual’s parent, making it easy to travel from any node to the root (Originator). The children map stores a list of children for each individual, enabling easy travel from parent to its descendants.

This representation is well suited for solving this problem as succession orders require tree traversal. Primogeniture can be implemented as a depth-first traversal using the children map and seniority can be implemented as a breadth-first traversal. Both traversals visit each node exactly one, which leads to a time complexity of O(n).

Additionally, the parent map allows for efficient computation of ancestor paths, which is needed to determine how closely related any two individuals are. By storing both upward and downward relationships, the structure supports all required operations efficiently within the target time bounds.

Question 2 (1 mark)

Write a simple description of the algorithm you have designed for get_cousin_dist().
Your description should justify the correctness of your algorithm, and make an argument as to its time complexity.

The algorthm finds the cousin relationship between two nodes (individuals) by first tracing all ancestors of the first node and storing their distance from the node in a dictionary. Then, it traverses upwards from the second node until it finds the first shared ancestor, which is the lowest common ancestor (LCA). Using the stored distances from both nodes to the LCA, the cousin degree is calculated as min(d1, d2) - 1, and the removal is the absolute difference |d1 - d2|.

This approach is correct because any relationship between two nodes in a tree is defined by their shared ancestor, and the LCA minimises total distance between them.

The time complexity is O(h) where h is the height of the tree, since each node is traced upwards at most once and dictionary lookups are O(1) (inconsequential).

Question 3 (5 marks)

Implement your design by filling out the method stubs in the Genealogy class found in genealogy.py.
You are not allowed to import any modules.
Your implementation must pass the tests given in test_genealogy.py, which can be invoked by running python -m unittest.

See genealogy.py.

Question 4 (1 mark)

Give an argument for the correctness and complexity of your get_primogeniture_order() function.

The primogeniture order is generated using a depth-first search (DFS) starting from the root node (Originator). The algorithm visits each node before recursively visiting its children from oldest to youngest, ensuring that entire subtrees are explored before moving to siblings.

This correctly implements primogeniture because succession follows a pre-order traversal of the tree, where descendants of older children are fully explored before younger siblings are considered.

The time complexity is O(n), where n is the number of nodes, because each node is visited exactly once during the traversal.

Question 5 (1 mark)

Give an argument for the correctness and complexity of your get_seniority_order() function.

The seniority order is generated using a breadth-first search (BFS) starting from the root node (Originator). A queue is used to process nodes level by level, ensuring that all nodes at a given depth are visited before moving to the next generation. Within each level, children are processed from oldest to youngest based on insertion order.

This is correct because seniority is defined by generation order first (distance from root), and sibling order second, which BFS naturally enforces.

The time complexity is O(n), since each node is enqueued and dequeued exactly once.

Question 6 (1 mark)

Give a brief explanation of the function and purpose of any data structures you implemented.

The main data structures I used in my code were dictionaries (maps) and a tree structure. The dictionary stores key-value pairs, here it is used to map each node’s (individual’s) name to its correspoding tree node object, allowing efficient O(1) access to any node. The tree structure stores each individual node with a parent pointer and a list of children, enabling efficient upward and downward traversal.

I used a queue with a circular array to support breadth-first search traversal in O(1) amortised time per operation. The combination of these structures allows efficient construction of the genealogy and supports both depth first and breadth-first traversals.

Additionally, the parent references in the tree allow efficient implementation of a Lowest Common Anscestor (LCA) algorithm, which traces nodes upward to find their shared ancestor, in order to find their cousin relationship.