HW6. Heaps and Succinct Data Structures (13th of Oct, 23.59)
EX1. Read the Kamp (CACM 2010 53:7) "You're doing it all wrong.”
http://queue.acm.org/detail.cfm?id=1814327.
- State in your own words the main criticism represented in the article, with brief justification. What is your opinion about the article?
- Provide the proposed formula from the article (block size, node i -> parent; node i -> first child, second child), as example code snippets.
- How would you redesign the similar idea for mapping for k-ary heap?
EX2: Design and run an experiment with the goal to measure the potential benefit from the Kamp-like implementation either for the binary heap or (any of the) k-ary heap.
Describe the setting for an experiment (insertions, deletions, decrease-value, …) and report the respective execution time measurements, that should favor your design. You are the master of defining the best possible experiments to prove the superiority of your invention.
EX3 – Design of a succinct TRIE(Conceptual)
Goal: Understand how to represent a trie using a DFS-parenthesis encoding.
Task:
Given the keywords { aaba , abaa , aabcab , aabcac , acbaa , aaca }
Draw the trie built on these words (nodes correspond to prefixes, edges to single letters).
Perform a depth-first traversal and write down the parenthesis string corresponding to the visit order, e.g. something like
(()(()())())
Each node has an open parenthesis ( when entered and a close ) when finished.
Show how you could locate:
- the subtree for the prefix "aab", and
- how many children that node has.
Briefly explain (2–3 sentences) which operations a fast succinct implementation would need, - e.g., rank, select, findclose.
Deliverable:
- A small hand-drawn or digital diagram of the trie.
- The corresponding parenthesis sequence.
- Short notes (bullet points are fine).
EX4 – Implementation (Prototype)
Goal: Validate that the DFS-parenthesis structure works correctly.
Task
Represent your tree from EX3 as a simple string of parentheses, e.g. bp = "(()(()())())".
Write a small program that implements:
- findclose(i): returns the index of the ')' matching the '(' at position i.
- subtree_size(i): counts how many nodes are inside that subtree (including itself).
Test both functions for a few nodes and print the results.
Hint: You can implement findclose by scanning forward while maintaining a counter of open parentheses.
Deliverable
- Short, working code (≈10–20 lines).
- Example outputs showing correct matching and subtree sizes.
EX5 – Scaling and Space Measurement
Goal: Estimate or measure how large the succinct representation would be on a real dictionary.
Task
Filter the UNIX words file to include only lowercase English words (locate the words.txt on your computer or google for it) :
grep -x -E '[a-z]+' /usr/share/dict/words > clean.txt
- Estimate the number of trie nodes: approximately the total number of characters across all words.
- The DFS-parenthesis encoding uses two bits per node (one for (, one for )).
- Compute the total bits and convert to bytes or kilobytes.
- Compare to the size of the plain text file (wc -c clean.txt).
- Write a short comment on when and why a succinct representation might use less space.
Hint: You can store the parentheses in a simple byte array, integer array, or string — no external succinct library is needed.
Deliverable
- Basic numeric estimates (table or short list).
- A brief paragraph discussing your findings.
EX6: (bonus, 2p) Study the extra information needed for the LCA, the (lowest common ancestor) for any two nodes in the tree, suitable for the succinct tree implementation, either for the parentheses or heap-like representation. Report the technique and provide an example with illustration(s).