<jupyter_start><jupyter_text>COMP9318 Lab2  Instructions1. This note book contains instructions for **COMP9318-Lab2**.* You are required to complete your implementation in a file `submission.py` provided along with this notebook.* 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.* You need to submit the code for **lab2** via following link: https://kg.cse.unsw.edu.au/submit/* 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.* 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.* 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`. * You should not import unnecessary modules/libraries, failing to import such modules at test time will lead to errors.* We will provide immediate feedback on your submission. You can access your scores using the online submission portal on the same day. * For **Final Evaluation** we will be using a different dataset, so your final scores may vary.  * You are allowed to submit as many times as you want before the deadline, but **ONLY the latest version will be kept and marked**.* 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)<jupyter_code># These are the only modules that you can use in lab2
import pandas as pd
import numpy as np<jupyter_output><empty_output><jupyter_text>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 $O(n^2)$ space.  InputThe input contains data (in a list) and the number of bins (an integer). OutputYou 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.<jupyter_code>x = [3, 1, 18, 11, 13, 17]
num_bins = 4
def sse(nums):
    if not len(nums):
        return 0
    avg = np.average(nums)
    result = sum([(x-avg)*(x-avg) for x in nums])
    return result

def v_opt_dp(x, b):# do not change the heading of the function
    dp_matrix = [[-1 for i in range(len(x))] for j in range(b)]
    dp_index = [[-1 for i in range(len(x))] for j in range(b)]
    
    for i in range(b):
        for j in range(len(x)):
            if (b-i-j) >= 2 or len(x)-j <= i:
                continue
            if not i:
                dp_matrix[i][j] = sse(x[j:])
            else:
                row = []
                for k in range(j, len(x)):
                    opt1 = sse(x[j:k+1])
                    opt2 = opt1+dp_matrix[i-1][k+1] if (k+1)<=len(x)-1 else opt1
                    row.append(opt2)
                min_val = min(row)
                dp_matrix[i][j] = min_val
                temp_index = j+1
                for val in row:
                    if val == min_val:
                        dp_index[i][j] = temp_index
                        break
                    temp_index += 1
    start = dp_index[-1][0]
    bins = []
    prev = start
    bins.append(x[0:start])
    for i in range(len(dp_index)-2, 0, -1):
        start = dp_index[i][start]
        bins.append(x[prev:start])
        prev = start
    bins.append(x[start:])
    return dp_matrix, bins
                    
    

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

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)
import submission as submission

matrix, bins = submission.v_opt_dp([7,9,13,5,35,42,6,12,4,5,7], 6)
print("Bins = {}".format(bins))
print("Matrix =")
for row in matrix:
    print(row)<jupyter_output>Bins = [[7, 9, 13, 5], [35], [42], [6], [12], [4, 5, 7]]
Matrix =
[-1, -1, -1, -1, -1, 1071.3333333333335, 38.800000000000004, 38.0, 4.666666666666666, 2.0, 0.0]
[-1, -1, -1, -1, 63.300000000000004, 38.800000000000004, 22.666666666666664, 4.666666666666666, 0.5, 0.0, -1]
[-1, -1, -1, 63.300000000000004, 38.800000000000004, 22.666666666666664, 4.666666666666666, 0.5, -0.5, -1, -1]
[-1, -1, 63.300000000000004, 38.800000000000004, 22.666666666666664, 4.666666666666666, 0.5, -0.5, -1, -1, -1]
[-1, 46.800000000000004, 38.800000000000004, 22.666666666666664, 4.666666666666666, 0.5, -0.5, -1, -1, -1, -1]
[39.666666666666664, 30.666666666666664, 22.666666666666664, 4.666666666666666, 0.5, -0.5, -1, -1, -1, -1, -1]
{'fraction_non_alphanumeric': 0.1119567394352093, 'fraction_numerical': 0.10755057079911877, 'mean_word_length': 3.0048115477145148, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 9, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 23, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '622789', 'license': 'MIT', 'n_tokens_mistral': 1921, 'n_tokens_neox': 1543, 'n_words': 620, 'path': 'Lab2/Lab2-Specs.ipynb', 'repo_name': 'Bennyhwanggggg/Data-Warehousing-and-Data-Mining', 'size': '4993'}