Problems

Huffman Coding

Problem Statement:
Given a set of n characters from an alphabet A and their frequencies, assign a binary code to each character c ∈ A such that the total cost \( \sum_{c \in A} \text{freq}(c) \times |\text{binarycode}(c)| \) is minimized.

Approach:

Huffman Coding is a classic greedy algorithm used for lossless data compression. The goal is to assign shorter codes to more frequent characters, ensuring no code is a prefix of another (prefix-free property).

1. Build a Min-Heap:
   • Insert all characters as nodes, prioritized by frequency.
2. Construct the Huffman Tree:
   • While there is more than one node in the heap:
   • Remove the two nodes with the lowest frequencies.
   • Create a new node with these two as children and frequency equal to their sum.
   • Insert the new node back into the heap.
   • The remaining node is the root of the Huffman tree.
3. Generate Binary Codes:
   • Traverse the tree from root to leaves:
   • Assign '0' to left edges and '1' to right edges.
   • The path from root to each leaf gives the binary code for that character.

// Node class for Huffman Tree
data class Node(val c: Char?, val freq: Int) : Comparable<Node> {
    var left: Node? = null
    var right: Node? = null
    override fun compareTo(other: Node): Int = freq - other.freq
}

fun buildHuffmanTree(freq: Map<Char, Int>): Node? {
    val pq = PriorityQueue<Node>()
    freq.forEach { (c, cnt) ->
        pq.add(Node(c, cnt))
    }
    while (pq.size > 1) {
        val l = pq.poll()
        val r = pq.poll()
        val m = Node(null, l.freq + r.freq)
        m.left = l
        m.right = r
        pq.add(m)
    }
    return pq.poll()
}

fun generateCode(tree: Node) {
    val codes = mutableMapOf<Char, Pair<Int, Int>>()

    val stack = LinkedLists<Triple<Node, Int, Int>()
    stack.add(Triple(tree, 0, 0))
    while(stack.isNotEmpty()) {
        val (node, code, len) = stack.removeFirst()

        if(node.char != null) {
            codes[node.char] = Pair(code, len)
        } else{
            node.left?.let {
                stack.add(Triple(it, code shl 1, len + 1))
            }
            node.right?.let {
                stack.add(Triple(it, (code shl 1) or 1, len + 1))
            }
        }
    }

    return codes
}

fun huffmanCoding(text: String) {
    val freq = string.groupingBy{ it }.eachCount()
    val tree = buildTree(freq)

    val binaryCode = generatesCodes()
}

---

Interval Scheduling

Problem Statement: Given a set of n intervals S = {(\(start_i\), \(end_i\))}. Find the maximum subset S' such that no intervals in S' overlaps.

Approach:

1. Sort on end times
2. Iterate: If the current intervals start time is more than the previous selected intervals end time select it, else continue.

fun maxIntervals(intervals: List<Pair<Int, Int>>) { 
    val sorted = intervals.sortedBy { it.second } 
    val selectedIntervals = mutableListOf<Pair<Int, Int>>()
    selectedIntervals.add(sorted.first())
    sorted.drop(1).forEach { 
      if(it.first > sorted.last().second) {
          sorted.add(it)
      }
    }
}

Weighted version: refer to the DP section

---

Room scheduling Problem

Also called interval-coloring problem

Problem Statement: Given a set of n intervals S = {(\(start_i\), \(end_i\))}. Each interval is a request for a room. Find the minimum number of rooms required to schedule all requests.

Approach:

1. Sort on start times
2. Iterate: For current request assign it to an available class, i.e., start time > end time of last class in the room. If no room is available, create a new room.

fun maxRooms(intervals: List<Pair<Int, Int>>) {
    intervals.sortBy { it.first }

    // Stores end time and there room
    val endTimes = PriorityQueue(compareBy<Pair<Int, Int>> { it.first }) 
    val rooms = mutableMapOf<Pair<Int, Int>, Int>()
    var numRooms = 0
    intervals.forEach {
        // if current interval start time is after end of any previous rooms interval use it else need new room
        // We only need to check smallest end time so we use Priority queue
        if(endTimes.isNotEmpty() && endTimes.peek.first() <= it.first) {
            val (_, roonNum) = endTimes.poll()
            rooms[it] = roomNum
            endtimes.add(Pair(it.second), roomNum)
        } else {
            rooms[it] = numRooms++
            endtimes.add(Pair(it.second), numRooms)
        }
    }

    return rooms
}

It Can be solved using line sweep algorithm

Variants: add max capacity to room and min requirement for an interval

---

Fractional Knapsack Problem

Problem Statement: Given items and their weights and values. How to maximize total value subject to max weight C?

The idea is we want to achieve max value per weight.

Approach:

1. Get value per weight, density, for each item.
2. Add items with most density until the max weight is reached. If the current item does not fit entirely, take a fraction of it to fill the remaining capacity.

fun knaspack(weights: List<Int>, values: List<Int>, W: Int) {
    var value = 0
    var tW = 0
    val density = weights.zip(values).sortedByDescending{ it.second / it.first }

    for((w, v)  in density) {
        if(W >= tw + w){ 
            value += v
            tW += w
        } else {
            value += v * ((W- tw) / w) 
        }
    }
    return value
}

Variant: 0/1 Knapsack problem - refer DP section.