Algorithms

Recursion and backtracking --

• Process of defining a function or calculating a number by repeated application of an algorithm.

• Recursion — make correct set of choices and you end up at the solution

• Backtrack — extension of recursion where if you reach dead end or otherwise discover that you have made an incorrect choise you have to backtrack to previous descision point and try a different path.

Sorting algorithms --

• arranges elements of a list in certain order

• sometimes sorting efficiently reduces the complexity of the problem, mostly in case of searching cases

Searchin algorithms --

• Find for a particular element usually from DB, simple data elements in arrays, texts in files etc.

Selection algorithms --

• Finding Kth smalest largest number in a list

• Multiple algorithms

String algorithms --

• Algorithms based on strings

Greedy algorithms --

• Single minded algorithms.

• Process that looks for simple, easy to implement solutions to complex multip step problems by deciding which next step will provide the most obvious benifit

• idea is to perform single procedure over and over again untill it can't be done any more and what kind of result it will produce

Divide and conquer --

• divide— breaks the problem into serveral subproblems that are similar to the original problem but smaller in size

• Conquer— solve the subproblem recursively

• Base case — if subproblem are small enout then solve them directly

• Combine — the solutions to create a solution for the original problem.

• Master algorithm for divide and conquer --

  • divide the problems in to subproblems each of which is part of the original problem and then perform some additional work to compute the final answer.

  • ex - For each of the following recurrence give an expression for the runtime T(n). IF the recurrence can be solved with the master theorm

  • 
  • Problem -1 1'(11) = 3T (11/2) I · 11 2

    Solution: T(11) = 3T (n/2) + 11 2 = > T (11) = 0(n2) (M aster Theore m Case 3 .a)

    Proble m-2 T(n) = 4T (11/2) + 11 2

    Solution: 'f'(n) = 4T (n/2) + n2 => T (n) = 0 (11210911) (Master Theorem Case 2 .a)

    Problem-3 T(n) = T(n/2) + 112

    Solution: '/'(11) = '/'(11/2) + 112 = > <9(112) (Master Theorem Case 3.a)

    Problem -4 T(11) = 211 '/'(11/2) + 11 11

    Solution: '/'(11) = 2"T(n/2) + 11" => Docs not apply (a is not constant)

    Problcm -5 '/'(11) = 167'(11/'1) + n

    Solution: T(n ) = 167' (n/4) + n => T(n) = 0(n2) (Master Theorem Case 1)

    Problem -6 T(n ) = 2'/'(11/2) + 11/0911

    Solution: T(n) = 2T(n/2) + 11/0911 => T(n) = 0(11/og'ln) (M aster Theorem Case 2.a)

    Problem-7 T(n) = 2T(n/2) + 11//0911

    Solut ion: 7'(11) = 27'(n/2) + 11/lo911 = > 7'(11) = S(nlo,qlogn) (Muster Theorem Case 2. b)

    Problem-8 T(n) = 2T (11/4) + no si

    Solution: T(n) = 2T(n/4) + n°·5 1 => 'l' (n) = 8(11°·

    51 ) (Master Theorem Case 3.b)

    Problem -9 T(n) = O.ST(n/2) + 1/n

    Solution: '/'(11) = O.ST(n/2) + l/11 => Does not apply (n < I)

    Problcm -10 T (11) = 6T (11/3) 1 11 l logn

    Solution: 'f'(n) = 6T(n/3) 1- 112 10911 => T(11) = <9(112/o,q11) (Ma:>ter Theore m Case 3.a)

    Problem -11 T (11 ) = 64T(n/U) - 11 210911

  • Solution: T(11) = 64T(n/8) - 11 210911 = > Docs not apply (function is not positive)

    Problem-12 T (n) = 7T(n/3) + 11 2

    Solut ion: T(11) = 7T(n/3) + n2 => T(n) = E> (n2) (M aster Theorem Case 3 .as)

    Problem -13 T (11) = 47' (n/2) + logn

    Solut ion: 7'(11) = 47'(n/2) + IO.CJ11 - > 'f(11) = <9(112 ) (Mus ter Theorem Case I)

    Problem -14 7'(n) = 16'/'(n/4)+ 11!

    Solution: T(n) = 16T (n/4) + 11! - > T(n) = 0(11!) (Master Theorem Case 3.a)

    Problem -15 T (11) = .f2T (n/2) + logn

    Solut ion: '/'(11) = ..fi.T (n/2) + logn => T (n) = E>(..fii) (Master Theorem Case 1)

    Problem -16 T (n) = 3'f' (11/2) + 11

    Solution: T(11 ) = 3T (n/2) + 11 -> T(n) = 0(111"0:1) (M aster Theorem Case 1)

    Problcm-17 T(n) = 3T (11 /3) + ..{ii.

    Solution: '/'(11) = 3T (n/3) + Jn = > T(11) = <9(11) (M aster Theorem Case 1)

    Problem-18 T(n) = 4T (n/2) + en

    Solution: '/'(11 ) = 47' (n/2) + en = > T(n) = 0(n2) (Mas ter Theorem Case l)

    Problem-19 T(n) = 3T (11/4) + 11/0911

    Solution: T(11) = 3T (n/4) + 11/0.qn => T(11) = 0(11/og11) (Muster Theorem Case 3.a)

    Problem-20 T (11) = 3T (n/3) + 11/2

    Solution: T(11) = 3T (n/3) I- 11 /2 = > T (11) = 8(11/o911) (M aster Theorem Cusc 2.a)

Dynamic programming --

• Technique to solve in cases when all above solutions have failed.

• DP is a simple technique but it can be difficult to master

Mislanious —

• Bitwise tracking —