How sparse must the matrix be for the sparse representation

Assignment Help Basic Computer Science

Reference no: EM131214985

Suppose we wish to store an n × n boolean matrix (0 and 1 elements only). We could represent it by the bits themselves, or we could represent the matrix by listing the positions of the 1's as pairs of integers, each integer requiring ⌈log2 n⌉ bits. The former is suitable for dense matrices; the latter is suitable for sparse matrices. How sparse must the matrix be (i.e., what fraction of the elements should be 1's) for the sparse representation to save space?

Reference no: EM131214985

Questions Cloud

Determine the tail length for each stream element : Determine the tail length for each stream element and the resulting estimate of the number of distinct elements if the hash function is:

What percentage of the class is female : A professor is studying the performance of various student groups in his class.- If the overall class average score is E [X| F] = 74.6 , what percentage of the class is female?

Memory and result sets : What is the effect of large result sets on memory? What are good ways to use memory more efficiently?

System fulfilling the statement of need : You have been asked to lead a software development team to build a system fulfilling the Statement of Need specified in project 1. Your team is employed by a small company. The customer wants a project that balances reasonable development cost, ti..

How sparse must the matrix be for the sparse representation : The former is suitable for dense matrices; the latter is suitable for sparse matrices. How sparse must the matrix be (i.e., what fraction of the elements should be 1's) for the sparse representation to save space?

Evaluate the macroeconomic performance of an economy : Research and critically analyse an evaluate the macroeconomic performance of an economy - How is real GDP growth related to the other indicators in Australia and the USA? Explain.

What are effects of nonperforming loans on a banking system : What are the effects of nonperforming loans on a banking system? How did Japan plan to ensure self-sustaining growth in the face of strong demographic pressures?

Implement in a network : Which of the FCAPS models, in your view, is the most difficult to design and implement in a network, and why?

Advantages does this storage media : What advantages does this storage media have over using your system's hard drive or some other external media (external hard drive, flash drive, R/W disks) for storing your data?

User Account

All Pages