Programming Question - 3 coursera ADA

import sys
import random

def ParseGraph(filename):
  vertices = []
  edges = set([])

  for l in open(filename):
    fields = [int(f) for f in l.split()]
    vertex = fields.pop(0)
    incident = [tuple(sorted([vertex, f])) for f in fields]
    vertices.append(vertex)
    edges.update(incident)

  return vertices, list(edges)

def RandomContraction(vertices, edges):
  while len(vertices) > 2:
    edge = random.choice(edges)
    a, b = edge
    vertices.remove(b)
    new_edges = []
    for e in edges:
      if e == edge:
        continue
      if b in e:
        if e[0] == b:
          other = e[1]
        if e[1] == b:
          other = e[0]
        e = tuple(sorted([a, other]))
      new_edges.append(e)
    edges = new_edges
     
  return vertices, edges

vertices, edges = ParseGraph(sys.argv[1])

minimum = sys.maxint
for i in range(0, 1000):
  v, e = RandomContraction(vertices[:], edges[:])
  print v, len(e)
  if len(e) < minimum:
    minimum = len(e)

print "min cut: %d" % minimum


17

Programming Question - 2 Algorithms: Design and Analysis, Part 1 Stanford

from sys import argv

def quicksort(A,begin,end) :
count = 0
if end - begin <= 1:
return 0
else :
#swap done here
A[begin], A[end-1] = A[end-1] , A[begin]
split = partition(A,begin,end)
count = end - begin - 1
lc = quicksort(A,begin,split)
rc = quicksort(A,split+1,end)
return count + lc + rc


def partition(A,begin,end) :
pivot = A[begin]
i = begin + 1

for j in range(begin+1,end) :
if A[j] < pivot :
A[i], A[j] = A[j], A[i]
i = i + 1

A[i-1], A[begin] = A[begin], A[i-1]
return i-1


len(A)
quicksort(A,0,len(A))



Output1: 162085
Output2: 164123
Output3: 138382

Count Inversions in an array - coursera Programming Question-1 python mearge sort

Data taken from text file code:-

#load the array with text file
fin = open(../../coresera/inversions/IntegerArray.txt)
A=[]
for line in fin:
    A.append(int(line.strip()))

mearge sort : python code

import random
from sys import maxsize as inf


def merge_sort(A):
def merge(L, R):
m = len(L)-1
B = []
i = j = 0
inv = 0
while L[i] != inf or R[j] != inf:
if L[i] <= R[j]:
B.append(L[i])
i += 1
else:
B.append(R[j])
inv += m - i
j += 1
return B, inv
n = len(A)
inv = 0
if n >= 2:
mid = n // 2
L, R = A[:mid], A[mid:]
L, inv_left = merge_sort(L)
R, inv_right = merge_sort(R)
A, inv_split = merge(L + [inf], R + [inf])
inv = inv_left + inv_right + inv_split
return A, inv


if __name__ == '__main__':
A = [1,6,3,2,4,5]
A, inv = merge_sort(A)
print (inv)
print (A)



# Count the number of lines in a file.
if __name__ == "__main__":
    in_file = open("../../coresera/inversions/IntegerArray.txt")
    line_count = 0
    while True:
        in_line = in_file.readline().strip()
        if in_line == "":
            break;
        line_count += 1
    in_file.close()
    print("Line count:", line_count)




2407905288