Description

Instructions

1. This note book contains instructions for COMP9318-Lab2.

2. You are required to complete your implementation in a file submission.py provided along with this notebook.

3. You are not allowed to print out unnecessary stuff. We will not consider any output printed out on the screen. All results should be returned in appropriate data structures return by corresponding functions.

4. You need to submit the code for lab2 via following link: https://kg.cse.unsw.edu.au/submit/

5. For each question, we have provided you with detailed instructions along with question headings. In case of any problem, you can post your query @ Piazza.

6. If you choose to skip a question, leave the corresponding function body as it is (i.e., keep the pass line), otherwise it may affect your mark for other questions.

7. You are allowed to add other functions and/or import additional modules (you may have to in this lab), but you are not allowed to define global variables. Only functions are allowed in submission.py.

8. You should not import unnecessary modules/libraries, failing to import such modules at test time will lead to errors.

9. We will provide immediate feedback on your submission. You can access your scores using the online submission portal on the same day.

10. For Final Evaluation we will be using a different dataset, so your final scores may vary.

11. You are allowed to submit as many times as you want before the deadline, but ONLY the latest version will be kept and marked.

12. Submission deadline for this assignment is 23:59:59 on 21st March, 2019. We will not accept any late submissions.

Question 1: Optimal binning algorithm using dynamic programming (100 points)

In [1]:

# These are the only modules that you can use in lab2
import pandas as pd
import numpy as np

In this lab, you need to implement the optimal binning algorithm using the dynamic programming algorithm we discussed in the lecture. You are only allowed to use space.

Input

The input contains data (in a list) and the number of bins (an integer).

Output

You are required to output the binning result and the matrix computed by the algorithm.

The matrix entries record optimal binning cost for a suffix of the input array using a certain number of bins. You should assign -1 to all the invalid solutions.

In [2]:

x = [3, 1, 18, 11, 13, 17]
num_bins = 4

In [3]:

def v_opt_dp(x, b):# do not change the heading of the function
    pass # **replace** this line with your code

In [4]:

## You can test your implementation using the following code...

# Output:
#
# Bins = [[3, 1], [18], [11, 13], [17]]
# Matrix =
# [-1, -1, -1, 18.666666666666664, 8.0, 0]
# [-1, -1, 18.666666666666664, 2.0, 0, -1]
# [-1, 18.666666666666664, 2.0, 0, -1, -1]
# [4.0, 2.0, 0, -1, -1, -1]

import submission as submission
matrix, bins = submission.v_opt_dp(x, num_bins)
print("Bins = {}".format(bins))
print("Matrix =")
for row in matrix:
    print(row)
Bins = [[3, 1], [18], [11, 13], [17]]
Matrix =
[-1, -1, -1, 18.666666666666664, 8.0, 0]
[-1, -1, 18.666666666666664, 2.0, 0, -1]
[-1, 18.666666666666664, 2.0, 0, -1, -1]
[4.0, 2.0, 0, -1, -1, -1]

In [ ]:

In [ ]: