CS106B笔记

Recursion

  • 关于recursion,CS106B给出了一个很好的模板。
  • self-similar 问题用递归解决是一个良好方向。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    if (The problem is very simple) {
    Directly solve the problem.
    Return the solution.
    } else {
    Split the problem into one or more
    smaller problems with the same
    structure as the original.
    Solve each of those smaller problems.
    Combine the results to get the overall
    Solution.
    Return the overall solution.
    }
  • backtracking在课程和作业中也有体现 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    if (problem is sufficiently simple) {
     return whether the problem is solvable
    } else {
     for (each choice) {
     try out that choice
     if (that choice leads to success) {
     return success;
     } 
     }
     return failure;
    }
  • cs106b中对利用BFS的一个问题给出的思路 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    create an empty queue
    for (each water source at or below the water level) 
        {
            flood that square;
            add that square to the queue;
        }
    while (the queue is not empty) 
    {
      dequeue a position from the front of the queue;
      for (each square adjacent to the position in a cardinal direction) 
      {
       if (that square is at or below the water level and isn't yet flooded)        {
                 flood that square;
                 add that square to the queue;
            }
      }
    }
    # Sorting 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //selection sorting
    void selectionSort(Vector<int>& elems) {
     for (int index = 0; index < elems.size(); index++) {
     int smallestIndex = indexOfSmallest(elems, index);
     swap(elems[index], elems[smallestIndex]);
     }
    }

     int indexOfSmallest(const Vector<int>& elems, int startPoint) 
     {
     int smallestIndex = startPoint;
     for (int i = startPoint + 1; i < elems.size(); i++) {
     if (elems[i] < elems[smallestIndex]) {
     smallestIndex = i;
     }
     }
     return smallestIndex;
    }
1
2
3
4
5
6
7
8
9
//Insertion Sort
void insertionSort(Vector<int>& v) {
	for (int i = 0; i < v.size(); i++) {
		for (int j = i - 1; j >= 0; j--) {
			if (v[j] <= v[j + 1]) break;
		swap(v[j], v[j + 1]);
        }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//Merge Sort
void mergesort(Vector<int>& v) {
 if (v.size() <= 1) {   
 return;
 }
 //当输入量比较小的时候，此处可以换为Insertion Sort
 //if (v.size() <= kCutoffSize) 
 //insertionSort(v);
 int half = v.size() / 2;
 Vector<int> left = v.subList(0, half);
 Vector<int> right = v.subList(half);
 mergesort(left);
 mergesort(right);
 merge(left, right, v);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
二分
bool binarySearchRec(const Vector<int>& elems, int key,
 int low, int high) {

 if (low == high) return false;
 int mid = low + (high - low) / 2;
 if (key == elems[mid]) return true;
 if (key < elems[mid]) {
 return binarySearchRec(elems, key, low, mid);
 } else {
 return binarySearchRec(elems, key, mid + 1, high);
 }
}
bool binarySearch(const Vector<int>& elems, int key) {
 return binarySearchRec(elems, key, 0, elems.size());

Class

  • Create a header file (typically suffixed with .h) describing what operations the class can perform and what internal state it needs.
  • Create an implementation file (typically suffixed with .cpp) that contains the implementation of the class.
  • Clients of the class can then include the header file to use the class. 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //Example
    #include "vector.h"
    class RandomBag {
    public:
     void add(int value);
     int removeRandom();
     bool isEmpty() const;
     int size() const;
    private:
     Vector<int> elems;
    };
  • 主要部分
  • Member variables (What subvariables make up this new variable type?)
    • These are the variables stored within the classUsually not accessible outside the class implementation
  • Member functions (What functions can you call on a variable of this type?)
    • Functions you can call on the object。
    • Known as methods
  • Constructor (What happens when you make a new instance of this type?)
    • Gets called when you create the object
    • Sets the initial state of each new object

Dynamic Memory Allocation

  • 概念性的如stack and heap

  • Types like Vector, Map, Set, etc. that store a variable number of items need space to store those elements.

  • When you use those types as a client, they just “work” and somehow figure out where to store things. You as the end user don’t see how.

  • Internally, those types use a technique called dynamic memory allocation to get space in RAM where they can put their elements. 

    1
    2
    3
    string* ptr = new string[3];
    //Anything created with new[] persists until explicitly cleaned up.
    delete[] ptr;

  • 使用C++自身的variables 和parameters 会自动处理内存分配和释放

  • 但是使用new[]的不会，需要手动处理，防止内存泄漏，使用delete[] # Hash 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    int nameHash(string first, string last){
     /* This hashing scheme needs two prime numbers, a large prime and a small
     * prime. These numbers were chosen because their product is less than
     * 2^31 - kLargePrime - 1.
     */
     static const int kLargePrime = 16908799;
     static const int kSmallPrime = 127;
     int hashVal = 0;
     /* Iterate across all the characters in the first name, then the last
     * name, updating the hash at each step.
     */
     for (char ch: first + last) {
     /* Convert the input character to lower case. The numeric values of
     * lower-case letters are always less than 127.
     */
     ch = tolower(ch);
     hashVal = (kSmallPrime * hashVal + ch) % kLargePrime;
     }
     return hashVal;
    }

  • This is a hash function. It’s a type of function somesmart math and CS people came up with.

  • problem: 不同输入通过哈希函数可能有相同输出

  • Application：Map Set 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //Linear Probing
    - To check if an element exists in the table:
      Compute the hash code of the element. 
      Jump to that location in the table. 
      Scan forward – wrapping around if necessary – until the item or an empty slot is found. 
    - To insert an element into the table: 
      If the item already exists, do nothing.
      Otherwise, jump to the slot given by the hash code of the element. Walk forward – wrapping around if necessary – until a blank spot or tombstone slot is found. Then, put the item there.
    - To remove an element from the table:
      Jump to the slot given by the hash code of the element.
      Walk forward – wrapping around if necessary – until the item or and   empty slot is found. If the item is found, replace it with a tombstone.

1
2
3
4
5
6
7
8
9
10
//Robin Hood Hashing
- To check if an element exists in the table:
Jump to the spot in the table given by the element’s hash code.
Scan forward – wrapping around if necessary – keeping track of how many steps you’ve taken. Stop when you find the item, you find a blank slot, or you find a filled slot closer to home than the number of steps you’ve taken.
- To insert an element into the table:
If the element is already in the table, do nothing.
Jump to the table slot given by the element’s hash code. Scan forward – wrapping around if necessary – keeping track of the number of steps taken. If you find an empty slot, place the element there. Otherwise, if the current slot is full and closer to home than the element you’re inserting, place the item to insert there, displacing the element that was at that spot, and continue the insertion as if you were inserting the displaced element.
- To remove an element from the table:
Jump to the slot given by the hash code of the element.
Walk forward – wrapping around if necessary – until the item or an empty slot is found. If the item is found, remove it. Then, keep moving forward – wrapping around as necessary – moving elements backward in the table one slot until an empty slot or an item in its home position is found

Linked Lists

1
2
3
4
5
6
7
8
9
10
11
12
struct Node {
string Date;
Node* next;
};
Node* list = new Node;
list->Date = "pudu!";
/*
- If you allocate memory using the new[] operator (e.g. new int[137]), you have to free it using the delete[]operator.
delete[] ptr;
- If you allocate memory using the new operator , you have to free it using the deleteoperator.
delete ptr;
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void prependTo(Node*& list, const string& value) {
 Node* prev = new Node;
 prev->Date = value;
 prev->next = list;
 list = prev;
}
//Newend
 Node* newEnd = new Node;
 newEnd->data = target;
 newEnd->next = nullptr;
 cur->next = newEnd;

// insert 
 Node* cur = head;
 while (cur != nullptr && cur->data != target ) {
 cur = cur->next;
 }
 Node* toInsert = new Node;
 toInsert->data = value;
 toInsert->next = cur->next;
 cur->next = toInsert;

// Delete
  void deleteNode(Node*& list, int value) {
    // traverse to node before value to delete
    Node* prev = nullptr;
    Node* cur = list;
    while (cur != nullptr && cur->data != value) {
        prev = cur;
        cur = cur->next;
    }
    // delete and rewire
    Node* next = cur->next;
    delete cur;
    if (prev != nullptr) {  // added this
        prev->next = next;
    } else {
        list = next;        // and this
    }
 }
1
2
3
4
//Doubly-Linked Lists
Cell* list = /* first cell */;
list = list->next; 
list = list->prev;

Tree

  • BST
  1. Binary tree (each node has 0, 1, or 2 children)
  2. For a node with value X:
    1. All nodes in its left subtree must be less than X
    2. All nodes in its right subtree must be greater than X 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      struct Node { 
       Type value; 
       Node* left; // Smaller values
       Node* right; // Bigger values 
      };
      /*
      • Pre-order traversal
      • In-order traversal 
      • Post-order traversal
      */

      // Free tree
      void freeTree(TreeNode* node) {
       if (node == nullptr) {
       return;
       }
       freeTree(node->left);
       freeTree(node->right);
       delete node;
       }

      //Balance
       • A BST is balanced if its height is O(log n), where n is the number of nodes in the tree
       • Theorem: If you start with an empty tree and add in random values, then with high probability the tree is balanced
       • A self-balancing BST reshapes itself on insertions and deletions to 
      stay balanced (how to do this is beyond the scope of this class)


Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// BFS
bfs-from(node v) {
 make a queue of nodes, initially seeded with v.
 
 while the queue isn't empty:
 dequeue a node curr.
 process the node curr.
 
 for each node adjacent to curr:
 if that node has never been enqueued:
 enqueue that node.

//DFS
dfs-from(node v) {
 make a stack of nodes, initially seeded with v.
 
 while the stack isn't empty:
 pop a node curr.
 process the node curr.
 
 for each node adjacent to curr:
 if that node has never been pushed:
 push that node.
 }

//Dijkstra's Algorithm
 1. Of the unseen nodes, find the node that 
currently has the shortest distance from the 
start
 2. Look at this node's neighbors, and update the 
total distance to the neighbors based on their 
distance and the distance already to this node.
 3. If the node visited is the destination, stop
 4. Repeat from step 1

//A* Algorithm
 • Finds the shortest weighted path from one node to another
 • Uses external information about the graph
 • Heuristic: estimates the cost of the cheapest path to the goal
 • Should always underestimate the distance to the goal, because if it 
overestimates, it could find a non-optimal solution
 • If the distance to the destination is closer, weight the nodes in that 
direction to be preferable
 • priority(u) = weight(s, u) + heuristic(u, d)



碎碎念

  • 本人学习cs的路程是先上了CS50,然后开始的CS106B。从个人体验上来讲，CS106B的作业质量很高，比起cs50难度跨越也更大。

  • 一定一定要看对应作业的Slide，我学的是2022年的，2022年的作业许多内容都可以从Slide中找到对应的提示，其他年的Slide也可以看看，相当不错。

  • 在课程学习的个人体会上，结合作业相关的提示，编写一个看起来仿佛可以的伪代码似乎并不是一个困难的事情，但伪代码的翻译相当的困难，还是代码写少了。

  • 发现个人的问题是，一是看的，写的代码太少了，经常性的卡在一些细节性问题，或用一种很傻的方法去处理。二是编写的伪代码的架构问题，经常性的不足以把题目拆分清楚，解决好。

  • 后续学习需要针对这两方面需要解决。