Series catalog:

  • “Introduction to Algorithms” part one, part two algorithm analysis and Javascript implementation
  • “Introduction to Algorithms” part 4 – Dynamic programming analysis and Javascript implementation

The full code is here

Greedy algorithm (Greedy algorithm) is an algorithm that takes the best or most favorable (i.e., most favorable) choice in its current state at each step in the hope that the result will be either the best or optimal. Greedy algorithms are particularly effective in problems with optimal substructures. Optimal substructure means that the local optimal solution determines the global optimal solution. Simply put, a problem can be resolved in subproblems, and the optimal solution of the subproblem can be recurred to the optimal solution of the final problem. Greedy algorithms differ from dynamic programming in that they choose a solution for each subproblem and cannot fall back. Dynamic planning saves the previous calculation results and selects the current one based on the previous results, providing the rollback function.

General step

  1. Determine the optimal substructure
  2. Design recursive algorithms
  3. Greedy feasibility, mainly in the use of dynamic programming and greedy
  4. The recursive algorithm is transformed into an iterative algorithm

Activity selection problem

Background introduction

Let’s say we have a venue, and there are a lot of events that need to use it, and we want to schedule as many events as possible. We have a timetable, and the events are arranged according to the end time

Si: start time Fi: end time

Algorithm ideas

Again, dichotomy assuming a recurrence c[I,j]=c[I,k]+c[j,k]+1 c is the number of activities given the set Sij and assuming Aij is the optimal solution and ak is the middle value, then we need to find Sik(the activities after AI ends and before AK starts) and The optimal set in Skj(those activities after AK ends and before AJ begins). If there is a set Bik whose number of activities is greater than Aik, then it contradicts the previous assumption that Aij is the optimal solution. So the recurrence works. So that’s the idea of dynamic programming. As much as possible, we should choose activities that end early so that we have more resources left over for other activities to allocate. Why is such greed right? conditionals

  • Sk is a set
  • Am was the first event to end
  • Ak is the optimal solution
  • Aj is the activity that ends earliest in the optimal solution

If AM = aj, then it proves that the earliest finished activity must be in the optimal solution if AM! = aj, because “am” must end before “aj” so if I replace “am” with “aj”, “AM” does not intersect with the activity in “Ak”,Ak is still true. Therefore, am can still be included in the optimal solution. It follows that our greedy strategy is valid

The algorithm process

The code process is simple because it is sorted by end time. Just iterate through it and select the one that starts later than the last one. Then record the end time again.

Code implementation

function GreedyActivitySelector(s, f) {
  let n = s.length;
  let A = [0]; // The final activity array holds the activity number
  let end = f[0]; // Record the end time of the last activity
  for (let i = 1; i < n; i++) {
    if(s[i] >= end) { A.push(i); end = f[i]; }}return A;
}
module.exports = GreedyActivitySelector;
Copy the code

Simple Test Case (JEST)

const GreedyActivitySelector = require(".. /chapter-16/GreedyActivitySelector");
const s = [1.3.0.5.3.5.6.8.8.2.12];
const f = [4.5.6.7.9.9.10.11.12.14.16];
test("Activity Selection Problem".() = > {
  expect(GreedyActivitySelector(s, f)).toEqual([0.3.7.10]);
});
Copy the code

Huffman coding

Background introduction

Huffman encoding compresses data efficiently, typically saving 20 to 90 percent of time. Here’s how he did it

  1. Count the frequency of occurrence of each character
  2. The higher the frequency, the shorter the number string
  3. No short string of digits can be a prefix of another long one (10,101)

You can compress 300000 bits to 224000 bits as shown in the table above

Algorithm ideas

A binary tree with depth k and number of nodes 2^ k-1 is a full binary tree

  • There must be an odd number of nodes
  • Layer I has 2 to the I minus 1 nodes
  • I have 2 to the k minus 1 leaves

The optimal encoding scheme for a file always corresponds to a full binary tree. Right? | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

The algorithm process

The algorithm uses a minimum priority queue with the attribute freq as the key, which has identified the two lowest frequency objects and merges them. Here, the minimum priority queue is directly modified using the previous maximum priority queue. For details, please refer to the previous part 1 and 2. We get the recursive traversal output of the merged Haverman tree, and we get the code for each key

The entire build process is shown below

Code implementation

const format = (input) = > {
    return input.map((e) = > {
        e.priority = e.freq
        return e
    })
}
var MinPriorityQueue = require('.. /chapter-06/MinPriorityQueue')

// The whole function is used to construct the Huffman tree
function HuffmanTree(c) {
    let n = c.length;
    let Q = new MinPriorityQueue(c);
    for (let i = 0; i < n - 1; i++) {
        let z = { key: ' '.freq: 0.priority: 0,}// Take the smallest two here
        let x = Q.extractMin() 
        let y = Q.extractMin()

        // Add to get new nodes and merge
        z.priority = x.priority + y.priority
        z.freq = x.freq + y.freq
        z.key = z.freq
        z.left = x
        z.right = y
        // The binary tree is changed from an array to an object for easy look-down
        Q.insert(z)
    }
    return Q.queue[0]}// This function defines all encodings by passing through code recursively
function PrintHuffman(Node) {
    let codeMap = new Map(a)// Store the code corresponding to the key
    let code = ' '
    const find = (node, codeMap, code) = > {
        let pass_code_left = code // Passthrough code for the left subtree
        let pass_code_right = code // Passthrough code for the right subtree
        let IS_NUMBER = / ^ [0-9] * $/
        if (IS_NUMBER.test(node.key)) {  // Boundary conditions end recursion when key is not a character
            if (node.left) {
                pass_code_left = pass_code_left + '0'
                find(node.left, codeMap, pass_code_left)
            }
            if (node.right) {
                pass_code_right = pass_code_right + '1'
                find(node.right, codeMap, pass_code_right)
            }
        } else {
            codeMap[node.key] = code
        }
    }
    find(Node, codeMap, code)
    return codeMap
}

function Huffman(input){
    return PrintHuffman(HuffmanTree(format(input)))
}

module.exports = Huffman
Copy the code

Simple Test Case (JEST)

var Huffman  = require('.. /chapter-16/Huffman') 
var input = [
    { key: 'f'.freq: 5 },
    { key: 'e'.freq: 9 },
    { key: 'c'.freq: 12 },
    { key: 'b'.freq: 13 },
    { key: 'd'.freq: 16 },
    { key: 'a'.freq: 45 }
]

test('Huffman code'.() = >{
    expect(Huffman(input).a).toBe('0')
    expect(Huffman(input).c).toBe('100')})Copy the code