斯坦福 算法2 第一周作业

来自斯坦福网站的Algorithms: Design and Analysis，与目前coursera上的版本内容没有变化，不过时间安排略有不同。

1. Problem Set 1

按照提示，$R_{j}$Rj​表示按结束时间升序排序的第j个任务，设其结束时间为$S_{j}$Sj​。那么这个任务占用的时间就是$[S_{j-1},S_{j}]$[Sj−1​,Sj​]。其它的任何任务i占用的时间都是$[S_{j-1},S_{i}]$[Sj−1​,Si​]，而根据设定$S_{i} \geq S_{j}$Si​≥Sj​，也就是说选择$R_{j}$Rj​占用的时间段初试时间与其它所有任务相同，而结束时间比选择其它的都短，因此与最少的任务重叠。

刚开始我觉得应该按$d_{j}-p_{j}$dj​−pj​来排序，后来发现用$d_{j}$dj​就可以了。证明过程与课程中的证明很类似。按照$d_{j}$dj​升序得到的解法$\alpha$α的表示为[1,2,3,…,n]，而假设最优解$\alpha*$α∗与$\alpha$α不同。那么就最优解$\alpha*$α∗中就必然存在至少一个连续的逆序对i,j使得$d_{i} > d_{j}$di​>dj​。i前一个任务i-1的结束时间为$C_{i-1}$Ci−1​，i之前与j之后的人物的$l$l值不受影响。我们只需要关注$max(l_{i},l_{j})$max(li​,lj​)的结果。

在最优解法$\alpha*$α∗下任务i先执行，j后执行。因此$max(l_{i}^{*},l_{j}^{*}) = max(C_{i-1}+p_{i}-d_{i}, C_{i-1}+p_{i}+p_{j}-d_{j})$max(li∗​,lj∗​)=max(Ci−1​+pi​−di​,Ci−1​+pi​+pj​−dj​) 。假如交换i与j的执行顺序，那么得到新的$max(l_{i},l_{j}) = max(C_{i-1}+p_{j}-d_{j}, C_{i-1}+p_{i}+p_{j}-d_{i})$max(li​,lj​)=max(Ci−1​+pj​−dj​,Ci−1​+pi​+pj​−di​)。因为$d_{i} > d_{j}$di​>dj​，所以$l_{j}^{*} = C_{i-1}+p_{i}+p_{j}-d_{j} > l_{i} = C_{i-1}+p_{j}-d_{j}$lj∗​=Ci−1​+pi​+pj​−dj​>li​=Ci−1​+pj​−dj​，同时$l_{j}^{*} = C_{i-1}+p_{i}+p_{j}-d_{j} > l_{j} = C_{i-1}+p_{i}+p_{j}-d_{i}$lj∗​=Ci−1​+pi​+pj​−dj​>lj​=Ci−1​+pi​+pj​−di​。于是得到$max(l_{i}^{*},l_{j}^{*}) > max(l_{i},l_{j})$max(li∗​,lj∗​)>max(li​,lj​)，也就是说交换后的策略更好，与假设最优解$\alpha*$α∗与贪心结果$\alpha$α不同矛盾。得证。

用心感受。

子图中的最小生成树T的边可能无法组成一个联通图，因此有可能不是一个生成树。但是因为The Cut Property，子图内部的T的每条边肯定依然是最小的，因此就是子图的生成树的组成部分。

仔细想想不难。

2. Optional Theory Problems

告辞。

3. Programming Assignment 1

3.1 3.2 课程中的scheduling 问题

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <sstream>
#include <set>
#include <string>
#include <ctime>
#include <algorithm>

using namespace std;

#define INT_MAX 2147483647


void readData(string fileName,vector<pair<int,int>>& v) {
    cout << "read data from "<< fileName <<endl;
    ifstream input(fileName);
    string line;
    int weight, length;
    getline(input,line); //num
    if(input) {
        while(getline(input,line)) {
            istringstream ist(line);
            ist >> weight >> length;
            v.push_back({weight,length});
        }
    }
    cout << "reading data finished."<<endl;
}

bool divcmp(pair<int,int>& a, pair<int,int>& b) {
    double score1 = double(a.first)/a.second;
    double score2 = double(b.first)/b.second;
    return score1 > score2;
}

bool diffcmp(pair<int,int>& a, pair<int,int>& b) {
    double score1 = a.first-a.second;
    double score2 = b.first-b.second;
    if(score1 == score2)
        return a.first > b.first;
    return score1 > score2;
}

void weightSum(vector<pair<int,int>>& v) {
    vector<pair<int,int>> v1 = v;
    
    cout << "sort jobs according to difference ..."<<endl;
    sort(v.begin(),v.end(),diffcmp);
    cout << "sort finished."<<endl;
    long long sum1 = 0, t = 0;
    for(int i = 0; i < v.size(); i++) {
        t += v[i].second;
        sum1 += t*v[i].first;
    }

    cout << "problem1 res: "<< sum1 << endl;
    
    cout << "sort jobs according to divide ... "<<endl;
    sort(v1.begin(),v1.end(),divcmp);
    cout << "sort finished."<<endl;
    long long sum2 = 0;
    t = 0;
    for(int i = 0; i < v1.size(); i++) {
        t += v1[i].second;
        sum2 += t*v1[i].first;
    }
    cout << "problem2 res: "<< sum2 << endl;
}

int main() {
    string fileName = "jobs.txt";
    vector<pair<int,int>> v;
    readData(fileName,v);
    weightSum(v);
    return 0;
}

3.3 Prim 算法

只实现了naive版本的。heap加速写起来还是太麻烦。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <sstream>
#include <set>
#include <string>
#include <ctime>
#include <algorithm>

using namespace std;

#define INT_MAX 2147483647


void readGraph(string fileName,unordered_map<int,vector<pair<int,int>>>& G) {
    cout << "read data from "<< fileName <<endl;
    ifstream input(fileName);
    string line;
    int u,v,weight;
    if(input) {
        getline(input,line);
        while(getline(input,line)) {
            istringstream ist(line);
            ist >> u >> v >> weight;
            G[u-1].push_back({v-1,weight});
            G[v-1].push_back({u-1,weight});
        }
    }
}


long long prim(unordered_map<int,vector<pair<int,int>>>& G, int start) {
    int N = G.size();
    long long res = 0;
    vector<int> visited(N);
    vector<int> curDis(N,INT_MAX);

    curDis[start] = 0;
    int visitedCount = 0;
    int next,nextDis;

    while(visitedCount < G.size()) {
        next = -1;
        nextDis = INT_MAX;
        for(int i = 0; i < N; i++)
            if(visited[i] == 0 && curDis[i] < nextDis) {
                nextDis = curDis[i];
                next = i;
            }
        
        visited[next] = 1;
        res += nextDis;
        visitedCount++;
        if(next == -1) break;

        for(int k = 0; k < G[next].size(); k++) {
            auto p = G[next][k];
            if(!visited[p.first])
                curDis[p.first] = min(curDis[p.first],p.second);
        }
    }
    return res;
}

int main() {
    string fileName = "edges.txt";
    unordered_map<int,vector<pair<int,int>>> G(500);
    readGraph(fileName,G);

    long long res = prim(G,0);
    cout << "prim res: "<< res << endl;
    return 0;
}