1. For each scenario described below, discuss the algorithm and the data structu

Question

1.       For each scenario described below, discuss the algorithm and the data structure you would use to count the occurrences of characters in a file given the following constraints.   Present a discussion on the algorithm only, do not present source code.

a.       The program must utilize the minimum amount of memory throughout the duration of the program.

b.       The program must minimize the power consumption used by the program (limit the CPU load).

c.       The program will be required to load the frequencies once, but the program will access the individual frequencies often during the execution of the program. Provide a design that conserves memory utilization while providing the fastest access to the data.

d.       The program will need to calculate the frequencies, but the program must preserve the order in which the characters were encountered while processing the file. That is, the order of the elements in the data structure(s) must be the order in which they were first encountered in the file. The program must conserve both CPU and memory with memory being the most important. The program will not be reading a file, but a network stream for input. Characters will be sent via a socket program to the counting program. The program must continuously track the frequencies of all characters encountered while the program is running. A key constraint is that the list must always be sorted in frequency order so that the smallest

Any help on what data structures and what algorithms would be best for each scenario would be appreciated.   No code needed, just some descriptions. Thanks.

Explanation / Answer

To make the efficient use of your program you should analyse the senario first. Here is my analysis

a. The program collects the frequency stream throught the network. So you cannot predict the maximum frequency count. So using of array with fixed size will not help you to minimise the memory usage.

b. If you want to minimise CPU execution, you have to find out an algorithm which will give you O(1) or O(n) time complexity. Here link list will also not help you.

c. Your data structure should always be sorted becase you frequently will use the frequencies. You have to keep in mind to minimise memory as well as CPU execution.

d. As data comes through network, make a suitable buffer to hold data for processing.

Here, is the optimum solution I found.

Use a vector,

This will resolve your memory utilisation problem in a) because it will not create unnecessary memory.

This will resolve your CPU utilisation problem in b) which can give you constant time access to a particular index value. But here you have to find a way to insert the frequency in particular index value. Calculate the index of the frequency if you know the frequency range, and insert in the vector index if it is not inserted already, solution for your problem in c.

I think this is the optimal solution for your program.

Put a comment if you need more information.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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