CMPS 3120 Algorithm Analysis
Divide and Conquer
Computing the height of a binary tree:
Our "dummy" tree structure: (PS: node 1 is the root node)
which means, given a data like this:
1 2 3
2 4 5
4 0 0
5 0 0
3 0 6
6 0 0
The tree should looks like
Use D&C idea to solve this problem (hint)
Divide and Conquer in sorting algorithm
- Mergesort
- Quicksort
Multiplication of Large Integers: Consider the problem of multiplying two (large) n-digit integers represented by arrays of their digits such as: A = 12345678901357986429 ; B = 87654321284820912836 . The efficiency is n2 one-digit multiplications. Can you improve that?
Closest Pair problem: given n points in metric space, find a pair of points with the smallest distance between them.