COMP9318 Lab1

Instructions

This note book contains instructions for COMP9318-lab1.

You are required to complete your implementation in a seperate 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.

Submission instructions for lab1 will be emailed to all students within 1-2 days.

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. However, 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 20th March, 2018. We will **not accept any late submissions.

Question 0: An example (0 point)

In this section, we illustrate the steps needed to complete this notebook and prepare the file submission.py. As an example, you are required to implement a function that takes two arguments a and b, and outputs their sum.

You will be provided with the definition of the function as given below:

def add(a, b): # do not change the heading of the function

pass # **replace** this line with your code

Step 1: You need to write your implementation in the function body like below (you should remove the pass line from the function body):

def add(a, b): # do not change the heading of the function

return a + b

Step 2: you need to paste your code to submission.py, which originally contains only function definitions. As an example, we have done the Question 0 for you.

Question 1: Integer square root of an integer (25 points)

You need to write a function, nsqrt(), that takes as input an integer x, and return the largest integer that does not exceed x−−√ . You need to abide by the following constraints:

The time complexity of your algorithm should be O(logx) .

You cannot use sqrt() function.

For example, nsqrt(11) = 3, and nsqrt(1369) = 37.

def nsqrt(x): # do not change the heading of the function

if (x < 2):

return x;

else:

small = nsqrt(x // 4) * 2

large = small + 1

if (large * large > x):

return small

else:

return large

you can test your implementation using the following code.

import submission as submission

print(submission.nsqrt(11), submission.nsqrt(1369))

3 37

Question 2: Finding a root (25 points)

Use Newton’s method to find a root of an equation numerically. Newton’s method starts from x0 and iteratively computes

xi+1=xi−f(xi)f′(xi).

We plot the equation below (for x > 0)

import math

import matplotlib

import numpy as np

import matplotlib.pyplot as plt

%matplotlib inline

def f(x):

return x * math.log(x) – 16.0

# xvals = np.arange(0.01, 10, 0.01)

xvals = np.arange(0.001, 10, 0.001)

yvals = np.array([f(x) for x in xvals])

plt.plot(xvals, yvals)

plt.plot(xvals, 0*xvals)

plt.show()

Let us consider find a x such that f(x)=xln(x)−16=0 .

Here, f′(x)=(x⋅1x+1⋅ln(x))+0=1+ln(x) .

we denoted it as fprime(x):

def fprime(x):

return 1.0 + math.log(x)

You need to implement Newton’s method below.

NOTE: you must use the default values of the mentioned parameters, do not change them

## We will be using following parameters:

# x_0: initial guess

# EPSILON: stop when abs(x – x_new) < EPSILON

# MAX_ITER: maximum number of iterations

def find_root(f, fprime, x_0=1.0, EPSILON = 1E-7, MAX_ITER = 1000): # do not change the heading of the function

x_new = x_0

for index in range(MAX_ITER):

x = x_new

x_new = x – f(x) / fprime(x)

if abs(x – x_new) < EPSILON:

break;

index += 1;

return x_new;

You can test your implementation using the following code.

Note that we will evaluate your submission with a different function, i.e., f(x) . If you want to change it during your implementation, you should also change f′(x) accordingly.

import submission as submission

x = submission.find_root(f, fprime)

print(x)

print(f(x))

7.792741452820329

0.0

Question 3: Trees (25 + 25 points)

In this question, you need to perform following tasks:

Build a tree from a string, which represents the pre-order traversal of the tree.

Compute the max depth of the tree.

We provide you with the following Tree class, and a helper function which parses the string and returns an array of tokens.

# Note: You need to pay attention to how to determine whether a node is a leaf node in this implementation.

class Tree(object):

def __init__(self, name=’ROOT’, children=None):

self.name = name

self.children = []

if children is not None:

for child in children:

self.add_child(child)

def __repr__(self):

return self.name

def add_child(self, node):

assert isinstance(node, Tree)

self.children.append(node)

The following code demonstrates basic use of the class.

t = Tree(‘*’, [Tree(‘1’),

Tree(‘2’),

Tree(‘+’, [Tree(‘3’),

Tree(‘4’)])])

def print_tree(root, indent=0):

print(‘ ‘ * indent, root)

if len(root.children) > 0:

for child in root.children:

print_tree(child, indent+4)

print_tree(t)

*

1

2

+

3

4

Here is the helper function str_to_tokens, and its sample usage.

import re

def myfind(s, char):

pos = s.find(char)

if pos == -1: # not found

return len(s) + 1

else:

return pos

def next_tok(s): # returns tok, rest_s

if s == ”:

return (None, None)

# normal cases

poss = [myfind(s, ‘ ‘), myfind(s, ‘[‘), myfind(s, ‘]’)]

min_pos = min(poss)

if poss[0] == min_pos: # separator is a space

tok, rest_s = s[ : min_pos], s[min_pos+1 : ] # skip the space

if tok == ”: # more than 1 space

return next_tok(rest_s)

else:

return (tok, rest_s)

else: # separator is a [ or ]

tok, rest_s = s[ : min_pos], s[min_pos : ]

if tok == ”: # the next char is [ or ]

return (rest_s[:1], rest_s[1:])

else:

return (tok, rest_s)

def str_to_tokens(str_tree):

# remove \n first

str_tree = str_tree.replace(‘\n’,”)

out = []

tok, s = next_tok(str_tree)

while tok is not None:

out.append(tok)

tok, s = next_tok(s)

return out

# format: node, list-of-children

str_tree = ”’

1 [2 [3 4 5 ]

6 [7 8 [9] 10 [11 12] ]

13

]

”’

toks = str_to_tokens(str_tree)

print(toks)

[‘1’, ‘[‘, ‘2’, ‘[‘, ‘3’, ‘4’, ‘5’, ‘]’, ‘6’, ‘[‘, ‘7’, ‘8’, ‘[‘, ‘9’, ‘]’, ’10’, ‘[‘, ’11’, ’12’, ‘]’, ‘]’, ’13’, ‘]’]

Question 3-1 (25 points)

Now you need to implement the function make_tree(tokens), which receives tokens formatted like toks above and returns a Tree object.

def make_sub_tree(parent_tree, tokens, start, end):

if start <= end and parent_tree != None:

i = 0

while start + i <= end:

sub_tree = None

while start + i <= end and tokens[start + i] != ‘[‘ and tokens[start + i] != ‘]’:

sub_tree = Tree(tokens[start + i])

parent_tree.add_child(sub_tree)

i += 1

if start + i <= end:

if tokens[start + i] == ‘[‘:

i += 1

i += make_sub_tree(sub_tree, tokens, start + i, end)

elif tokens[start + i] == ‘]’:

i += 1

return i

return i

return 0

def make_tree(tokens): # do not change the heading of the function

if len(tokens) > 0:

the_tree = Tree(tokens[0])

make_sub_tree(the_tree, tokens, 1, len(tokens) – 1)

return the_tree

else:

return None

You can test your implementation using the following code.

import submission as submission

tt = submission.make_tree(toks)

print_tree(tt)

1

2

3

4

5

6

7

8

9

10

11

12

13

Question 3-2 (25 points)

Now you need to implement the max_depth(root) function, which receives the root of the tree and returns the max depth of the tree.

For the given sample tree string, the max depth is 4.

def max_depth(root): # do not change the heading of the function

depth = 0

if None == root:

return depth

depth += 1

max_sub_depth = 0;

if len(root.children) > 0:

for child in root.children:

sub_depth = max_depth(child)

if sub_depth > max_sub_depth:

max_sub_depth = sub_depth

return depth + max_sub_depth

You can test your implementation using the following code.

import submission as submission

depth = submission.max_depth(tt)

print(depth)

4