Binary search – Python implementation

def binarySearch(array,item):
    if len(array) == 0: return False
    else:
        mid = len(array)//2
        if array[mid] == item:
            return True
        else:
            if item < array[mid]:
                return binarySearch(array[:mid],item)
            else:
                return binarySearch(array[mid+1:],item)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))
Advertisements

Heap – Python implementation

class Heap:
    #init
    def __init__(self):
        self.buffer = [0]
        self.size = 0
    #insert – key
    def insert(self, key):
        self.buffer.append(key)
        self.size = self.size + 1
        self.bublUp(self.size)
    #bublUp
    def bublUp(self, i):
        if i // 2 > 0:
            if self.buffer[i] < self.buffer[i // 2]:
                 swap(i,i // 2)
            self.bublUp(i // 2)
    #delMin
    def delMin(self):
        minVal = self.buffer[1]
        self.buffer[1] = self.buffer[self.size]
        self.buffer.pop()
        self.bublDown(1)
        return minVal
    #bublDown
    def bublDown(self, i):
        if i * 2 <= self.size:
            mc = self.minChild(i)
            if self.buffer[mc] < self.buffer[i]:
                self.swap(mc,i)
            self.bublDown(mc)
    #minChild
    def minChild(self,i):
        if 2*i + 1 > self.size:
            return 2 * i
        else:
            if self.buffer[2 * i] > self.buffer[2 * i + 1]:
                return 2 * i + 1
            else:
                return 2 * i
    #helper functions
    def swap(self, a, b):
        self.buffer[a],self.buffer[b] = self.buffer[b],self.buffer[a]
    def show(self):
        print self.buffer
h = Heap()
h.insert(4)
h.insert(4)
h.insert(8)
h.insert(9)
h.insert(4)
h.insert(12)
h.insert(9)
h.insert(11)
h.insert(13)
h.show()
print h.delMin()
h.show()

Merge sort – Python implementation

def Sort(left,right):
    i = j = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    result = result + left[i:]
    result = result + right[j:]
    return result
def mergeSort(array):
    if len(array) < 2: return array
    else:
        mid = len(array) / 2
        left = mergeSort(array[:mid])
        right = mergeSort(array[mid:])
        return Sort(left,right)
a = list(xrange(10000))
a.reverse()
mergeSort(a)

Required knowledge for n00b computer scientist – Field algorithms

  1. What is Big-O?
  2. Implement Stack
  3. Implement Queue
  4. Implement Merge-Sort
  5. Implement Quick-Sort
  6. Implement Sequential  Search
  7. Implement Sequential Sorted Search
  8. Implement Brackets Pair Checker (“([{“)
  9. Implement Infix To Postfix conversion
  10. Implement Postfix calculator
  11. Implement base convertor (recursive and regular)
  12. Implement binary search.
  13. Implement palindrome  checker
  14. Implement a function that will enable reversing the input string.
  15. Implement a function that will enable deleting the white space and special characters.
  16. Implement Quick-Sort with random pivot.
  17. Implement Quick-Sort with “Median-of-Three”.
  18. Implement algorithm which finds median of three numbers with two comparisons.
  19. Implement graph
  20. Implement random contraction algorithm – Karger’s algorithm minimum cut
  21. Implement DFS (Depth-first Search)
  22. Implement non-recursive DFS (Depth-first Search)
  23. Implement BFS (Breadth-First Search)
  24. Implement BFS (Breadth-First Search) path finding
  25. Implement topological sort using non-recursive DFS (Depth-first Search)
  26. Implement computing Strong Connecting Components (SCC) – Kosaraju’s or Tarjan’s algorithm (improved Kosaraju’s version).
  27. Implement Dijkstra’s shortest path algorithm

Dijkstra’s shortest path algorithm – Python Implementation

from pprint import pprint
def dijkstra(graph,start,target):
    inf = 0
    for u in graph:
        for v ,w in graph[u]:
           inf = inf + w
    dist = dict([(u,inf) for u in graph])
    prev = dict([(u,None) for u in graph])
    q = graph.keys()
    dist[start] = 0
    #helper function
    def x(v):
        return dist[v]
    #
    while q != []:
        u = min(q, key=x)
        q.remove(u)
        for v,w in graph[u]:
            alt = dist[u] + w
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
    #”way”
    trav = []
    temp = target
    while temp != start:
        trav.append(prev[temp])
        temp = prev[temp]
    trav.reverse()
    trav.append(target)
    return ” -> “.join(trav),dist[target]
graph = {
    ‘A’ : [(‘B’,20), (‘D’, 80), (‘G’, 90)],
    ‘B’ : [(‘F’, 10)],
    ‘C’ : [(‘F’, 50), (‘H’, 20)],
    ‘D’ : [(‘G’, 20), (‘C’, 10)],
    ‘E’ : [(‘B’, 50),(‘G’, 30)],
    ‘F’ : [(‘D’, 40),(‘C’, 10)],
    ‘G’ : [(‘A’, 20)],
    ‘H’ : []
    }
pprint(graph)
print
traverse, dist = dijkstra(graph,’A’,’C’)
print traverse
print “Distance:”,dist