MCD4710 – Introduction to Algorithms and Programming

Assignment 1 (8%) - Trimester 1 2021

Due: Thursday, April 1 2021, 11:55pm (week 6)

Objectives

The objectives of this assignment are:

● To demonstrate the ability to implement algorithms using basic data structures and operations on them.

● To gain experience in designing an algorithm for a given problem description and implementing that algorithm in Python.

● To explain the computational problems and the challenges they pose as well as your chosen strategies and programming techniques to address them.

Submission Procedure

You are going to create a single Python module file familytree.py based on the provided template. Submit this file by the due date of midnight April 1.

For your submission:

1. Save the current version of your familytree.py into a zip file called yourStudentID_yourFirstName_yourLastName.zip.

2. Submit this zip file to Moodle.

3. Your assignment will not be accepted unless it is a readable zip file containing a file called familytree.py.

Late Submission

Late submission will have 5% deduction of the total assignment marks per day (including weekends). Assignments submitted 7 days after the due date will not be accepted.

Important Note:

● Please ensure that you have read and understood the university’s policies on plagiarism and collusion available at http://www.monash.edu.au/students/policies/academic-integrity.html. You will be required to agree to these policies when you submit your assignment.

● A common mistake students make is to use Google to find solutions to the questions. Once you have seen a solution it is often difficult to come up with your own version. The best way to avoid making this mistake is to avoid using Google. You have been given all the tools you need in workshops. If you find you are stuck, feel free to ask for assistance on the Ed discussion forums, ensuring that you do not post your code.

● Your code will be checked against other students’ work and code available online by advanced plagiarism detection systems. Make sure your work is your won. Do not take the risk.

● Your program will be checked against a number of test cases. Do not forget to include comments in your code explaining your algorithm. If your implementation has bugs, you may still get some marks based on how close your algorithm is to the correct algorithm. This is made difficult if code is poorly documented.

● Where it would simplify the problem you may not use built-in Python functions or libraries (e.g. using list.sort() or sorated()). Remember that this is an assignment focusing on algorithms and programming.

Assignment code interview

Each student will be interviewed during a lab session regarding their submission to gauge your personal under-standing of your Assignment code. The purpose of this is to ensure that you have completed the code yourself and that you understand the code submitted. Your assignment mark will be scaled according to the responses provided.

Interview Rubric

0	The student cannot answer even the simplest of questions.   There is no sign of preparation.   They probably have not seen the code before.
0.25	There is some evidence the student has seen the code.   The answer to a least one question contained some correct points.   However, it is clear they cannot engage in a knowledgeable discussion about the code.
0.5	The student seems underprepared.   Answers are long-winded and only partly correct.   They seem to be trying to work out the code as they read it.   They seem to be trying to remember something they were told but now can’t remember.   However, they clearly know something about the code.   With prompting, they fail to improve on a partial or incorrect answer.
0.75	The student seems reasonably well prepared.   Questions are answered correctly for the most part but the speed and/or confidence they are   answered with is not 100%.   With prompting, they can add a partially correct answer or correct an incorrect answer.
1	The student is fully prepared.   All questions were answered quickly and confidently.   It is absolutely clear that the student has performed all of the coding themselves.

Marks and Module Documentation

This assignment will be marked both by the correctness of your module and your analysis of it, which has to be provided as part of your function documentation. Each of the assessed functions of your module must contain a docstring that contains, in this order:

1. A one line short summary of what the function is computing

2. A formal input/output specification of the function

3. Some usage examples of the function (in doctest style); feel free to augment and alter the examples for the assessed functions that are already provided in the template if you feel they are incomplete or otherwise insufficient (provide some explanations in this case)

4. A paragraph explaining the specific problems that need to be solved by this function, and your overall approach in tackling these problems

5. A paragraph explaining the specific choices of programming techniques that you have used

    Beyond the assessed functions, you are highly encouraged to add additional functions to the module that you use as part of your implementation of the assessed functions. In fact, such a decomposition is essential for a readable implementation of the assessed function, which in turn forms the basis of a coherent and readable analysis in the documentation. All these additional functions also must contain a minimal docstring with the items 1-3 from the list above. Additionally, you can also use their docstrings to provide additional information, which you can refer to from the analysis paragraphs of the assessed functions.

    Mark breakdowns for each of the assessed functions can be found in parentheses after each task section below. Marks are subtracted for inappropriate or incomplete discussion of the function in their docstring. Again, readable code with appropriate decomposition and variable names is the basis of a suitable analysis in the documentation.

Marking Criteria

This assignment contributes to 8% of your final mark.

● Task A - Person Index, Father, Mother: 3 marks

● Task B - Grandchildren: 3 marks

● Task C - Aunts and Uncles: 4 marks

● Decomposition: 1 mark

● Variable names and Code documentation: 2 marks

Total: 13 marks

Overview

In this assignment we create a Python module to implement some basic family tree software, where users can look up various relationships that exist in the database, as well as merging two family tree databases that may contain overlapping information. We represent each entry in a family tree database as a list of three strings [name, father, mother], where name is a person’s name, father is the name of their father, and mother is the name of their mother. Where a particular relationship is unknown, the value None is used.

    For example, consider the following family tree:

Figure 1: The Duck Family Tree

    The relationships shown in this tree are represented using the following database in Python (note that this database is just for the purposes of illustration, and your module must work for other family tree databases as well):

>>> duck_tree = [[’Donald Duck’,’Quackmore Duck’,’Hortense McDuck’],

...                     [’Della Duck’, ’Quackmore Duck’, ’Hortense McDuck’],

...                     [’Hortense McDuck’, ’Fergus McDuck’, ’Downy ODrake’],

...                     [’Scrooge McDuck’, ’Fergus McDuck’, ’Downy ODrake’],

...                     [’Huey Duck’, None, ’Della Duck’],

...                     [’Dewey Duck’, None, ’Della Duck’],

...                     [’Louie Duck’, None, ’Della Duck’]]

    Again, this is just one limited example of a family tree database. You should write a module that can be used for searching arbitrary family trees represented in this way. For instance, the database might look like this:

>>> modern_family = [[’Phil Dunphy’, ’Frank Dunphy’, ’Grace Dunphy’],

...                     [’Claire Pritchett’, ’Jay Pritchett’, ’Dede Pritchett’],

...                     [’Haley Dunphy’, ’Phil Dunphy’, Claire Pritchett’],

...                     [’Alex Dunphy’, ’Phil Dunphy’, Claire Pritchett’],

...                     [’Luke Dunphy’, ’Phil Dunphy’, Claire Pritchett’],

...                     [’Mitchell Pritchett’, ’Jay Pritchett’, ’Dede Pritchett’],

...                     [’Joe Pritchett’, ’Jay Pritchett’, ’Gloria Ramirez’],

...                     [’Manny Delgado’, ’Javier Delgado’, ’Gloria Ramirez’]]

    As a run-through example, this assignment will use the duck tree database. But it is important to remember that your functions should work on any family tree that is represented in the manner described. Consider creating your own examples to test your functions on.

Simple Relationship Lookups

This assignment involves writing functions that retrieve information about simple familial relationships in a family tree database. Each function in this section takes as input a person’s name and a family tree database, and returns some information about that person which is stored in the database.

Task A: Person Index, Father, Mother (3 Marks)

For this task, your module has to contain at least the three mandatory functions person index, father, and mother. The details are as follows:

    Implement a function person index(person, family) with the following specification.

Input: A string containing a person’s name, person, and a family tree database family as specified above.

Output: The index value of that person’s entry in the family tree database, or None if they do not have an entry in the tree.

    For example, for the above family tree database, person index behaves as follows:

>>> person_index(’Dewey Duck’, duck_tree)

5

>>> person_index(’Fergus McDuck’, duck_tree)

None

    (Note that although ’Fergus McDuck’ is listed as a father in the database duck tree, he does not have an entry in this database, as his name never appears in the first column of that database. So the output for the second example should be None.)

    Implement a function father(person, family) with the following specification.

Input: A string containing a person’s name, person, and a family tree database family as specified above.

Output: A string containing the name of that person’s father, as defined in the database family, or None if the information is not in the database (including if the person themselves are not in the database).

    Building on the same example, father would behave as follows:

>>> father(’Della Duck’, duck_tree)

’Quackmore Duck’

>>> father(’Huey Duck’, duck_tree)

None

>>> father(’Daffy Duck’, duck_tree)

None

    Implement a function mother(person, family) with the following specification.

Input: A string containing a person’s name, person, and a family tree database family as specified above.

Output: A string containing the name of that person’s mother, as defined in the database family, or None if the information is not in the database (including if the person themselves are not in the database).

    For example, mother should behave as follows:

>>> mother(’Hortense McDuck’, duck_tree)

’Downy ODrake’

>>> mother(’Fergus McDuck’, duck_tree)

None

>>> mother(’Daffy Duck’, duck_tree)

None

Task B: Grandchildren (3 Marks)

Implement a function grandchildren(person, family) with the following specification.

Input: A string containing a person’s name, person, and a family tree database family as specified above.

Output: A list containing the names of all of person’s grandchildren that are stored in the database. If there is no information about any of person’s grandchildren in the database (including if the person themselves are not in the database), the function should return an empty list.

    For example, grandchildren should behave as follows:

>>> sorted(grandchildren(’Downy ODrake’, duck_tree))

[ ’Della Duck’, ’Donald Duck’]

>>> grandchildren(’Donald Duck’, duck_tree)

[]

    Hint: Consider how you may define grandchildren in terms of person’s children.

Task C: Aunts and Uncles (4 Marks)

Implement a function aunts and uncles(person, family) with the following specification.

Input: A string containing a person’s name, person, and a family tree database family as specified above.

Output: A list containing only the names of the aunts and uncles of person that are stored in the database, or an empty list if no such information exists in the database (including if the person themselves are not in the database). Aunts and uncles are defined as siblings of either of the person’s parents. Equivalently they can be thought of as children of any of person’s grandparents.

    For example, aunts and uncles should behave as follows:

>>> duck_tree = [[’Donald Duck’,’Quackmore Duck’,’Hortense McDuck’],

...                     [’Della Duck’, ’Quackmore Duck’, ’Hortense McDuck’],

...                     [’Hortense McDuck’, ’Fergus McDuck’, ’Downy ODrake’],

...                     [’Scrooge McDuck’, ’Fergus McDuck’, ’Downy ODrake’],

...                     [’Fergus McDuck’, ’Dingus McDuck’, ’Molly Mallard’],

...                     [’Huey Duck’, None, ’Della Duck’],

...                     [’Dewey Duck’, None, ’Della Duck’],

...                     [’Louie Duck’, None, ’Della Duck’]]

>>> sorted(aunts_and_uncles(’Huey Duck’, duck_tree))

[’Donald Duck’]

>>> sorted(aunts_and_uncles(’Quackmore Duck’, duck_tree))

[]

>>>sorted(aunts_and_uncles(’Della Duck’, duck_tree))

[’Scrooge McDuck’]

>>>sorted(aunts_and_uncles(’Donald Duck’, duck_tree))

[’Scrooge McDuck’]