Coursera - Algorithms: Design and Analysis, Part 1

Week 1 - Question 1 
Download the text file here. (Right click and save link as) This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated. Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array. Because of the large size of this array, you should implement the fast divide-and-conquer algorithm covered in the video lectures. The numeric answer for the given input file should be typed in the space below. So if your answer is 1198233847, then just type 1198233847 in the space provided without any space / commas / any other punctuation marks. You can make up to 5 attempts, and we'll use the best one for grading. (We do not require you to submit your code, so feel free to use any programming language you want --- just type the final numeric answer in the following space.) [TIP: before submitting, first test the correctness of your program on some small test files or your own devising. Then post your best test cases to the discussion forums to help your fellow students!]

count inversion, 基本的merge sort嵌入count

vector<int> merge(vector<int> p1,vector<int> p2,long long &count) {
    vector<int> rt;
    int i = 0, j = 0;
    while (i < p1.size() && j < p2.size()) {
        if (p1[i] < p2[j]) {
            rt.push_back(p1[i]);
            count += j;
            i++;
        }else {
            rt.push_back(p2[j]);
            count += (p1.size() - i);
            j++;
        }
    }
    
    while (i < p1.size()) {
        rt.push_back(p1[i]);
        i++;
        count += j;
    }
    while (j < p2.size()) {
        rt.push_back(p2[j]);
        j++;
    }
    
    return rt;
}

vector<int> mergeSort(vector<int> &nums,int start, int end,long long &count) {
    if (start == end) {
        vector<int> rt(1,nums[start]);
        return rt;
    }
    int mid = (start + end) / 2;
    vector<int> part1 = mergeSort(nums,start,mid,count);
    vector<int> part2 = mergeSort(nums,mid + 1,end,count);
    return merge(part1,part2,count);
}

long long countInversions(vector<int> &nums) {
    long long count = 0;
    vector<int> v = mergeSort(nums,0,nums.size() - 1,count);
    return count / 2;
}

------------------------------------
closest pair of points

class Point{
public:
    int x;
    int y;
};


bool cmpX(Point &p1, Point &p2) {
    return p1.x < p2.x;
}

bool cmpY(Point &p1, Point &p2) {
    return p1.y < p2.y;
}

float bruteForce(vector<Point> &p, int left, int right) {
    // brubute force when there are lessn than 3 nodes
}

float getDistance(Point p1, Point p2) {
    // distance between two points
}

float split(vector<Point> &p,vector<Point> &q, int mid,int minD) {
    vector<Point> strip;
    for (int i = 0; i < strip.size(); i++) {
        if (fabs(strip[i].x - p[mid].x) < minD) {
            strip.push_back(strip[i]);
        }
    }
 
 // 7 position head in y-coordinates is enough
    for (int i = 0; strip.size() - 1; i++) {
        for (int j = i + 1; j <= i + 7 || j < strip.size()) {
            minD = min(minD,getDistance(strip[i],strip[j]));
        }
    }
 
    return midD;
}

float helper(vector<Point> &p,vector<Point> &q,int left,int right) {
    if (right - left <= 3) {
        return bruteForce(p,left,right);
    }
 
    int mid = (left + right) / 2;
    float minDistance = min(helper(p,left,mid), helper(p,mid,right));
 
    return min(minDistance,split(p,mid,minDistance));
}

float closestPair(vector<Point> &p) {
    sort(p.begin(),p.end(),cmpX);
    vector<int> q = p;
    sort(q.begin(),sortByY.end(),cmpY);
 
    helper(p,q,0,p.size() - 1);
}

-------------------------------------------------------------------------------------

1. [Posted June 29th] You are given as input an unsorted array of n distinct numbers, where n is a power of 2. Give an algorithm that identifies the second-largest number in the array, and that uses at most n+log2n−2 comparisons. 
2. [Posted June 29th] You are a given a unimodal array of n distinct elements, meaning that its entries are in increasing order up until its maximum element, after which its elements are in decreasing order. Give an algorithm to compute the maximum element that runs in O(log n) time. 找rotated array里的最大值
3. [Posted June 29th] You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative, or zero. You want to decide whether or not there is an index i such that A[i] = i. Design the fastest algorithm that you can for solving this problem. 2分取中点，如果i大于A[i], 往右走。如果小，往左走
4. [Posted June 29th] Give the best upper bound that you can on the solution to the following recurrence: T(1)=1 and T(n)≤T([n−−√])+1 for n>1. (Here [x] denotes the "floor" function, which rounds down to the nearest integer.) 
5. [Posted June 29th] You are given an n by n grid of distinct numbers. A number is a local minimum if it is smaller than all of its neighbors. (A neighbor of a number is one immediately above, below, to the left, or the right. Most numbers have four neighbors; numbers on the side have three; the four corners have two.) Use the divide-and-conquer algorithm design paradigm to compute a local minimum with only O(n) comparisons between pairs of numbers. (Note: since there are n2 numbers in the input, you cannot afford to look at all of them. Hint: Think about what types of recurrences would give you the desired upper bound.) find peak

--------------------------------------------------------------------------

Week 2
Notes: