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 nonempty 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 steps. I believe that this has a complexity of in that case. 

Tags 
algorithms 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Analysis of algorithms, please help  OriaG  Applied Math  1  August 28th, 2013 04:41 AM 
Mod Algorithms.  vamsi  Number Theory  0  February 25th, 2013 10:35 PM 
career with finding algorithms?  dusttrust  Applied Math  6  October 16th, 2011 02:22 PM 
Data structure and Algorithms  Christ1m  Computer Science  2  March 23rd, 2011 04:36 PM 
Divisor Counting Algorithms  kenzi_x  Number Theory  5  August 26th, 2009 07:17 PM 