*Introduction to Algorithms*by Thomas H. Cormen, et. al. Being unable to resist peer pressure I decided to follow and read along.

I plan on blogging my way through the chapters writing my answers to the questions as I go through the book. Like most of my plans they don't always work out, but one could try.

Here it goes!

**Sorting**- Sorting comes up in virtually every algorithm one could think of. Everything from optimizing monetary investments to efficient compression algorithms has to sort data at some point or another. A harder question might be: Name one non-trivial algorithm that doesn't require sorting.

**Multiplying Matrices**- graphics and scientific problems frequently require matrix operations.

**Convex Hull**- Collision detection for use in games, modeling biological systems, or other related work could make use of this

While most probabilistic structures have certain properties in common, bloom filters have a number of interesting pros and cons.

- A negative result is definitive - if a query returns that an element has not been added then one knows this to be 100% true.
- Since hashes are fixed size the amount of memory a Bloom Filter uses is known and bounded.
- Bloom filters can quickly become useless with large amounts of data. It is possible that every bit will be set to 1 which effectively makes the query a NOP.
- It is impossible to remove data from a bloom filter. One can't just set all the bits of the hash to a zero because that might be removing other elements as well.
- Without a second set of data there is no way to deterministically list all elements (unlike other probabilistic data structures such as Skip Lists).

- The shortest path problem is
- Given a weighted (undirected) graph G:
, a start vertex $V_0$ and an end vertex $V_e$, find a path between $V_0$ and $V_e$ such that the sum of the weights is minimized. This could be expanded to $Given a weighted graph G: , find a path between every pair such that the sum of the weights for each path is minimized. - Traveling salesman is defined as:
- Given a weighted, undirected, graph G:
and a start vertex $V_0$ find a path starting and ending at $V_0$ such that it passes through every other vertex exactly once and the sum of the weights is minimized.

**update 2011-06-30:**modified text of answers 1.1-3 and 1.1-5 to be more clear.

thanks,helpfull

ReplyDeletethanks

ReplyDeleteThank you Sir...nice presentation of the answers...Sir can you please reply 1.1-3 again by any common data structure like stack/queue/ linked list..I am not getting the answer given by you...and bloom filter is a probabilistic data structure.

ReplyDeleteIf you have a specific question I'd be happy to answer, but I can't answer for you the pros and cons of every data structure in existence.

DeleteVery Useful Indeed, please post solutions for the other chapters as well.

ReplyDelete