Skip to content

Design Techniques I

Divide and Conquer: Quick sort

TC -> \(\Omega(nlogn)\) | \(O(n^2)\) - Pivot element is selected and positioned to it's sorted spot - Recursion called on 0,sortedPosition and sortedPostion+1 to n

Strassen's Matrix Multiplication

  • A simple algo to multiply two matrices requires 3 for loops i.e. \(O(n^3)\).
  • base condition will be a 2x2 matrix as it can be solved in constant time with the 4 equations such as \(\(c_{11} = a_{11}*b_{12} + a_{12}* b_{21}\)\)
  • Works for a matrix with dimension a power of 2.
  • Strassen wrote 7 equations P,Q,R,S,T,U,V using which we can perform the 4 constant operations by using 7 instead of 8 multiplications
  • sooo? The benefit is it reduced the time complexity of the matrix multiplication from \(O(n^3)\ to \ O(n^{2.81})\)

Finding Convex Hull

  • Small convex polygon that contains all points in the plain.

Greedy Algorithms

Activity Selection Problem

  • Given n activities with start time and end time
  • You can only do 1 activity at a time
  • Return the maximum number of activities you can do
  • Algo
    • Sort the activities by their finish time
    • Select the first activity if not already selected
    • LOOP
      • iterate through the sorted activities array and reject any activities whose start time is less than current activities end time
      • Select the activity whose start time >= current activity's end time

fractional and 0/1 Knapsack problem

  • Fractional will give optimal solution
  • 0/1 May not give optimal solution with Greedy
  • Input -> n objects, profit and weight array
  • Algo
    • calculate profit per unit weight weight i.e profit/weight
    • select the objects with highest profit by weight
    • you can take fractional weight if less capacity is remaining in the knapsack

Job Sequencing with Deadlines

  • Given n jobs with their profits and deadlines
  • Return the jobs that you can do which would give maximum profit
    • sort the jobs based on their profit
    • assign into the last possible slot for the current job, if already filled check the left slot of it!
    • repeat until job slots are exhausted

Optimal Merge Pattern

  • Given n array sizes that have to be merged into a single array; find minimum required operations
  • Sort the size array in ascending order
  • merge the elements with the least value

Huffman Coding

  • Total cost = optimal merge summation + table cost
  • table cost = No. of characters * 8 + total number of bits for code

Dijkstra Algorithm

if ( d\[v] > d\[u] + c(u,v)  )
    d\[v] = d\[u] + c(u,v)

Prims and Kruskal's algorithm

  • No of spanning tree's possible(\(\\^{|Edges|}C_{|Vertex| -1}\)\)
    • O(ElogV)
    • O(ElogV) using min heap
  • PRIMS
    • From the graph select the minimum cost edge
    • For the remaining procedure, select the minimum edge but make sure it's connected to the already selected vertex
    • Continue till all vertex are reached
  • KRUSKALS
    • always select the minimum cost edge
    • not necessarily connected to previously selected
    • If minimum edge is forming a cycle, discard it and not select it