This is the second homework assignment. Your goal in this assignment is to write a function that performs a calculation and returns a value.

Practical information#

The assignment is due on Monday of semester week 4, the 15th of August, at 9:00am (Canberra time). To submit your solution, upload a single python file via wattle. Here is the assignment submission link.

In addition to submitting your solution, you must attend your lab in the same week (semester week 4). In the lab, your tutor will ask you some questions about your solution, and give you feedback if there is anything you need to improve. This discussion is also part of the assessment.

If you fail to show up for the discussion with the tutor, you will receive zero marks for this assignment. If you do not submit a solution, or your solution is not correct, you may still get partial marks for the discussion with the tutor.

The homework is individual. You must write your own solution, and you are expected to be able to explain every aspect of it. Also remember that you are not allowed to share your solution (code) with other students; this includes posting it (or parts of it) to the discussion forum, or to any other on-line forum.

If you have followed the lectures and worked through the exercises in lab 2, the assignment should not take more than an hour or two to complete.

The problem#

Calculating the number of ways to select k distinct elements from a set of n is one of the most famous problems in combinatorics. This number is often called “n choose k”, or the binomial coefficients. We will call it combinations(n, k), because you will implement it in a function called combinations.

There are several ways to compute this number, but the one that most students find easiest is the formula

$$\frac{n!}{k! (n-k)!}$$

where \(n!\) is the factorial function of \(n\). The factorial of 0 is defined to be 1, so that the combinations formula still works when n or k are zero.

Your task is to write a function combinations(n, k) that computes and returns the n choose k, or combinations(n, k), number.

The function must take two arguments (that is, have two parameters), and it must return an integer value (a value of type int).

We provide you with a skeleton code file: combinations.py. Download this file and write in it your implementation of the function.

The skeleton file already has in it several functions: One is an implementation of the factorial function, which you can use in your combinations function. (Note that there is also a function called factorial in the math module, which you can also use.) The others are testing functions that you can (and should!) use to test if your function is working correctly.

Testing#

The skeleton file has two testing functions:

  • test_combinations() This function runs a number of tests of your function, and produces an error message if any of the tests fail. If all tests are ok, it will print the message “all tests passed”.

  • print_pascals_triangle(n) This function prints the first n rows of Pascal’s triangle, which is made up of combinations numbers. n must be a positive integer. For example, print_pascals_triangle(5) should print

    1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

    This function will only print the numbers in Pascal’s triangle (as computed by your combinations function), it will not check that they are correct. You have to do that by comparing it with the expected output.

Marking#

What to submit

You should edit the skeleton file combinations.py that you downloaded, then upload only this file with your solution using the assignment submission link on Wattle.

The file that you submit must meet the following requirements:

  • It must be syntatically correct python code.
  • Like the file you downloaded, it must contain only function definitions; comments, including docstrings (if they are used appropriately) are of course ok to include. Anything that is not a function definition will be ignored when we check your submission.
  • You should not modify the testing functions.
  • Python 3.8 or later provides a function math.comb in the math module. You are not allowed to use this function.

As mentioned above, you must also attend the following lab (in week 4) and answer your tutor’s questions about your solution. This discussion is part of the assessment. You should be prepared to answer or demonstrate to the following questions:

  • Can you download the file that you submitted from wattle?
  • Can you run that file in the python interpreter (using an IDE of your choice) on the CSIT lab computer?
  • If the file has syntax errors, can you use the error messages from the interpreter or IDE to identify where the syntax errors are?
  • Does your submitted file meet the requirements stated above? Does it contain anything that is not a function definition? If so, can you point it out?
  • Does your function pass all the tests run by the unmodified test_combinations() function?
  • Does your function correctly compute and return the number of combinations for any valid arguments (non-negative integers n and k, with 0 <= k <= n).
  • Does your function always return a value of the correct type?
  • Can you think of any other test cases that should be used to test your function, in addition to or instead of those in test_combinations()?
  • How did you choose to calculate the number? Which formula or method did you use, and why?
  • What is the difference between the print function and the return statement?

In marking this assignment we will consider the following:

  • Does your submitted file satisfy the requirements specified above?
  • Does your implementation of the combinations function compute the correct value for all argument values?
  • Your ability to use the tools (e.g., the IDE or python interpreter), your understanding of python’s error messages, and your understanding of the solution, as demonstrated in your discussion with the tutor.

The assignment is worth 2% of your final mark.

bars search times arrow-up