みんなのコンピュータサイエンス

Chapter 1 Basis

Chapter 2 Complexity

1. Time complexity
2. Space complexity

Chapter 3 Strategy

1. Iteration
2. Recursion
3. Brute force
4. Backtruck
5. Heuristic

heuristic.js

function greedy(wCst) {
    const items = [{w:10, v:3}, {w:15, v:2}, {w:5, v:1}, {w:20, v:5}];
    let wTotal = 0;
    let vTotal = 0;
    items.sort((a, b)=>(b.v / b.w) - (a.v / a.w));
    for (const item of items) {
        if (wTotal + item.w <= wCst) {
            wTotal += item.w;
            vTotal += item.v;
            }
        }
    return [wTotal, vTotal];
    }

6. Divide and conquer

mergeSort.js

function mergeSort(arr){
    if (arr.length == 1) return arr;
    const mid = Math.floor(arr.length/2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let i = 0;
    let j = 0;
    while(i<left.length && j<right.length) {
        if (left[i]<right[j]) {
            result.push(left[i]);
            i++;
            }
        else {
            result.push(right[j]);
            j++;
            }
        }
    return [...result, ...left.slice(i), ...right.slice(j)]
    }

7. Dynamically

DynamicPrograming.js

function knapsackDP(items, capacity) {
    const n = items.length;
    // dp[i][w] = i番目までで重さw以内のときの最大価値
    const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        const { w, v } = items[i - 1];
        for (let weight = 0; weight <= capacity; weight++) {
            if (w > weight) {
                // アイテムが入らない場合は前と同じ
                dp[i][weight] = dp[i - 1][weight];
            } else {
                // 入れない場合と入れた場合の最大値を取る
                dp[i][weight] = Math.max(
                    dp[i - 1][weight],              // 入れない
                    dp[i - 1][weight - w] + v       // 入れる
                );
            }
        }
    }
    return dp[n][capacity]; // 最大価値
}

9. Bound

Chapter 4 Data

1. Data Type

   1. Stack
   2. Queue
   3. Priority queue
   priorityQueue.js

   import TinyQueue from 'tinyqueue';
   const queue = new TinyQueue([], (a, b) => a.priority - b.priority);    
   queue.push({ value: 'A', priority: 2 });
   queue.push({ value: 'B', priority: 1 });    
   console.log(queue.pop()); // { value: 'B', priority: 1 }
   

   4. List
   5. Sorted list
   6. Map

   const map = new Map();
   map.set('apple', 100);
   

   7. Set

   const set = new Set([1, 2, 3, 2, 1]);
   console.log(set); // Set {1, 2, 3}
   

2. Data Structure

   1. Array
   2. Linked list
   3. Double linked list
   4. Tree
   5. Binary Search tree
   6. Self-balancing binary tree
   7. Binary heap
   8. Graph
   9. Hash function

Chapter 5 Algorithm

1. Sort

   1. Selection Sort
   2. Merge Sort
   3. Bubble Sort
   4. Quick Sort

2. Search

   1. Sequential Search
   2. Binary Search

3. Graph

   1. Depth First Search
   2. Breadth First Search
   3. Graph coloring
   4. Dijkstra algorithm
   5. Bidirectional Search
   6. Pagerank algorithm
   7. Operations research
   8. Linear programming problem

Chapter 6 Database

1. Relational model
   2. Schema migration
   3. Sql
   4. Transaction
2. No sql
3. Distributed database

Chapter 7 Computer

1. Architecture
   1. Memory
   2. CPU
   3. Processor
2. Compiler
3. Layer
   1. Resistor
   2. L1 cache
   3. L2 cache
   4. L3 cache
   5. RAM
   6. Disk

Chapter 8 Language