IT279: Algorithm and Data Structures Recap 3/3

NP Problems

What is an "undecidable" problem in computer science?

- a problem that can't be solved no matter how much time and memory is provided

 

In computer science in terms like NP-complete or NP-hard, "NP" stands for:

- non-deterministic polynomial(비결정성 다항식)

 

True or false: Any problem that can be solved by a deterministic computer in polynomial time can also be solved by a non-deterministic computer in polynomial time.

- True

 

Greedy algorithms

It bases each decision on the information available at the time the decision is made.

It solves the problem one step at a time.

It uses a greedy criterion to determine the next step to take.

examples) Dijkstra's, Prim's, Kruskal's, Huffman Code

 

Huffman code(O(n log n))

- Priority Queue, frequency table(including end of message), binary tree -> build code table from the tree

grab two elements from the priority queue to build a new binary tree

And push the tree into the priority queue

It will go until there are no elements in the priority queue.

 

Greedy algorithm criteria

Dijkstra's: At each step, choose the vertex with the minimum distance from the starting point among those not yet included in the shortest path tree.

Prim's: Start from any vertex and choose the edge with the smallest weight that connects a vertex in the growing spanning tree to a vertex outside it.

Kruskal's: Select the edge with the lowest weight that does not form a cycle with the already selected edges.

Huffman Code: Repeatedly merge two nodes with the lowest frequency or combined frequency, building up a binary tree from the leaves to the root.

Bin-Packing:

- next fit: place the next item into the same bin as the previous item if it fits, or start a new bin if it doesn't

- First fit: place the next item into the first bin in which it fits

- Best fit: place the next item into the tightest spot, the bin that will leave the least room after the item is placed.

bin packing algorithm(Offline version is for sorted items)

Divide and conquer algorithm

Recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

 

Merge sort

Divide the array into two halves, recursively sort each half, and then merge the sorted halves

 

Quick Sort

Pick a 'pivot' element, partition the array into two sub-arrays with elements less than the pivot and elements greater than the pivot, and then recursively sort the sub-arrays.

 

Binary Search

Compare the target value to the middle element of the array; if they are not equal, half the array can be eliminated from consideration, and the search is performed recursively on the remaining half.

 

the closest pair of points

Split points into two partitions by X coordinate, find the two closest points within each partition using the same approach and then determine which of those pairs is closest and whether there is a closer pair across the partitions.

 

Dynamic Programming

Dynamic programming can only be applied if optimal solutions are built out of optimal solutions to subproblems.

True or False: If time is not a concern, any problem that could be solved using dynamic programming could also be solved using divide and conquer.

best describes: Bottom-up

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable when the problem can be divided into overlapping subproblems that can be solved independently. The key property that makes a problem suitable for dynamic programming is the presence of overlapping subproblems and optimal substructure.

Ex) Fibonacci sequence, shortest path problems (like Bellman-Ford), and the Knapsack problem are well-suited to DP.

 

multiply A B C matrices:

10*2 2*20 20*5

(AB)C

10 * 20 * 2 = 400, 10 * 20

10 * 5 * 20 = 1000, 10 * 5

1400

 

A(BC)

2*5*20 = 200, 2*5

10 * 5 * 2 = 100, 10 * 5

300

 

 

 

Randomized algorithms

 

Backtracking

backtracking is a form of Depth-first search(preorder)

We can find optimal solutions to NP-complete problems such as traveling salesman, bin packing, and graph coloring using backtracking.

The purpose of the game tree generated by minimax or alpha-beta pruning is to select a single optimal move for the compute player (typically called Max).

 

Red-black trees

 

Recoloring: We make the grandparent red and the uncle and parent black.(moving the red up the tree and the black down.)

Then we have to check to grandparent. If it is the root, we turn it black. If its parent is red, we again check the uncle and recolor or rotate.

Rules

- If the parent of the new node is red, check the uncle's sibling.

- If sibling Red, recolor parent, grandparent and uncle

1. If sibling is black (trianle) -> rotate newnode's parent

2. If sibling is black (line) -> rotate node's grandparent and recolor parent and grandparent

 

 

Rotation: Happens when uncle/aunt is black

Rotate parent and grandparent (and red child if double rotation)

Resulting parent is black

We're basically moving one of the red nodes over to the other subtree of the grandparent.

Rotations are the same as AVL rotations

 

 

When is insertion into a red-black tree different from insertion into a regular binary search tree?

When the parent of the new node is red.

 

When a newly inserted node requires us to adjust the tree, what node do we look at to determine whether to rotate or to recolor?

The new node's aunt

 

The longest path from root to leaf in a red-black tree can be up to twice as long as the shortest path from root to leaf in the tree.

 

 

Wrap-up

Stable sort: bubble sort, insertion sort, merge sort

smallest to largest: O(1), O(log n), O(n), O(n log n), O(n2), O(2n)

Priority for Dijkstra's algorithm: The cost of the edge + the cost to get to the "from" vertex (smallest first)