DATA1001 Assignment CSE Part

Due date: 23 rd July Friday (Week 8) 5:00 pm 

Marks: 15 marks, weighted 15% of your final mark. 

Submission format: Adobe PDF (preferred) or MS Word Doc. 

Submit to: Moodle.

 Late submission penalty: Assignments finalised after 23 July will be penalised at 20% per 24 hours. If you require an extension, see the Special Consideration policy. 

Q1. (3 marks)

 (1) (2 marks) Draw a binary search tree with the elements inserted by order: {32, 87, 12, 3, 45, 11, 65, 15, 59}.

 (2) (1 mark) Remove 65 from the binary search tree built in question (1), draw the BST after the removal.

Q2. (3 marks) 

Build a decision tree with the following data using ID3 algorithm. Please provide the detailed calculation of information gain at each step

Q3. (3 marks) 

With the following graph, answer the following questions:

 (1) (1.5 mark) Find a BFS traversal order starting from node 2. 

(2) (1.5 mark) Find a DFS traversal order starting from node 2.

Q4. (3 marks）

 Consider a Bloom filter of size m = 12 (i.e., 12 bits) and has 3 functions that take a string (lowercase) as input:

In these three functions, ‘str’ denotes the input string, ‘c’ denotes the character in the string, ‘str.length’ denotes the length of string (how many characters are there in the string). See the following examples:

e.g., h1(“bd”) = (1 + 3) mod 12 = 4; 

b is the second character, a is the first one, so ‘b’-‘a’ = 2 – 1 = 1. 

Similarly, ‘d’ – ‘a’ = 4 – 1 = 3.

h2(“bd”) = (25 + 23) mod 12 = 0;

 ‘z’ – ‘b’ + 1 = 26 -2 + 1 = 25.

 Similarly, ‘z’ – ‘d’ + 1 = 26 -4 + 1 = 23.

h3(“bd”) = 2 mod 12 = 2. 

Because the length of ‘bd’ is 2.

Answer the following questions: 

(1). (2 marks) Given a set of string S = {“unsw”, “cse”, “school”}, show the updated result of the Bloom filter. 

(2). (1 mark) Given a string “math”, use the Bloom filter to check whether it is contained in S, and give the reason.

Q5. (3 marks) 

Find the maximal k-core of the following graph with k=4. Give the nodes that are in the maximal k-core as the answer (e.g., if nodes B, G are in the k-core, your answer will be {B, G}.)