My Math Forum Algorithms (any help?)

 Computer Science Computer Science Forum

 February 2nd, 2014, 09:21 AM #1 Newbie   Joined: Feb 2014 Posts: 1 Thanks: 0 Algorithms (any help?) Hi guys, I've just started algorithms in my University course, the module is Computation and Reasoning, one part of it is Algorithms, I don't get these questions at all, any help? Given login - absc941 Question 3. Consider the following algorithm that applies to non-empty lists of letters: For list [L1,….,Ln]. 1. Put m=27, i=1. 2. While i < n o For j = i+1 to n If distance(Li,Lj) < m then m = distance(Li,Lj) o i = i+1 3. Return m. In the algorithm, the function distance(?,?) is given by the absolute difference between the position in the alphabet of ? and ?. For example, distance(e, v) = 17 and distance(f, c) = 3. a) Apply this algorithm with input list consisting of the four letters in your login reversed. That is, for login abcd123, the input is [d,c,b,a]. Your answer should consist of a table of values for i, j and m after each call to the “If…” line. b) For input of size 5, how many steps will this algorithm take? How many for the general case where the input is of size n? What complexity class is it in?
 February 7th, 2014, 01:16 PM #2 Senior Member   Joined: Mar 2012 From: Belgium Posts: 654 Thanks: 11 Re: Algorithms (any help?) a) is pretty straightforward and just some work. If you have a more specific question then we might help you out. b) In case n=5 then the while loop will be executed 4 times. The first time (when i=1) the for loop will be executed 4 times. The second time (when i=2) 3 times. then 2 times and then 1. Thus the algorithm will take 4+3+2+1=10 steps. In general it can be said that it will run $\frac {n^2-n}{2}$ steps. I believe that this has a complexity of $O$$n^2$$$ in that case.

 Tags algorithms

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post OriaG Applied Math 1 August 28th, 2013 04:41 AM vamsi Number Theory 0 February 25th, 2013 10:35 PM dusttrust Applied Math 6 October 16th, 2011 02:22 PM Christ1m Computer Science 2 March 23rd, 2011 04:36 PM kenzi_x Number Theory 5 August 26th, 2009 07:17 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top