CS 2 (Winter 2024) Lab 04: Recursion

This lab focuses on common misconceptions and errors in trees and recursive backtracking.


Register for the lab using grinch: https://grinch.caltech.edu/register. For this assignment, DO NOT BOTHER cloning the repository. The button at the bottom of this page will automatically submit your answers, and gitlab will check them for you.

Part 1: The HuffmanNode class

Consider the following HuffmanNode class which represents a dictionary which maps binary strings to characters:

L0: private static HuffmanNode {
L1:    public final Character value;
L2:    public Map<Boolean, HuffmanNode> children;

L3:    public HuffmanNode() {}

L4:    public HuffmanNode(char value) {
L5:        this.value = value;
L6:    }
L7: }

Fundamentally, any decompression algorithm takes a stream (or String) of bits and turns them back into a series of actual characters. Huffman decompression achieves this by constructing a tree (technically, a trie) where the leaves of the tree represent specific characters, and the path (i.e., left is 0 and right is 1) we took from the root to get to the leaf node is the binary string that represents that character.

For example, if we have the following Huffman Tree, where o represents an internal node with no value:

   / \
  c   o
     / \
    a   b

It could be represented as HuffmanNodes as follows:

HuffmanNode(value=null, children={
    false=HuffmanNode(value='c', children={}),
    true=HuffmanNode(value=null, children={
        false=HuffmanNode(value='a', children={}),
        true=HuffmanNode(value='b', children={})

Note that the children map only ever has false and true as keys (which represent 0 and 1, respectively). Furthermore, leaf nodes (i.e., the ones which character values) have an empty children map.

Fundamentally, you can think of Huffman trees as TrieMaps with binary strings as keys and characters as values.

Part 2: Getting the Whole Dictionary

L00: _______ Set<String> getDictionary() {
L01:    Set<String> result = new HashSet<>();
L02:    List<String> acc = new ArrayList<>();
L03:    getDictionary(this.root, result, acc);
L04:    return result;
L05: }

L06: _______ Set<String> getDictionary(HuffmanNode node, Set<String> result, List<String> acc) {
L07:    if (node == null || node.children.isEmpty()) {
L08:        result.add(String.join("", acc));
L09:    }
L10:    else {
L11:        acc.add("0")
L12:        getDictionary(node.children.get(false), result, acc);

L13:        acc.add("1")
L14:        getDictionary(node.children.get(true), result, acc);
L15:    }
L16:    return result;
L17: }

Part 3: Huffman Decompression

L01: public static String decompress(HuffmanNode node, String bits) {
L02:    String result = "";
L03:    while (!bits.isEmpty()) {
L04:        result += nextCharacter(node, bits);
L05:    }
L06:    return result;
L07: }

L08: public static char nextCharacter(HuffmanNode node, String bits) {
L09:    if (node == null || node.children.isEmpty()) {
L10:        return node.value;
L11:     }
L12:     else {
L13:         if (bits.substring(0, 1) == "0") {
L14:             nextCharacter(node.get(false), bits.substring(1));
L15:         }
L16:         else {
L17:             nextCharacter(node.get(false), bits.substring(1));
L18:         }
L19:     }
L20: }
Submit Responses For Credit