My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
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?
iKnowAll is offline  
 
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.
gelatine1 is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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





Copyright © 2018 My Math Forum. All rights reserved.