Algorithms

<Hash Table>

• Collision이 발생한 경우 대처방법이 필요하다. 대표적으로 chaining (=closed addressing)과 open addressing을 사용한다. chaining은 연결리스트를 활용하는 것이고, open addressing은 어떠한 식을 만들어서 다른 key에다가 value를 저장하는 것이다. Open addressing의 방법으로는 linear probing, quadratic probing, double hasing등이 있다. 

• Collision: Two keys result in the same value. The situation where a newly inserted key maps to an already occupied slot in the hash table is called collision and must be handled using some collision handling technique. (https://www.geeksforgeeks.org/separate-chaining-collision-handling-technique-in-hashing/)

<BFS and DFS>

• Time complexity of BFS: 

  • O(V + E) when adjacency list is used. 

  • O(V^2) when adjacency matrix is used.

• Time complexity of DFS:

  • O(V + E) when adjacency list is used.

  • O(V^2) when adjacency matrix Is used. 

<Topological Sort> 

• DAG(Directed Ayclic Graph)의 노드들을 순서화(sorting)하는 것. 

• Time complexity of Topological Sort is O(V + E) 

• 방법: Incoming edge=0 인 vertex를 순서대로 나열한다. incoming edge=0 인 vertex를 제거하고 그 vertex에 연결된 edge 또한 제거한다. 이 과정을 반복한다. 

<Shortest Path Problem>

• Single source: 하나의 출발노드 S로부터 다른 모든 node까지의 최단 경로를 구한다. (Bellman Ford, Dijkstra) 

• Single pair: 하나의 출발노드 S로부터 목적지 노드 T까지의 최단경로

• All pairs: 모든 노드 쌍에 대해서 최단경로를 찾아낸다 (Floyd Warshall and Johnsons)

• 중요: 최단경로의 어떤 부분 경로도 역시 최단경로이다. 

• DAG에서 longest path problem은 polynomial-time으로 풀 수 있는 문제이다.

• Bellman-Ford (Greedy algorithm 아님)

1. Directed vs Undirected graph 둘 모두 가능

2. It can handle directed graphs with negative weights, as long as we don’t have negative cycles. (https://www.baeldung.com/cs/dijkstra-vs-bellman-ford)

3. Undirected에서는 negative weights가 있으면 안된다. Negative cycle은 무조건 안된다. 

Time complexity: O(E V) = O(V^3). 모든 에지 E에 대해서 relexation을 V-1번 실행.

• Dijkstra (Greedy algorithm) 

1. Directed and undirected graph 둘 모두 가능

1. 음수 가중치가 없다고 가정한다. 

2. Bellman-Ford and Dijkstra's algorithms have the same end result!

Time complexity: O(V^2), but with min-priority queue it is O(V + E log V)

• Floyd-Warshall Algorithms (solved by Dynamic Programming)

1. Directed and undirected graph 둘 모두 가능 

2. Directed 일 경우, negative weight가 있어도 가능.

3. 모든 노드 쌍들간의 최단경로 길이를 구함 (All-pair Shortest Path)

Time complexity: O(V^3)

• Johnsons Algorithm 

1. Sparse graph에서는 Johnsons Algorithm의 성능이 Floyd-Warshall보다 좋다. (Sparse graph에서는 Johnsons Algorithms을 쓰는 것이 좋다)

2. 더 자세히는 알필요가 없는 것 같다.

<Minimum Spanning Tree>

• Spanning tree: 그래프의 모든 정점을 잇지만 사이클이 없는 부분그래프를 의미한다.

• Edge에 가중치가 있을 때, 최소의 비용으로 모든 도시들이 연결되게 하는 알고리즘.

• 해가 유일하지 않다. 

• 무방향 가중치 그래프에서 정의된다.  그리고 양(positive)의 가중치를 가져야 한다. 

• 해(solution)은 항상 tree가 된다. 즉 cycle이 없다. (노드가 n개인 트리는 항상 n-1개의 edge를 가진다.)

• Gernic MST algorithm.

1. 처음에는 A=0 이다.

2. 집합 A에 대해서 안전한 에지를 하나 찾은 후, 이것을 A에 더한다. 

3. 에지의 갯수가 n-1개가 될 때까지 2번을 반복한다. 

• Minimum Spanning Tree - Kruskal's algorithm (Greedy algorithm 사용)

1. 에지들을 가중치의 오름차순으로 정렬한다. 

2. 에지들을 그 순서대로 하나씩 선택해간다. 단 이미 선택된 에지들과 cycle을 형성하면 그 에지를 선택하지 않는다. 

3. n-1개의 edge가 선택되면 종료한다.

Time complexity = O(E log E) = O(E log V)

• Minimum Spanning Tree - Prim's algorithm (Greedy algorithm 사용)

1. 임의의 노드를 출발노드로 선택 

2. 출발노드를 포함하는 트리를 점점 키워감 

3. 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택.

Time complexity = O(E log E) = O(E log V) by using priority heap. O(V^2) when priority heap is not used.

• Prim과 Kruskal 에서 결과값은 total edge weight측면에서는 같은 것이다. 하지만 그 경로가 다를 수는 있다. 

<Pre-order, In-order, Post-order Traversal>

• The best video that I've found: https://www.youtube.com/watch?v=WLvU5EQVZqY 

• Pre-order: 첫번째로 그 노드를 visit하면 print 

• In-order: 두번째로 그 노드를 visit하면 print 

• Post-order: 세번째로 그 노드를 visit하면 print 

<Dynamic Programming>

• 순환식을 세운다.

• 순환식을 memoization(= Top-down: 중간 계산 결과를 caching하여 중복 계산을 피함. 실제로 필요한 subproblem만 푼다.) 방식이나 bottom-up(= recursion에 수반되는 overhead가 없다.) 방식으로 푼다. 

<Optimal Substructure>

• The problem is said to be an optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. 

• Divide and Conquer, Greedy, Dynamic Programming은 모두 문제가 가진 optimal substructure의 특성을 이용한다.

<Recursion>

• Recursion이 무한루프에 빠지지 않으려면? Fibonacci Numbers를 생각하면 쉽다.

1. Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재하여야 한다. 

2. Recursive case: Recursion을 반복하려면 결국 base case로 수렴해야 한다. 

3. Function P should have an execution path where it does not call itself.

4. Function P should either refers to a global variable or has at least one parameter.

<2-SAT vs 3-SAT>

• 2-SAT is in P 

• 3-SAT is in NP

<P & NP Problem>

• P in the P class stands for polynomial time. It is the problem that can be solved by a deterministic machine in polynomial time.

• NP in NP class stands for non-deterministic polynomial time. It is the problem that can be solved by a non-deterministic machine in polynomial time.

• NP-hard is at least as hard as the hardest problem in NP.

1. All NP-hard problems are not in NP

2. A problem X is NP-hard if, for every problem in Y in NP, there exists a polynomial-time reduction from Y to X.

• It is NP-complete if the problem is both NP and NP-hard.

• To prove that problem A is NP-hard, reduce a known NP-hard problem to A

• R is NOT in P when 'Q is NP-complete and Q is polynomial time reducible to R' (This means that R is NP-hard). 

• If every problem in NP can be reduced to X then X is NP-hard.

<Max flow Algorithm>

• Max flow algorithm is not greedy!

• Ford-Fulkerson: 

1. Uses the DFS approach

2. Time complexity: O(E * f) where f is the maximum flow of a network

• Edmonds-Karp (It is a modified form of the Ford-Fulkerson algorithm): 

1. Uses the BFS approach

2. Time complexity: O(V * E^2)

<AVL Tree>

• 모든 노드에 대해서 노드의 왼쪽부트리와 오른쪽 부트리의 높이차가 1이하인 BST (Binary Search Tree)

• Rotation may be required for insertion or deletion

• The height of the tree cannot exceed 1.44 x logN where N is the number of nodes.

• Search, insert, and delete take O(logN) 

<Red Black Tree>

• Node의 색(color)은 red or black이다.

• A root and leaves are always black.

• If a node is red then children are black.

• All paths from a node to its NIL descendants contain the same # of black nodes (=black height).

• Nodes require one storage bit to keep track of color.

• The longest path P (root to farthest NIL) is no more than twice the length of the shortest path p (root to nearest NIL). That is, P < 2 x p

• # of NIL leaves in T = 1 + # of interior nodes in T

• Rotation may be required for insertion and deletion

• Search, insert, and delete take O(logN)

<B - Tree>

• Rotations are not required

• All leaves have the same depth 

• Height = # of disk operation

• Height ≤ log_t ((N+1) / 2)로 알려져 있다 (t = minimum degree of B-Tree)

• Search, insert, and delete take O(logN)

<Simple graph>

• Also called as strict graph 

• Un-weighted, un-directed, no-loops, and no-multiple edges between nodes.

<Loop invariant>

• 프로그램 loop에서 모든 반복 시의 전후로 변하지 않는 성질

• True at the beginning of each execution of the loop and at the completion of the loop.

<Singly linked list vs Doubly linked list>

• 다음 속성은 singly와 doubly 둘 모두에 적용된다 (Singly인 경우: 포인터가 첫번째 노드를 가르키고 있다고 생각. Doubly인 경우: 포인터가 첫번째 노드와 마지막 노드를 가르키고 있다고 생각.)

• Singly linked list: Search: O(N), Insertion: O(1), Deletion: O(1)

• Doubly linked list: Search: O(N), Insertion: O(1), Deletion: O(1)

• Insertion 

1. 새로운 노드 생성

2. 이전노드의 포인터를 새로 만든 노드로 설정

3. 새로 만든 노드의 포인터를 다음노드로 설정

• Deletion

1. 지우고 싶은 것이 A --> B --> C 중에 B라면 

2. A --> C (A의 포인터를 B가 아닌 C를 가르키게 함), B --> C (위상태를 그냥 유지함) 로 만들어주고, 

3. B를 제거해준다. 

<Common Data Structure and Time Complexity>

<Eulerian vs Hamiltonian>

• Eulerian circuit/path is a circuit/path that uses every edge in a graph with no repeats.

1. Degree가 홀수인 정점(vertex)가 2개일 때 Euler path가 존재한다.

2. Degree가 홀수인 정점(vertex)가 0개일 때 Euler circuit이 존재한다.

• Hamiltonian circuit/path is a circuit/path that visits every vertex once with no repeat.

<Circuit vs Path>

• Circuit: Start and end at the same vertex 

• Path: Does not need to start and end at the same vertex

<Boolean Logic>

• AND: A . B 

• OR: A + B

• NOT: ㄱA

• NAND: ㄱ(A . B) = ㄱA + ㄱB

• NOR: ㄱ(A + B) = ㄱA . ㄱB

• XOR: A ⊕ B = (A + B) . (ㄱA + ㄱB) = A  . ㄱB + ㄱA . B

• XNOR: A⊙ B = (A + ㄱB) . (ㄱA + B) = A . B + ㄱA . ㄱ.B