Algo and Complex

• Brute Force Algorithms


  Straightforward methods of solving a problem that rely on sheer computing power and trying every possibility rather than advanced techniques to improve efficiency
• Brute Force Algorithms


  • Used by attackers to break into any website's data or systems by generating every possible combination of the password-protected information
  • Relies on the computational power of the machine to try every possible combination to achieve the target
• Exhaustive Search


  Yields all possible solutions to a problem
• Generate and Test


  Yields all possible solutions to a problem
• Brute Force algorithm is a simple problem solving technique that is easy to implement and will always come up with a solution if exists
• The computational cost of Brute Force algorithm is directly proportional to the number of candidate solutions, i.e. it grows as quickly as the problem size increases
• Brute Force algorithm is ideal to use when the problem size is limited and small and does not have complex and large problem sets
• The time complexity of Brute Force algorithm would be equal to O (n) since it takes the steps, which are equal to the words in the dictionary
• Brute Force Approach


  Going through all the possible solutions
• Brute Force approach is one of the easiest way to solve a problem but in terms of time and space complexity will take a hit
• Padlock with 4 digits, each from 0-9

  • 10,000 possible combinations

  
• Brute Force Algorithm


  • Intuitive, direct, and straightforward technique of problem-solving in which all the possible ways or all the possible solutions to a given problem are enumerated
  • Many problems solved in day-to-day life using the brute force strategy, for example exploring all the paths to a nearby market to find the minimum shortest path
  • Arranging the books in a rack using all the possibilities to optimize the rack spaces
• Brute force algorithm is a technique that guarantees solutions for problems of any domain helps in solving the simpler problems and also provides a solution that can serve as a benchmark for evaluating other design techniques, but takes a lot of run time and inefficient
• Brute Force can be applied to a wide variety of problems including trial and error problems, searching a number, performing some sort of sorting on the given input unsorted lists, find the integers between some ranges given any condition, find out the largest number
• Brute Force algorithms are popular among the attackers to steal confidential information by using a set of possible candidates to attack on some targeted information or leaked data
• Security attack tools using Brute Force


  • Aircrack-ng
  • John the Ripper
  • Rainbow Crack
  • L0phtCrack
  • Ophcrack
  • Hashcat
  • DaveGrohl
  • Ncrack
  • THC Hydra
• Greedy Algorithm


  An approach for solving a problem by selecting the best option available at the moment, without worrying whether the current best result will bring the overall optimal result
• Greedy Algorithm


  • Never reverses the earlier decision even if the choice is wrong
  • Works in a top-down approach
• Greedy algorithm may not produce the best result for all the problems as it always goes for the local best choice to produce the global best result
• Problems that can be solved using Greedy Algorithm


  • Have the Greedy Choice Property - optimal solution can be found by choosing the best choice at each step without reconsidering the previous steps
  • Have Optimal Substructure - the optimal overall solution corresponds to the optimal solution to its subproblems
• Greedy algorithms do not always give an optimal/feasible solution
• Greedy Algorithm


  1. To begin with, the solution set (containing answers) is empty

  2. At each step, an item is added to the solution set until a solution is reached

  3. If the solution set is feasible, the current item is kept

  4. Else, the item is rejected and never considered again
• Right child


  • Weight is 3
• Left child


  • Weight is 2
• Largest path


  Optimal solution is 3
• Greedy algorithm


  Choose 3
• Final result is 20 + 3 + 1 = 24
• There is another path that carries more weight (20 + 2 + 10 = 32)
• Greedy algorithm


  1. Solution set is empty

  2. Add item to solution set until solution reached

  3. If solution set is feasible, keep current item

  4. Else, reject item and never consider again
• Greedy algorithm solution

  Create empty solution set

  2. Start with sum = 0

  3. Select largest coin (5) until sum > 18

  4. Add 5, 5, 5, 2, 1 to solution set

  5. Final solution set is {5, 5, 5, 2, 1}
• Greedy solution does not always give optimal solution
• Greedy algorithm to find best route


  Start from source vertex

  2. Pick vertex with minimum edge weight

  3. Add vertex to tree if no cycle

  4. Keep adding fringe vertices until destination