1. Design a data structure IntSet that can hold a set of integers. Hide the priv

Question

1. Design a data structure IntSet that can hold a set of integers. Hide the private implementation: a binary search tree of integer objects.

Provide the following methods:

- A constructor to make an empty set

- void add(int x) to add x if it is not present

- void remove(int x) to remove x if it is present

- void print() to print all elements currently in the set

- boolean contains(int x) to test whether x is present

Test every method

2. Write a program that includes a method converting a two-dimensional array of ints to a two-dimensional array of boolean values. If the integer value is greater than or equal to 0, then the corresponding boolean vlaue is true; otherwise it is false. Add the necessary code to count how many statements are executed in the innermost loop. Run several simulations depending on the number of rows and columns in the argument integer array. What is the running time of the method as a function of the number of rows and columns of the parameter array?(You should assume that each row has the same number of columns.

3. Insert all words from a large file (such as the novel "War and Peace", which is available on the internet) into a hash set and a tree set. Time the results. Which data structure is faster?

Explanation / Answer

// Create a new node, with v as its contained value and next as // the value of the next pointer function make-node(v, node next): node let result := new node {v, next} return result end // Returns the value contained in node n function get-value(node n): element return n.value end // Returns the value of node n's next pointer function get-next(node n): node return n.next end // Sets the contained value of n to be v function set-value(node n, v) n.value := v end // Sets the value of node n's next pointer to be new-next function set-next(node n, new-next) n.next := new-next end // Create a new node, with v as its contained value and next as // the value of the next pointer function make-node(v, node next): node let result := new node {v, next} return result end // Returns the value contained in node n function get-value(node n): element return n.value end // Returns the value of node n's next pointer function get-next(node n): node return n.next end // Sets the contained value of n to be v function set-value(node n, v) n.value := v end // Sets the value of node n's next pointer to be new-next function set-next(node n, new-next) n.next := new-next end program(input-stream in, output-stream out) let total := 0 let count := 0 let largest := while has-next-integer(in): let i := read-integer(in) total := total + i count := count + 1 largest := max(largest, i) repeat println out "Maximum: " largest if count != 0: println out "Average: " (total / count) fi end program(input-stream in, output-stream out) let largest := let nodes := null while has-next-integer(in): let i := read-integer(in) nodes := make-node(i, nodes) // contain the value i, // and remember the previous numbers too largest := max(largest, i) repeat println out "Maximum: " largest // now compute the averages of all factors of largest let total := 0 let count := 0 while nodes != null: let j := get-value(nodes) if j divides largest: total := total + j count := count + 1 fi nodes := get-next(nodes) repeat if count != 0: println out "Average: " (total / count) fi end program (input-stream in, output-stream out) let largest := let nodes := null while has-next-integer (in): let i := read-integer (in) if (nodes == null) nodes := make-node(i, null) // construct first node in the list else nodes := set-next (nodes, make-node (i, null)) // append new node to the end of the list largest := max(largest, i) repeat println out "Maximum: " largest // now compute the averages of all factors of largest let total := 0 let count := 0 while nodes != null: let j := get-value(nodes) if j divides largest: total := total + j count := count + 1 fi nodes := get-next(nodes) repeat if count != 0: println out "Average: " (total / count) fi end function find-min-plus-max(array a[1..n]) // First, find the smallest element in the array let j := ; for i := 1 to n: j := min(j, a[i]) repeat let minim := j // Now, find the biggest element, add it to the smallest and j := ; for i := 1 to n: j := max(j, a[i]) repeat let maxim := j // return the sum of the two return minim + maxim; end

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.