Tag Archive | programming

Python GTK + Glade Tutorials (links)

Links:

Pygtk Reference Manual (this is a must):

Advertisements

Quick-sort “median-of-three” – Python implementation

def swap(array,a,b):
    array[a],array[b] = array[b],array[a]
def partition(array,start,end):
    median = (end – 1 – start) / 2
    median = median + start
    left = start + 1
    if (array[median] – array[end-1])*(array[start]-array[median]) >= 0:
        swap(array,start,median)
    elif (array[end – 1] – array[median]) * (array[start] – array[end – 1]) >=0:
         swap(array,start,end – 1)
    pivot = array[start]
    for right in range(start,end):
        if pivot > array[right]:
            swap(array,left,right)
            left = left + 1
    swap(array,start,left-1)
    return left-1
def quickSortHelper(array,start,end):
    if start < end:
        splitPoint = partition(array,start,end)
        quickSortHelper(array,start,splitPoint)
        quickSortHelper(array,splitPoint+1,end)
def quickSort(array):
    quickSortHelper(array,0,len(array))
if __name__ == “__main__”:
    array = list(xrange(10))
    array.reverse()
    quickSort(array)
    print array

 

For finding “median-of-three” visit the following link:

Stack v2.0 – Python implementation

Since the version in the previous post sucks i have posted a new version of stack implementation. Note: Use built in version for max performances.
 

class Stack:
    def __init__(self):
        self.items = []
    def pop(self):
        return self.items.pop()
    def push(self,element):
        self.items.append(element)
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    def top(self):
        return self.items[len(self.items) – 1]
    def show(self):
        print self.items
s = Stack()
s.push(1)
s.push(55)
print s.top()
s.show()
s.pop()
s.show()
print s.top()

Finding “median-of-three” with two comparisons – Python implementation

def find_median(a,b,c):
    # (A-B)*(C-A) >= 0
    if (a – b)*(c-a) >= 0:
        return a
        #A
    # (B – A)*(C-B) >=0
    elif (b – a) * (c – b) >=0:
        return b
        #B
    else:
        #C
        return c
a = 1
b = 3
c = 7
print find(a,b,c)
a = 1
b = 6
c = 2
print find(a,b,c)

Depth-first search (DFS) recursive – Python implementation

def dfs_rec(graph,start,path = []):
    path = path + [start]
    for edge in graph[start]:
        if edge not in path:
            path = dfs_rec(graph, edge,path)
    return path
graph = {1: [2, 3],
         2: [1, 4, 5, 6],
         3: [1, 4],
         4: [2, 3, 5],
         5: [2, 4, 6],
         6: [2, 5]}
print dfs_rec(graph,1)

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