## Algorithm: Design and Analysis , Part2, week1

Posted by Siting Liu On July 25th, 2014

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

Posted by Siting Liu On July 25th, 2014

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

Move on for Part2

## Algorithm: Design and Analysis , Part1, week6

Posted by Siting Liu On July 10th, 2014

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
### 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