# Book \: C++ Data Structure & Algorithm Design
> * Github Repository
> https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
*This note is based on **C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications***. This note will only include some code snippets and additional materials. Please refer to the book or the github repository for detail.
*Algorithm mentioned in this book \(Activities\) will be implemented and **parallized** if possible*
:::success
:bulb: **Advanced Analysis of Algorithms**
https://hackmd.io/@Erebustsai/SyfT89rsC
:::
# Data Structures Provide by C++
:::success
:bulb: **Limitations of C-style Arrays**
* Memory allocation and deallocation is manually controlled. Therefore, the program need to make sure in every possible exit, the memory should be deallocated.
* `operator[]` will not check for boundary. Invalid access or segmentation fault might occur.
* Deep Copy will need to be implemented manually.
However, using plain C-style array is the best way to interact with HPC system guest devices since support for C++ container might not be implemented. On the ohter hand, using **wraper from compute libraries** such as cuBLAS, Eigen, ViennaCL will releave programmer from manual controling memory.
:::
:::info
:bulb: **C++ Reference**
https://en.cppreference.com/w/
:::
:::success
:bulb: **C++11 新的容器：array、沒排序的 set 與 map**
https://viml.nchc.org.tw/containers-in-cpp-11/
:::
## **std::array**
1. `Operator[]` will work as C-style array without boundary check and `at(index)` throw an exception if the argument is not valid.
2. Passing `std::array` will be similar as built-in data type which means pass by value, pass by reference and with const will work.
3. One caveat is that the size of the array is part of the data type. Therefore, a template can be used to have a arbituary data size.
4. Another caveat is that the default behavior is deep-copy when passing a container like this as a function parameter.
:::info
:bulb: **C++ Variadic Template & `common_type`**
*C++ Variadic Template*
Pass in arbitrary number of variables can with different types. However, parameter pack need to be expanded.
https://tjsw.medium.com/%E6%BD%AE-c-variadic-template-parameter-pack-d76c0a4ffcdd
`common_type` in `<type_traits>` is used to return a type that all the type in the type list can be convert to. In the book **exercise 2**, the common type for all the variables is `float`.
https://blog.csdn.net/YX___/article/details/78076168
:::
## **std::vector**
1. `std::array` is always use in stack memory since the size is determined at compiler time.
2. `std::vector` is a variable length array and have usually *O\(1\)* insert time. \(Only when capacity not enough will be *O\(n\)* a `reserve` member function can be used to allocat a big enough space base on usage\)
:::info
:bulb: **`emplace` prefix member function**
https://viml.nchc.org.tw/cpp11-emplace/
`emplace` can be used to prevent creating a temperary object before put into the container.
:::
## **std::forward_list**
:::info
:information_source: **Forward List in C++ STL**
https://www.geeksforgeeks.org/forward-list-c-set-1-introduction-important-functions/
:::
1. Deletion and insertion in the middle of the data structure are *O\(1\)*. However, no contiguous accessing advantage available.
2. No `back` and `push_back` available only `front` and `push_front`
3. `insert_after` is used than `insert`
4. `std::sort` can be used to sort array-related structures but linked list-based structure use `sort` member function
:::info
:bulb: `std::less` and `std::greater`
https://blog.csdn.net/sandalphon4869/article/details/105419706
These class with `operator()` has `return x < y`. Therefore, we just need to define `operator<`
:::
## Iterators
### Iterator traversal
:::info
:information_source: **`std::advance`**
> Reference \:
> * `std::next` vs `std::advance` in C++
> https://www.geeksforgeeks.org/stdnext-vs-stdadvance-in-cpp/
Notice that add or minus on a iterator will only work on iterator with random access support. Therefore, `std::vector` will work but `std::forward_list` will not work.
The biggest different between `std::next` \& `std::advance` is that `std::next` will return an iterator when `std::advance` do not.
:::
### Iterator Invalidation
Insertion, deletion, `push_back`, etc, might invalidate an iterator. For example, a `std::vector`, the iterator might be invalid when `push_back` is called because the entire container might be moved to other memory location and accessing the iterator after it might causing `undefined behavior`. However, for a `std::list`, a insertion or `push_back` will not cause an iterator to be invalid because of the nature of link-list structure.
## **std::deque**
1. Provide `push_front`, `pop_front` with *O\(1\)*
2. Insertion and deletion in the middle take maximum of N / 2 steps
3. Cost more memory than other containers and maintain multiple chunks of contiguous memory space.
## **Container Adaptors**
`stack`, `queue` and `priority_queue` ... These containers doesn't provide more effeciency but increase readability and reduce human error.
An example of `priority_queue` can be found in another post **General Performance Engineering** \(https://hackmd.io/@Erebustsai/HJ4PO0bV6\). This wrap around a *heap* sturcture and provide a quick access to maximum or minimum element.
:::info
:information_source: **STL Performance Benchmarks**
* STL system performance benchmark Repo
https://github.com/jupidity/STL-system-performance-benchmark/tree/master
* `std::forward_list::sort()` in C++ STL
https://www.geeksforgeeks.org/stdforward_listsort-c-stl/
* `std::list::sort()` vs `std::sort()`
https://www.reddit.com/r/cpp/comments/j3fjh8/comment/g7bvx7d/?utm_source=share&utm_medium=web3x&utm_name=web3xcss&utm_term=1&utm_content=share_button
* benchmarking `std::vector` and `std::list` sorting performance
https://cppbenchmarks.wordpress.com/2020/08/25/benchmarking-stdvector-and-stdlist-sorting-performance/
:::
:::info
:information_source: `<random>`
https://blog.gtwang.org/programming/cpp-random-number-generator-and-probability-distribution-tutorial/
:::
# Trees, Heaps, and Graphs
## Non-Linear Problem
* Hierarchical Problems \: Problem with hierarchy in data structure
* Cyclic Dependencies \: Graphs
## Tree
```cpp
static org_tree create_org_structure(const std::string& pos)
{
org_tree tree;
tree.root = new node{ pos, NULL, NULL };
return tree;
}
```
***Traversing Trees***
> Reference \:
> * In-order Tree Traversal with Stack \& Loop
> https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
The example tree in this section has two node \(left, right node\).
* Preorder traversal \: current node -> left child -> right child
```cpp
static void preOrder(node* start)
{
if(!start)
return;
std::cout << start->position << ", ";
preOrder(start->first);
preOrder(start->second);
}
```
* In-order traversal \: left node -> current node -> right node
* Post-order traversal \: left node -> right node -> current node
:::info
:information_source: **Traversing Trees Additional Material**
https://alrightchiu.github.io/SecondRound/binary-tree-traversalxun-fang.html
:::
## Variant of Trees
***Binary Search Tree \(BST\)***
* Value of the parent node >= value of the left child
* Value of the parent node <= value of the right child
**Find Element**
Simply traverse the tree up to down.
**Insert Element**
Simpy traverse the tree up to down till no leaf found and insert the element accrodingly.
**Delete Element**
Find the successor which is the next biggest number \[smallest in the bigger subtree\] by traversing to the left most node of the right subtree and move it.
:::info
:information_source: **Implementation Provide by the Book**
https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson2/Exercise09/Exercise9.cpp
:::
**In-order traversal**
Applied on BST can get a sorted values in ascending order.
**Balancing Tree**
To optimize the BST, we need to optimize the height of the tree.
:::success
:bulb: **Not Possible Multi-threaded Insertion of BST**
The following post shows that it's not possible to have a BST insertion in parallel naively.
* Stackoverflow Post
https://stackoverflow.com/a/40231148
The following is a paper shows how to build a parallel Binary Search Tree.
* Parallel Binary Search Tree Construction Inspired by Thread-Level Speculation \(2022\)
https://ieeexplore.ieee.org/document/10053324
:::
***Heap***
*Please refer to the book for better understanding.*
A **complete tree** \(in Page 81\) store in an array
> If the parent is the ith node, its children will always be 2\*i \+ 1 and 2\*i \+ 2 indices. And similarly, we can get the parent node for the ith child node by using \(i – 1\) \/ 2.
Notice that it start with 0
**Max, Min Heap \:** Fix the maximum or minimum value of data in the tree at root. Therefore, a node's childs will only be **smaller** than parent node in max heap and otherwise for min heap.
**Insertion & Deletion \:** When accessing or deleting the tree, a swap is required for maintaining the heap property. To implement the insertion, insert the node at one of the leaf and perform swap till heap property is restored; to implement the deletion, **the deletion can only happened on root** so we swap the root and the last element and preceed swap till heap property restored.
:::success
:bulb: **`std::make_heap`**
* **c++ make_heap(), pop_heap()函數**
https://blog.csdn.net/u012604810/article/details/80912794
* **Heap in C++ STL geeksforgeeks**
https://www.geeksforgeeks.org/cpp-stl-heap/
:::
:::info
:information_source: **Heap in C++ STL : priority_queue**
**cppreference.com**
https://en.cppreference.com/w/cpp/container/priority_queue
:::
## Example \: Streaming Median
**Problem Discreption from the Book**
> Imagine that some source is giving us data one element at a time continuously (a stream of data). We need to find the median of the elements that have been received up until now after receiving each and every element.
:::info
:information_source: **Extra Material for Streaming Median**
https://stackoverflow.com/questions/10657503/find-running-median-from-a-stream-of-integers
:::
**Solution**
> We'll store the data among two heaps – one min heap and one max heap. We'll store the smaller, first half of the elements in a max heap, and the larger, or the other half, in a min heap.
**Detail Solution**
* Find Median from Data Stream
https://home.gamer.com.tw/artwork.php?sn=5312685
* DSA Problem : Find Median from Data Stream
https://medium.com/@ankitviddya/dsa-problem-find-median-from-data-stream-8a6d92743d7c
* Data Structures: Solve 'Find the Running Median' Using Heaps
https://www.youtube.com/watch?v=VmogG01IjYc
# Hash Tables and Bloom Filter
## Motivation
Lookup is checking if an element is contianed in a contianer or finding a corresponding value for a key. Simply using linear search with O\(N\) complexity is slow and using a height-balanced tree similar to BST can reduce the complexity to O\(logN\). However, we can reduce complexity to constant time with **hash table**.
## Hash Table
The idea behind hashing is try to represent all the value with a possibly unique key and use the key to retrieve the corresponding value.
How to solve Collision \[*Happend when there are multiple input have the same hash value*\]
:::info
:information_source: **Load Factor**
A number indicated the ratio of `number or keys` and `size of hash table`
`load_factor = number_of_keys/size_of_hash_table`
:::
* **Chaining** \: Store a linked list for each index and store all collision elements in the link list. The book suggest that using linked list because it can enable fast removal of elements.
* **Open Addressing** \: \[Reference \: https://ithelp.ithome.com.tw/articles/10279018\] This method require total number of key is smaller than the total number of slots. When collision happened, a probe will be used to check is the slot is occupied and a second hash function will be provided to determine the elemnts slot. ***Linear Probing*** if the space is occupied, compute *hash\(x + 1\)* and continuously adding 1 tell reaching a empty space.
* **Perfect \(Cuckoo\) Hashing** \: \[Reference \: https://medium.com/@kewei.train/cuckoo-hashing-95e037f4f024\] Having two or more hash tables and hash functions and insert elements by pushing out old elements to another table. Please refer to the book for better understanding.
## Cuckoo Hashing Implementation
**Insertions**
* Insert A with location occupied by B.
* Move B to second hash table where location occupied by C.
* Move C to first hash table.
*Insertion happened until all the element find its place in these two hash tables and it will goes recursively.*
> Reference Book Page 117
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
In cuckoo hashing, we keep two hash tables of the same size, each with their own unique hash function.
* Any element can be present in any of the two hash tables.
* Any element can be moved to another location in the future, even after insertion.
We can still increase the degree by increasing the number of possible locations for any element so that we gain better results and have less frequent rehashing.
**Cycle**
* Insert A with location occupied by B.
* Move B to second hash table where location occupied by C.
* Move C to first hash table where location occupied by D.
* Moving D finally end up moving to location occupied by A.
* Infinite loop.
**Cycle Solution**
> To address this, once we've identified the cycle, we need to rehash everything with new hash functions. The hash tables that were created with new hash functions may still have the same problems, so we may have to rehash and try out different hash functions.
:::success
:bulb: **Wikipedia Page**
https://en.wikipedia.org/wiki/Cuckoo_hashing
:::
:::success
:hammer: **A bug in code repository**
> https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson3/Exercise15/Exercise15.cpp
The following snippet start at line 91
```cpp=
int hash = hash2(key);
if (data2[hash] == -1)
{
std::cout << "Inserted key " << key << " in table " << table << std::endl;
data2[hash] = key;
}
else
{
int old = data2[hash];
data2[hash] = key;
std::cout << "Inserted key " << key << " in table " << table << " by replacing " << old << std::endl;
// insert_impl(old, cnt + 1, 2); // wrong
insert_impl(old, cnt + 1, 1);
}
```
:::
**Implementation Consideration**
> Reference \: https://medium.com/@kewei.train/cuckoo-hashing-95e037f4f024
>
> 在insertion fail發生的時候, capacity如何? 很不幸, 在論文上提到, 當table是一維的時候, insertion fail發生時, 空間利用率大概也就是50%, 60%, 跟其他的hash演算法差不多. 因此一個簡單的變形是: 讓一個bucket一次擁有4個slot, 如果4個slot還沒被填滿之前是不會有key被踢出的. 論文指出如果是4個slot, capacity可以到90%以上.
:::info
:bulb: **Hash Table in STL**
* **C++ std::unordered_set 用法與範例**
https://shengyu7697.github.io/std-unordered_set/
* **C++ set與map、unordered_map、unordered_set與雜湊表**
https://blog.csdn.net/qq_30815237/article/details/91047041
:::
## Bloom Filter
*TODO \: Skip*
> Reference \: https://medium.com/@Kadai/資料結構大便當-bloom-filter-58b0320a346d
Bloom filter only guarantees that there won't be any **false negatives**, but there may be **false positives**.
# Divide \& Conquer
**My Other Post**
* https://hackmd.io/@Erebustsai/SyfT89rsC
* https://hackmd.io/@Erebustsai/HJ4PO0bV6
* https://hackmd.io/@Erebustsai/S1sguFsJkg
## Algorithm Complexity Chart
The above image is provided by the book in page 144, which showes the trend of different complexity growth. Notice that complexity of an algorithm is not completely accurate becuase the N in big-o in reality might not have same scale and different instruction will take different time to work.
## Example \: Binary Search
* Step \#1 \: Divide input array into two halves by finding the `middle_index`.
* Step \#2 \: Compare value in `middle_index` with the `key` in search. If found, exit function.
* Step \#3 \: Compare value witth one in `middle_index`. If the key is smaller update `right_index` to `middel_index - 1`; If the key is bigger update `left_index` to `middle_index + 1`.
* Step \#4 \: With the updated indexes, repeat to step \#1
:::success
:bulb: **Implementation Tips**
1. For iterative version of binary search, `while(left <= right)` can be the condition for the loop.
2. > Note that our implementation of binary search uses **iterators** and the C++ Standard Library functions such as `std::distance()` and `std::advance()`. This is considered good practice in modern C++ since it helps keep our code agnostic of the underlying data type and safe from index out-of-bounds errors.
:::
:::info
:information_source: **Ternary Search**
Simplily speaking, just a three way search that cut out three parts rather than two parts. However, it will take more comparisons in each recursion\/iteration as described in the second reference in the following references.
* Ternary Search
https://www.geeksforgeeks.org/ternary-search/
* Why is Binary Search preferred over Ternary Search?
https://www.geeksforgeeks.org/binary-search-preferred-ternary-search/
:::
## Divide-and-Conquer Approach
> * **Divide** \: Take the original problem and divide it into parts so that the same problem needs to be solved for each part.
> * **Conquer** \: Solve the problem for each part.
> * **Combine** \: Take the solutions for the different parts and combine them into a solution for the original problem.
## Sorting with Divide-and-Conquer
**Merge Sort**
The divide nature of the Merge Sort makes it perfect for distribution task such as multi thread \(CPU\) and many thread \(GPU\) systems.
* Merge Sort can be parallized. See https://github.com/Chen-KaiTsai/PerformanceEngineering_repo/blob/main/OpenMP_Algorithms/MergeSort/Merge_sort.cpp
* Merge Sort is part of the multi-GPU sorting. See https://hackmd.io/9NN76OIXSCmPmEkX4IJt_w\#Paper\--Evaluating\-Multi\-GPU\-Sorting\-with\-Modern\-Interconnects
**Partial Sort or Quick Select**
See my other post
https://hackmd.io/9tGyeFoYRVuArznahp07Iw?view#Find-the-ith-Smallest-Element-of-a-Set
Github Repo
https://github.com/Chen-KaiTsai/GPGPU_CUDA/blob/main/ImageFilter/filter.cu
**Linear Time Selection**
See my other post
https://hackmd.io/9tGyeFoYRVuArznahp07Iw?view#Find-the-ith-Smallest-Element-of-a-Set
TODO
## C++ Standard Library Tools for Divide and Conquer
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications ***Page 177***
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
**Binary Search Related**
* `std::binary_search()` \: Search for a *single element* in a container using binary search.
* `std::search()` \: Search for a range of elements in a container.
:::info
:information_source: **Binary Search functions in C++ STL**
https://www.geeksforgeeks.org/binary-search-functions-in-c-stl-binary_search-lower_bound-and-upper_bound/
:::
* `std::upper_bound()` \: Returns an iterator to the first element in a container that is graeter than given value.
* `std::lower_bound()` \: Returns an iterator to the first element in a container that is not less than given value.
:::info
:information_source: **求比 k 大的最小值 lower_bound/upper_bound**
https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FHk8wnUcWB
:::
**Partition**
* `std::partition()` \: With a custom operator, reordering the elements in a container by applied the condition (if true, it is placed before all the elements for which it returns false). \{https://cplusplus.com/reference/algorithm/partition/\}
* `std::partition_copy()` \: Applies partition but return two separate arrays as results.
* `std::is_partitioned()` \: Test whether range is partitioned
* `std::stable_partition()` \: Rearranges the elements in the range \[first,last\)\, in such a way that all the elements for which pred returns true precede all those for which it returns false\, and, unlike function partition\, the relative order of elements within each group is preserved. **This is generally implemented using an internal temporary buffer**. \[https://cplusplus.com/reference/algorithm/stable_partition/\]
**Sorting**
* `std::sort()` \: Sorting. \[https://cplusplus.com/reference/algorithm/sort/\]
* `std::stable_sort()` \: \[https://cplusplus.com/reference/algorithm/stable_sort/\]
* `std::partial_sort()` \: \[https://cplusplus.com/reference/algorithm/partial_sort/\]
* `std::merge()` \: Can be used to merge two sorted array \[https://cplusplus.com/reference/algorithm/merge/\]
:::info
:information_source: **【C++】sort\(\)、stable_sort\(\)和partial_sort\(\)排序函數詳解**
https://blog.csdn.net/qq_22734027/article/details/134180341
:::
**Others**
* `std::nth_element` \: Rearrange the array so that the element at the nth position is the one which should be at that position if we sort the list.\[https://www.geeksforgeeks.org/stdnth_element-in-cpp/\]
* `std::accumulate` \: \[https://cplusplus.com/reference/numeric/accumulate/\]
* `std::transform` \: Take a function and a container as parameters and applied function on each element in the container; take two containers and reduce element by element into destination container. \[https://cplusplus.com/reference/algorithm/transform/\]
:::info
:information_source: **Header `<functional>`**
> Function objects are objects specifically designed to be used with a syntax similar to that of functions. In C++, this is achieved by defining member function operator() in their class. ***They are typically used as arguments to functions, such as predicates or comparison functions passed to standard algorithms***.
https://cplusplus.com/reference/functional/
:::
> Reference
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications ***Page 182***
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
>
> `std::transform()` does not change the original vector and instead returns the result in a separate vector, while `std::for_each()` modifies the input vector. Another difference between the two is that `std::transform()` does not guarantee that the input function, `f`, will be applied from the first to the last element of the container; that is, the order of function application does not necessarily match the order of elements. Starting with C++ 17, `std::transform()` also supports native parallelization by accepting **ExecutionPolicy** as the first argument.
# Greedy Algorihtms
> the simplicity of the greedy approach often makes it an excellent tool for 'first attack', by which we can understand the properties and behavior of the underlying problem, which can then be solved using other, more complex approaches
## Shortest Job First
**Problem Description**
> Say you are standing in a queue at your bank. It's a busy day and there are N people in the queue, but the bank has only one counter open \(it's also a really bad day\!\). Let's assume that it takes a person, pi, the amount of time of ai to get served at the counter. Since the people in the queue are quite rational, everyone agrees to reorder their places in the queue so that the average waiting time for everyone in the queue is minimized.
**Similar Problem \: Participate Events**
Finish or participate as many events as possible before a deadline. In this case chose the event in order of which finished earliest.
**The Knapsack Problem\(s\)**
> Suppose you are given a set of objects, O \= \{O1, O2, …, On\}, with each having a certain weight, Wi, and a value of Vi. You are also given a bag \(or a knapsack\) that can carry only a total weight of T units.
:::success
A normal K-napsack Problem is an NP-Complete Problem. There is no polynomial-time solution to this problem and testing all possible combination will be the only \'*correct*\' solution.
:::
**The Fractional Knapsack Problem**
> we are now allowed to break each object into as many parts as we need
**Solution**
> the fractional knapsack problem has a simple solution\: order the elements according to their value per weight ratio and \'greedily\' choose as many objects as possible with the maximum ratio
## Requirement for Greedy Algorithms
* Optimal Substructure \: When an optimal solution to a given problem, P, is composed of the optimal solutions to its subproblems, then P is said to have an optimal substructure.
* Greedy Choice \: When an optimal solution to a given problem, P, can be reached by selecting the locally optimal solution on each iteration, P is said to have the greedy choice property.
## Minimum Spanning Tree \: Kruskal's Algorithm
> "Given a graph, G = < V, E >, where V is the set of vertices and E is the set of edges, each associated with an edge weight, find a tree, T, that spans all the vertices in V and has the minimum total weight."
:::success
:bulb: **My Other Post**
https://hackmd.io/9tGyeFoYRVuArznahp07Iw?view#Minimum-Spanning-Trees
:::
**Step**
1. Add all the edges of `G` in a min-heap, `H`
2. From `H`, pop an edge, `e`. Naturally, `e` has the minimum cost among all edges in `H`.
3. If both vertices of `e` are already in `T`, this means that adding `e` world create a cycle in `T`. Therefore, discard `e` and go to step 2. Otherwise, proceed to the next step.
4. Insert `e` in the minimum spanning tree, `T`.
**Proving Greedy Applies**
* **Optimal Substructure** \:
**Proving by using contradiction.**
1. A minimum spanning tree `T`, over the vertices of graph `G`. Removing any edge `e` from `T` separate `T` into smaller trees, `T1`, `T2`.
2. We assume that MST problem does not exhibit optimal substructure so there will be a spanning tree with a lesser total weight over the vertices of `T1`. Adding back the removed edge `e` and `T2` back to `T1` to create a new tree as `T'`.
3. In this case, tree `T'` will have smaller tatal weight than the original tree `T` and this contradicts our original assumption that `T` is a MST.
* **Greedy Choice** \:
This is much intuitive than the above one. If there is a edge that connect `v` to other vertices with minimum weight but not included in `T`. There must be a spanning tree with smaller total weight and this contradict the original assumption that `T` is a MST.
## Disjoint-Set Data Structure
:::info
:information_source: **Reference Tutorials**
* **Ch21 並查集 - Disjoint Set**
https://hackmd.io/@CLKO/rkRVS_o-4?type=view#Ch21-%E4%B8%A6%E6%9F%A5%E9%9B%86
* **Union-Find / Disjoint-Set – 陪你刷題**
https://haogroot.com/2021/01/29/union_find-leetcode/
:::
A set of trees of elements consist of
* a **numerical ID**
* a **rank** \: Size of the tree.
* a **pointer\/index** to its parent
**Operations**
* `find` operation on a tree returns the root element of that tree by following the parent pointers for each element until the root of the tree is reached.
* `union` operation merges two trees using `find` to determine tree roots rank and set the root with higher rank as the parent of the root with a lower rank.
**Using Disjoint-Set on Kruskal\'s Algorithm**
> If the union operation succeeds in merging the two trees, then the edge is added to the MST\; otherwise, the edge can safely be discarded as it would introduce a cycle in the MST.
**Implementation**
https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson5/Exercise26/kruskal.cpp
# Graph Algorithms I
> What makes graphs useful is that they are the general representation of relationships.
In this section, graphs are restricted to weighted and directed type. Therefore, these following algorithms are support for *weighted and directed graph*.
## The Graph Traversal Problem
:::success
***Visiting all vertices with a starting vertex.***
:::
**Breadth-First Search**
> A \"breadth-first\" search or breadth-first traversal of the graph starts by adding the starting vertex to **a frontier that consists of the set of previously visited vertices** and then iteratively exploring the vertices adjacent to the current frontier.
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications. **Page 248**
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
**Implementation**
https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson6/Exercise28/bfs.cpp
```cpp
auto outgoing_edges(size_t v) const
{
std::vector<Edge<T>> edges_from_v;
for (auto& e : edge_list)
{
if (e.src == v)
edges_from_v.emplace_back(e);
}
return edges_from_v;
}
```
```cpp
while (!queue.empty())
{
auto current_vertex = queue.front();
queue.pop();
// If the current vertex hasn't been visited in the past
if (visited.find(current_vertex) == visited.end())
{
visited.insert(current_vertex);
visit_order.push_back(current_vertex);
for (auto e : G.outgoing_edges(current_vertex))
queue.push(e.dest);
}
}
```
The above code snippet shows the main mechanism of this BFS implementation. Notice that when checking a graphs `outgoing_edges` will traverse the entire `edge_list` and return a `vector` with only edges out from the selected vertex `v`. Therefore, everytime visiting a vertex will cost O\(N\) complexity with `N = num_edges`.
Using `map` instead of `vector` might be a better solution. ***TODO : Implementation***
**Depth-First Search**
**Back Tracking Nature**
> DFS starts from the source vertex and iteratively visits vertices as far away as possible along a certain path, returning to earlier vertices to explore vertices along a different path in the graph.
> DFS starts from the source vertex and iteratively visits vertices as far away as possible along a certain path, returning to earlier vertices to explore vertices along a different path in the graph.
**Implementation**
https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson6/Exercise29/dfs.cpp
## Prim's MST Algorithm
Similar to BFS but when choosing visited vertex, the vertex with lowest cost edge from the frontier is picked.
**Using Label**
A label is used to describe the current distance between the frontier \(In the beginning only the first vertex\) and a certain vertex.
**Steps**
1. Initialize the labels on all the vertices to infinity except the first visited vertex \(starting vertex\) to 0. Notice that the distance of a vertex to itself is 0 and without `visiting`, all the other vertices have infinity distance.
2. Add the starting vertex to a min-heap `H`.
3. Pop a vertex, `U`, from `H`. Since we are using min-heap, the vertex must have minimum distance from the starting vertex \(frontier\).
4. For all vertices, `V`, adjacent to `U`, if `label of V > edge weight (U, V)`, set the label of `V = edge weight (U, V)`. This step is called `visiting` a vertex `U`. Remember to add all `V` into the `H` as BFS do.
5. Go to step 2.
**Implementation**
https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson6/Exercise30/prim.cpp
**Summary**
> The time complexity of , Prim's algorithm is O\(E log V\) when using a binary min-heap and an adjacency list for storing the MST, which can be improved to O\(E + V log V\) when using a type of heap called the \"Fibonacci min-heap.\"
## Dijkstra's Shortest Path Algorithm
> Given a directed graph, `G - < V, E >` where `V` is the set of vertices and `E` is the set of edges, each of which is associated with an edge weight, a source vertex, and a destination vertex, find a minimum-cost path from a source to a destination.
> Dijkstra's algorithm works for graphs with **non-negative edge weights** and is only a slight modification of Prim's MST algorithm.
1. Updating labels to the total distance of the vertex from the source. It means that adding the current vertex label with the outgoing vertex edge weights.
2. Terminate when destination reached.
# Graph Algorithms II
## Bellman-Ford Algorithm
> Reference \:
> * 最短路徑 (Bellman-Ford 演算法)
> https://ithelp.ithome.com.tw/m/articles/10209748
Bellman-Ford have higher cost than Dijkstra's algorithm; however, with the ability to handle negatvie weights.
*Code is easier than description to understand.*
**Book Example of Graph with Negative Weights that Dijkstra's Algorithm Misinterpret**
**Implementation**
https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson7/Exercise32/Exercise32.cpp
Notice that the program use `INT_MAX` from `<climit>`. The `UNKOWN` is set to `INT_MAX`. This is required since the algorithm isn't check for any not visited or connected nodes only use `<`. Therefore, the unvisited nodes should be automatically set to the max value of the edge data type.
Additionally, we don't need to consider a positive cycle for this algorithms nature.
### Negative Weight Cycles
> a negative weight cycle or a cycle in the graph where the combined edge weights produce a negative sum.
A graph without negative weight cycle applied with Bellmen-Ford can be determined within `|V - 1|` iteration through all vertices. A negative weight cycle can only be found if there exist a shorter path after `|V - 1|` iterations.
**Solution**
The solution to this is to do an additional loop in the `Vectice` loop by checking through all the edges ***same as the inner loop***. If a shorter path found \(trigger an update to the table\), a negative weight cycle is found.
:::success
The iteration in the above section is the outer for loop. Every iteration mentioned above require another for loop that loop through all the edges.
:::
## Johnson's Algorithm
> Reference \:
> * Johnson’s Algorithm
> https://medium.com/algorithm-solving/johnsons-algorithm-c461506fccae
Combine both Dijkstra's Algorithm and Bellmen-Ford Algorithm to retrieve *the shortest paths between every pair of vertices in a graph*.
Johnson's algorithm simply adds an additional weight to all the edges which will make all the edges non-negative.
:::success
> The first step in Johnson's algorithm is to add a new 'dummy' vertex to the graph, which is subsequently connected to every other vertex by zero-weighted edges.
> ...
> because it has a 0-weighted edge connecting it to every other node in the graph, none of its shortest path distances will ever be positive
\(if negative weights exist\)
> Here, w(uv) represents the original edge weight between nodes `u` and `v`, `d[s, u]` and `d[s, v]` represent the shortest path distances between `S` and `u/v`, and `W(uv)` represents the transformed edge weight values.
:::
> Reference\: Book Page 312
## Strongly Connected Components
A strongly connected components is exclusive to directed graphs.
> Reference
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications **Page 327**
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
> Figure 7.14\: Graph with different strongly connected components
In the above picture, `A`, `B`, `CEFG`, `DHI` are strongly connected components
## Kosaraju's Algorithm
Finding strongly connected components in a graph.
> Kosaraju's algorithm works by performing two independent sets of **DFS** traversals, first exploring the graph in its original form, and then doing the same with its transpose
> Reference
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications **Page 329**
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
> Figure 7.16\: Transpose of a graph
:::success
:bulb: **Kosaraju\'s Algorithm**
https://www.youtube.com/watch?v=QlGuaHT1lzA
:::
**Using Adjacency Lists**
> The use of adjacency matrices with this algorithm is not recommended due to the significant amount of additional iterations required to find the neighbors of each vertex in the traversal.
**Implementation**
https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson7/Exercise35/Exercise35.cpp
# Dynamic Programming I
* **Overlapping Subproblems**
* **Optimal Substructure**\: when the optimal solution to the overall problem can be formed through some combination of the optimal solutions of its subproblems.
My Other Post \:
* **Course \: Advanced Analysis of Algorithms** III\. Dynamic Programming
https://hackmd.io/9tGyeFoYRVuArznahp07Iw#III-Dynamic-Programming
## Examples of DP Problems
* Combinatorics \(Counting the number of combinations\/permutations of a sequence matching certain criteria\)
* Strings\/arrays (edits distance, longest common subsequence, longest increasing subsequence, etc)
* Graphs \(shortest path problem\)
## Two Required Properties for Dynamic Programming
> Reference \:
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications **Page 352**
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
>... , the Fibonacci sequence is said to exhibit a property known as **overlapping subproblems**. This is one of the defining characteristics that separate a standard **divide-and-conquer** problem from a **dynamic programming** problem; **in the former, subproblems tend to be unique, whereas in the latter, the same subproblems must be solved repeatedly**
> ...
> A problem is said to exhibit an **optimal substructure** when the optimal solution to the overall problem can be formed through some combination of the optimal solutions of its subproblems.
:::success
the purpose of DP is to devise a method of caching previous solutions as a means to avoid the repeated calculation of previously solved subproblems.
:::
## Not DP Way \: Top-down Solution as Memoization
:::info
:information_source: **Wiki for Memoization**
https://zh.wikipedia.org/zh-tw/%E8%AE%B0%E5%BF%86%E5%8C%96
:::
* Indexing of the previous caclulation results should be unique \(One index for a state\).
* Still working recursively; therefore, stack overflow might be possible.
## The DP Way \: Bottom-up Solution as Tabulation
As the name suggest, tabulation is the inverse approach to the memoization.
> Reference \:
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications **Page 356**
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
> The standard implementation of tabulation consists of storing the solutions for the base cases and then iteratively filling a table with the solutions for every subproblem, which can then be reused to find the solutions for other subproblems.
> ...
> In addition to the fact that tabulated solutions frequently tend to be much more efficient in terms of memory, they also produce a complete lookup table encompassing every given state. Therefore, if you are likely to receive queries about any state of the problem, tabulation is likely to be your best option.
:::success
any problem that can be solved with memoization can theoretically be reformulated into a tabulated solution, and vice versa.
:::
## Subset Sum Problem
> Reference \:
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications **Page 357**
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
> the subset sum problem asks the following question\: given a set of non-negative integers, S, and an integer, x, is there a subset of S's elements whose sum is equal to x?
:::info
:information_source: **Subset Sum Problem**
* Subset Sum Problem Explained \(Dynamic Programming\)
https://favtutor.com/blogs/subset-sum-problem
* Programming Interview : Dynamic Programming \:Subset sum problem
https://www.youtube.com/watch?v=zKwwjAkaXLI
:::
**Step \#1**
In the above image, the book provide a easily understanded diagram, which shows that there exist optimal substructure and overlapping subproblem.
> each new subset of size n is formed by appending a single new element to a subset of size `n - 1`.
**Step \#2**
*Define the states and the base cases.*
### Brute Force
**Why Brute Force?**
1. Simplicity
2. The certainty of solution correctness
3. Ability to visualize the subproblems
### Backtracking
Recurssion termination conditions \(Base Case\). Basically, it means early stopping. The subset sum problem can be stopped early by checking if the subset sum is going to exceed the target value.
**Implementation**
https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson8/Exercise37/Exercise37.cpp
```cpp
bool SubsetSum_Backtracking(vector<int> set, int sum, int i)
{
// The sum has been found
if(sum == 0)
{
return true;
}
// End of set is reached, or sum would be exceeded beyond this point
if(i == set.size() || set[i] > sum)
{
return false;
}
// Case 1: Add to sum (Notice that adding to the sum means that the up-coming sum of the set should be equal to sum - current-element(set[i]))
// Case 2: Leave as-is
return SubsetSum_Backtracking(set, sum - set[i], i + 1)
|| SubsetSum_Backtracking(set, sum, i + 1);
}
```
Notice that the above function can only work when the set is ***sorted***. The source code from github repo showes that the main function first sort the set before calling and timing the above function.
### Memoization
There are few ways for the Cache Schemes when using Memoization
* Simple Arrays \: for numerical indexing and faster than `std::map`.
* Hash Tables\/Maps with built-in language features \: cache key is integer but too big.
* Hash Tables\/Maps with custom hashing formula
:::info
:information_source: `std::map` v.s. `std::unordered_map`
> Reference \:
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications **Page 374**
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
> Hash tables (for example, std::unordered_map) tend to be much faster than standard map/dictionary structures for locating and retrieving keys (but are still slower than arrays).
> ...
> std::map is much more versatile than std::unordered_map in terms of what types of data can be used as keys. Although std::unordered_map can technically offer the same functionality, it requires the programmer to create their own hashing function for data types it is not equipped to store as keys by default.
:::
To check if the cache scheme is good, we can use a count varaiable to store the amount of hit happened in the cache and judge the scheme by it.
```cpp
bool SubsetSum_Memoization(vector<int> &set, int sum, int i, vector<vector<int>> &memo)
{
// The sum has been found
if(sum == 0)
{
return true;
}
// End of set is reached, or sum would be exceeded beyond this point
if(i == set.size() || set[i] > sum)
{
return false;
}
// Is this state cached?
if(memo[i][sum] == UNKNOWN)
{
// Get solution for this state and cache it
bool append = SubsetSum_Memoization(set, sum - set[i], i + 1, memo);
bool ignore = SubsetSum_Memoization(set, sum, i + 1, memo);
memo[i][sum] = append || ignore;
}
// Return cached value
return memo[i][sum];
}
```
Notice that cache solely on the value of sum cannot produce correct answer. Refer to **book page 374**.
### Tabulation
> * C++ Data Structures and Algorithm Design Principles: Leverage the power of modern C++ to build robust and scalable applications **Page 380**
> https://www.amazon.com/Data-Structures-Algorithm-Design-Principles-ebook/dp/B07SYJSGVD
> if we have already determined that a sum, `x`, can be formed between indices `0` and `i` \(inclusive\), then clearly, a sum equal to both `x` and `x + set[i]` can be formed between indices `0` and `i + 1`.
**Implementation**
https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles/blob/master/Lesson8/Exercise39/Exercise39.cp#L116C1-L117C1
```cpp
vector<vector<bool>> SubsetSum_Tabulation(vector<int> &set)
{
int maxSum = 0;
for(int i = 0; i < set.size(); i++)
{
maxSum += set[i];
}
vector<vector<bool>> DP(set.size() + 1, vector<bool>(maxSum + 1, 0));
for(int i = 0; i < set.size(); i++)
{
DP[i][0] = true;
}
for(int i = 1; i <= set.size(); i++)
{
for(int sum = 1; sum <= maxSum; sum++)
{
if(sum < set[i-1])
{
DP[i][sum] = DP[i-1][sum];
}
if(sum >= set[i-1])
{
DP[i][sum] = DP[i-1][sum] || DP[i-1][sum - set[i-1]];
}
}
}
return DP;
}
```
Notice that the 2D table size is equal pretty big consider that one of the dimension size is equal to sum of all the input \(largest subsum possible + 1 for 0\). Additionally, this will output a table that can be reused as a look-up table for all the possible queries.
## Working with String Sequences LCS \(Longest Common Subsequence\)
My Other Post \:
* https://hackmd.io/9tGyeFoYRVuArznahp07Iw?view#III-Dynamic-Programming
# Appendix
## RAII
:::info
:information_source: **The Importance of Practicing RAII in C++**
https://medium.com/@gealleh/the-importance-of-practicing-raii-in-c-87011f3e3931
:::
## Sorting Algorithms Implementation
:::info
:information_source: **Common Sorting Algorithms**
This site provide detailed implementation and explaintation of different sorting algorithms. This will be used as the basic to try to improve on.
https://4yu.dev/post/Sort-Algorithm/
:::
:::info
:information_source: **STL 的排序演算法**
https://lkm543.medium.com/stl-的排序演算法-9e31de7f83b4
:::
## Stepanov Abstraction Penalty
> Reference \:
> * Alexander Stepanov Wikipedia
> https://en.wikipedia.org/wiki/Alexander_Stepanov
> * What are the downsides of using STL in C++?
> https://www.quora.com/What-are-the-downsides-of-using-STL-in-C++
## Nice Articles
> Reference \:
> * 礦坑系列
> https://hackmd.io/@Mes/Cpp_Miner/https%3A%2F%2Fhackmd.io%2F%40Mes%2FPreface
Sign in with Wallet
Connect another wallet