User Name Remember Me? Password

 Computer Science Computer Science Forum

 February 2nd, 2014, 08: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, 12: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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post OriaG Applied Math 1 August 28th, 2013 03:41 AM vamsi Number Theory 0 February 25th, 2013 09:35 PM dusttrust Applied Math 6 October 16th, 2011 01:22 PM Christ1m Computer Science 2 March 23rd, 2011 03:36 PM kenzi_x Number Theory 5 August 26th, 2009 06:17 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      