CS1500
Algorithms and Data Structures for Engineering, FALL 2012
HW4 Pointers
Problem1 Write the following two functions:
int* ReverseArray (int X[], int size) - returns an array containing all elements from the input array in reverse order
int Median (int* , int ) - returns the median element of the input array (which may or may not be sorted)
This problem does not require pseudocode.
EXTRA CREDIT: Write the median function above with an algorithm that
requires only linear time. If you solve the extra credit, the pseudocode is required to show the algorithm for finding the median value.
Problem2 - same problem as in hw3, only now you have to handle collisions in your hash table.
Take as input the name of the text file (create your own text
document for testing purposes). Process the text in the file,
keeping track for each word of the number of occurrences.
Output each word and its count.
Hint: Implement a hash functionthat
maps words into keys, then use the keys as word ID-s and as hash table
indices. To handle collisions, each node in your table is going
to be the head of a linked list which contains all words/counts that
have been hashed to that node index.
For this problem you are required to submit pseudocode.
While for HW3 a look-up table containing the words encountered "so far" is acceptable, the same is not OK for this assignment. You really have to use a hash function, linked lists, and an array or vector (as hash table) such that for every word
* hushFunction(word)=key
* A[key] is the listhead of the list containing all words that hash to key.