Algorithm: Design and Analysis , Part2, week1

Programming Assignment-1

Question 1
Code up the greedy algorithms for minimizing the weighted sum of completion times.Download the text file here. This file has the format:
[number_of_jobs]
[job_1_weight] [job_1_length]
[job_2_weight] [job_2_length]

Run the greedy algorithm that schedules jobs in decreasing order of the difference (weight – length). Report the sum of weighted completion times of the resulting schedule.

Question 2
Use the same data set as in the previous problem. Run the greedy algorithm that schedules jobs (optimally) in decreasing order of the ratio (weight/length). Report the sum of weighted completion times of the resulting schedule.

====================================================
Read More

Algorithm: Design and Analysis , Part1, Final Statement

Got the final statement for “Algorithm Design and Analysis Part1″ completion

Final_Statement2

Move on for Part2

Algorithm: Design and Analysis , Part1, week6

Programming Question-6
Question 1
Download the text file here.

Implement a variant of the 2-SUM algorithm.
The file contains 1 million integers, both positive and negative (there might be some repetitions!).

Compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y in the input file that satisfy x+y=t.

### Cousera: Stanford Algorithm: Design and Analysis
### Content: 1st assignment: 2Sum
### Week: 6th
### Date: June 20th 2014
### Author: Siting Liu
### ==================================================
from bisect import *

### --------------------------------------------------
def two_sum(_list, width):
    sumList = set()
    for x in _list:
        lpos = bisect_left(_list, -width-x)
        rpos = bisect_right(_list, width-x)

        sumList |= set([x + y for y in _list[lpos:rpos]])

    return sumList

### --------------------------------------------------
def main(fileName, width):
    _list = []
    with open(fileName,"r") as f:
        for line in f:
            _list.append(int(line.strip('\n')))

    f.close()

    _list.sort()

    return len(two_sum(_list, width))
### --------------------------------------------------
if __name__ == "__main__":
    print main("2sum.txt", 10000)

====================================================
Read More

Loading...
X