Brute force , Need help

Question

Hi guys I'm a junior student and I had a course called The Design and Analysis of Algorithms,The course is cool but the instructor is not any way, I dont understand the brute force and how to count the number of operations and how to count the time complexity(worst,best,avg), I tried to search for it on the net but each time I end with the big-o notation and the divide and conquer which i dont want. If any of you guys can download the instructor slide from this link and see what I'm talking about ....

the slide

I really need your help on this , and I promise i will do my best

Answer 1

Brute force is a class of "algorithms" (or plainly "way of doing things") where you don't try to be clever, just dumb search. Example: if you want to look up a phone number in the phone book, the clever solution would be to observe that all entries are sorted by last name, and directly look up the correct letter, etc. The brute force solution would be to read the phone book from the start, checking every single name and stopping when the right name is found.

Answer 2

Brute forcing is the task of testing all possible configurations of a specific problem and testing if one of them matches the properties of a solution.

Consider a 4 digit pin code. If you lose it, you can test all possible codes from 0000 to 9999 to find the correct code. This is a kind of brute forcing.

The same thing can be used to solve some computer science problems such as 0/1 knapsack problem in which, a thief wants to find out what to steal. Every object has value v[i] and weight w[i]. He or she wants to find out the combination that provides maximum value and has less weight than "W". A possible solution to this problem is to consider all combinations of objects and find the value and the weight of each combination and then select the optimal one.

Answer 3

You might get a bit out of watching the first few lectures of this series on algorithms.

Answer 4

Can i have an example on the selection sort and bubble sort how to count the time complixity and how to count the operations and what is the traveling sales man problem

The Selection sort algorithm is available in pseudocde from Wikipedia, as is the Bubble Sort. The time complexity is computed by the number of times it takes the algorithm to run through until it gets the right answer.

The Traveling Salesman problem is a classic problem in computer science that interrelates the algorithm's execution time with figuring out the answer to the question.

To wit:

The problem is: given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?

If I try to use an algorithm to bruteforce the best route, it'll take a really long time on any route bigger than the simplest route. That's where Big(O) comes in, it shows me how each algorithm I'd choose would affect how long it'd take me to get the answer.

I posted this answer based off of the comments you left for other answers. For what it's worth, Big-O notation is exactly what you want, it's the indicator of how long your algorithm will take to execute.