讲解Frequency Element、辅导Python、讲解algorithm、Python编程语言辅导
- 首页 >> OS编程 Problem 1 (20 points)
You are given an array of size N, where an element has a higher frequency than any other element in the array. Specifically, that element occurs at least N/2+1 times. You are not allowed to compare elements in the array, however you are allowed to check if any two elements are equal.
You are to design a randomized algorithm that returns the element with the highest frequency in such an array in linear time.
a)Complete the following pseudo-code (and python code in hw2_pr1.py) to accomplish this task. (10 points)
Highest Frequency Element(Input: array A of length N)
While True
i = random(1,N)
// chooses a random number between 1 and N
b)Show that the expected number of checks for equality is Θ(N) (10 points)
Problem 2. (25 points)
The rb_tree.py file contains an implementation of the red-black tree as described in the CLRS textbook.
Follow the insertion algorithm on page 315 to complete the insert() function. Please note that an implementation of insert_fixup() function is provided for you. Use it as shown in CLRS.
Problem 3. (25 points)
Background
The file hash.py contains a hash function that works on strings. That hash function works by adding up the ASCII value of each character in the string and then using modulus to ensure that number is within the range of the table. The function works fairly well for some input sets, but not always. As an example, consider a company that sells lots of different products. Each product has a product code which consists of three capital letters, and a price. The company wants to store their inventory in a hash table so they can quickly look up the price by entering the product code. We can estimate how good of a job our hash function is doing by estimating the average number of comparisons we need to make to find an item, and the max number we need to make. For a hash table that uses chaining (an array of linked lists), we can estimate this by counting how many elements are in an average list that has data in it, and how many elements are in the longest list.
To do:
hash.py uses the simple hash function described earlier to store 500 random products in a table of size 2,000.
Run it to see the number of lists being used, and what the average and max sized list are (it will print this out).
Revise the hash function of the program to spread the data out better.
You should get the average filled list to have fewer than 5 elements in it (less than 2 would be great).
The hashed value must be solely based on the value of the string, it can’t have any randomness (because we have to be able to find the item again without storing the different hash funcitons!).
Explain why your hash function spreads the data better.
Problem 4. (20 points)
Recall that a complete graph is one in which every node is connected to every other node by an edge. In this problem, you will write a function to test whether or not a graph (based on an adjacency matrix) is complete.
completeGraph.py contains a graph class based on an adjacency matrix.
This file has an empty function called complete.
Fill in this function so that it tests the graph to check if it is complete or not and returns a boolean.
The main function tests this function on a graph that is complete and one that is not. For grading purposes your function may be tested on other graphs as well.
You are given an array of size N, where an element has a higher frequency than any other element in the array. Specifically, that element occurs at least N/2+1 times. You are not allowed to compare elements in the array, however you are allowed to check if any two elements are equal.
You are to design a randomized algorithm that returns the element with the highest frequency in such an array in linear time.
a)Complete the following pseudo-code (and python code in hw2_pr1.py) to accomplish this task. (10 points)
Highest Frequency Element(Input: array A of length N)
While True
i = random(1,N)
// chooses a random number between 1 and N
b)Show that the expected number of checks for equality is Θ(N) (10 points)
Problem 2. (25 points)
The rb_tree.py file contains an implementation of the red-black tree as described in the CLRS textbook.
Follow the insertion algorithm on page 315 to complete the insert() function. Please note that an implementation of insert_fixup() function is provided for you. Use it as shown in CLRS.
Problem 3. (25 points)
Background
The file hash.py contains a hash function that works on strings. That hash function works by adding up the ASCII value of each character in the string and then using modulus to ensure that number is within the range of the table. The function works fairly well for some input sets, but not always. As an example, consider a company that sells lots of different products. Each product has a product code which consists of three capital letters, and a price. The company wants to store their inventory in a hash table so they can quickly look up the price by entering the product code. We can estimate how good of a job our hash function is doing by estimating the average number of comparisons we need to make to find an item, and the max number we need to make. For a hash table that uses chaining (an array of linked lists), we can estimate this by counting how many elements are in an average list that has data in it, and how many elements are in the longest list.
To do:
hash.py uses the simple hash function described earlier to store 500 random products in a table of size 2,000.
Run it to see the number of lists being used, and what the average and max sized list are (it will print this out).
Revise the hash function of the program to spread the data out better.
You should get the average filled list to have fewer than 5 elements in it (less than 2 would be great).
The hashed value must be solely based on the value of the string, it can’t have any randomness (because we have to be able to find the item again without storing the different hash funcitons!).
Explain why your hash function spreads the data better.
Problem 4. (20 points)
Recall that a complete graph is one in which every node is connected to every other node by an edge. In this problem, you will write a function to test whether or not a graph (based on an adjacency matrix) is complete.
completeGraph.py contains a graph class based on an adjacency matrix.
This file has an empty function called complete.
Fill in this function so that it tests the graph to check if it is complete or not and returns a boolean.
The main function tests this function on a graph that is complete and one that is not. For grading purposes your function may be tested on other graphs as well.