## Algorithm: Design and Analysis , Part1, week6

Posted by Siting Liu On July 10th, 2014

Programming Question-6

Question 1

Download the text file here.

The goal of this problem is to implement a variant of the 2-SUM algorithm.

The file contains 1 million integers, both positive and negative (there might be some repetitions!).

Your task is to 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 35 36 37 38 39 40 41 42 43 |
## Cousera: Stanford Algorithm: Design and Analysis ## Content: 1st assignment: 2Sum ## Week: 6th ## Date: June 20th 2014 ## Author: Siting Liu from bisect import * class TwoSum(): def __init__(self, source): """""" self.source = source def readInput(self, source): _list = set([]) with open(source,"r") as f: for line in f: _list.add(int(line.strip('\n'))) f.close() _list = list(_list) _list.sort() return _list def main(self): _list = self.readInput(self.source) sumList = set([]) for x in _list: lpos = bisect_left(_list, -10000-x) rpos = bisect_right(_list, 10000-x) for y in _list[lpos:rpos]: if x!= y: sumList.add(x+y) print len(sumList) TwoSum("2sum.txt").main() |

====================================================

Read More

## Algorithm: Design and Analysis , Part1, week5

Posted by Siting Liu On June 21st, 2014

Programming Question-5

Question 1

In this programming problem you’ll code up Dijkstra’s shortest-path algorithm.

Download the text file here. (Right click and save link as).

The file contains an adjacency list representation of an undirected weighted graph with 200 vertices labeled 1 to 200. Each row consists of the node tuples that are adjacent to that particular vertex along with the length of that edge. For example, the 6th row has 6 as the first entry indicating that this row corresponds to the vertex labeled 6. The next entry of this row “141,8200″ indicates that there is an edge between vertex 6 and vertex 141 that has length 8200. The rest of the pairs of this row indicate the other vertices adjacent to vertex 6 and the lengths of the corresponding edges.

Your task is to run Dijkstra’s shortest-path algorithm on this graph, using 1 (the first vertex) as the source vertex, and to compute the shortest-path distances between 1 and every other vertex of the graph. If there is no path between a vertex v and vertex 1, we’ll define the shortest-path distance between 1 and v to be 1000000.

You should report the shortest-path distances to the following ten vertices, in order: 7,37,59,82,99,115,133,165,188,197.

IMPLEMENTATION NOTES: This graph is small enough that the straightforward O(mn) time implementation of Dijkstra’s algorithm should work fine. OPTIONAL: For those of you seeking an additional challenge, try implementing the heap-based version. Note this requires a heap that supports deletions, and you’ll probably need to maintain some kind of mapping between vertices and their positions in the heap

**First! A graph from this courses. LOL**

*Compared to the Algorithm course from Princeton on cousera, the course – Design and Analysis Algorithms by Stanford has sloppy notes and ppt presentations to read, and teacher has faster speaking pace for student to follow, However, I am just so into Stanford’s, for Tim Roughgarden’s deep explanation on mathematic prove.*

====================================================

Read More

## Algorithm: Design and Analysis , Part1, week4

Posted by Siting Liu On June 8th, 2014

Programming Question-4

Question 1

Download the text file here. Zipped version here. (Right click and save link as)

The file contains the edges of a directed graph. Vertices are labeled as positive integers from 1 to 875714. Every row indicates an edge, the vertex label in first column is the tail and the vertex label in second column is the head (recall the graph is directed, and the edges are directed from the first column vertex to the second column vertex). So for example, the 11th row looks liks : “2 47646″. This just means that the vertex with label 2 has an outgoing edge to the vertex with label 47646

Your task is to code up the algorithm from the video lectures for computing strongly connected components (SCCs), and to run this algorithm on the given graph.

Output Format: You should output the sizes of the 5 largest SCCs in the given graph, in decreasing order of sizes, separated by commas (avoid any spaces). So if your algorithm computes the sizes of the five largest SCCs to be 500, 400, 300, 200 and 100, then your answer should be “500,400,300,200,100″.

WARNING: This is the most challenging programming assignment of the course. Because of the size of the graph you may have to manage memory carefully. The best way to do this depends on your programming language and environment.

The SCC method is simply, but the challenge part is to handle large data.

Unluckily, python may not be the necessary one to do this, I crashed N times until finally I decided to work on C++ on xcode (< ---I love this app!)

Read More