1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete algorithms.

  1. Nov 29, 2005 #1
    I have a project to do on algorithms, and as far as I can tell, the project is due before we cover the topic :p.

    My textbook only makes a slight reference to what an algorithm is :(.

    Can anyone point me in the direction of a website or book that tells me all there is to know about algorithms?
  2. jcsd
  3. Nov 30, 2005 #2
    Algorithms is a pretty large subject: You may want to be a bit more specific. Algorithms themselves are just set procedures that will produce an output to a specific task or problem. If you want to understand the efficiency of an algorithm I suggest you look up "big o notation". I think that it's important to note that algorithms can be counterintuitive in that the shortest algorithm is rarely the fastest for a given problem.

    An example of a classic algorithm would be Euclid's algorithm for finding the greatest common factor of two numbers, which uses the idea that gcf(y, x) = gcf(x, y mod x).

    A good example of the problem of choosing an algorithm is the problem of sorting an array of numbers in a particular order using a computer program. There are many options to accomplishing this task. One of the most inefficient methods would be simply to ask the computer to produce every possible permutation of the array and to select the sorted one (run time o(n!)). A typical high school level implementation of that task would involve the bubblesort algorithm, which checks each element and only the elements at a position in the array greater than the one being checked and will swap the two if the two are not sorted according to the method you want the array to be sorted (run time o(n^2)). There are still faster ways, such as quicksort, which has a run time of o(n*log(n)), and calls for a sort of complicated to explain recursive sorting of the array into two partitions consisting of numbers greater than a certain number (called the pivot) and numbers less than that number, and then proceeds to recurse down until each partition is one element. Quicksorts are typically 20 lines of code in most programming languages compared to maybe 5 lines for bubblesort.

    I hope I at least gave you some keywords to look up in your search.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook