# Algorithms (any help?) Watch

Page 1 of 1

Go to first unread

Skip to page:

**I'm really bad at maths, I'm in my first year of uni and they've given everyone the same modules for the first year...does anyone understand algorithms or ANY of these questions because I'm truly baffled.**

Given username was absc941

Question 1.

Consider the following algorithm (note that a letter’s position in the alphabet starts from ‘a’ at position 1 and goes to ‘z’ at position 26).

Input is a list, with elements numbered from 1. Put

Given username was absc941

Question 1.

Consider the following algorithm (note that a letter’s position in the alphabet starts from ‘a’ at position 1 and goes to ‘z’ at position 26).

Input is a list, with elements numbered from 1. Put

*d = 1947*

1. For1. For

*i=1 to 7*

If theIf the

*ith element of the list is a letter then*

If the letter’s position in the alphabet is an odd number then

If the letter’s position in the alphabet is an odd number then

*d =**d + 11*

else

2. Returnelse

2. Return

*d.*

If theIf the

*ith element is numeral**n then*

*d =**d +**n.*

Now consider the list of characters in your login. Apply the algorithm above to this list, writing down the value of all variables involved in the algorithm each time one of these values changes.

Now consider the list of characters in your login. Apply the algorithm above to this list, writing down the value of all variables involved in the algorithm each time one of these values changes.

**Question 2**

Consider the list of all number from 0 to 99:

[0, 1, 2, 3, …, 97, 98, 99]

Consider the number given by the last two digits of your login. [Suppose your login was abcd123, then your number would be 23. If your login was abcd409, then your number would be 9.] Apply binary search (as defined in the lectures) to search for this number within the above list. ShowConsider the list of all number from 0 to 99:

[0, 1, 2, 3, …, 97, 98, 99]

Consider the number given by the last two digits of your login. [Suppose your login was abcd123, then your number would be 23. If your login was abcd409, then your number would be 9.] Apply binary search (as defined in the lectures) to search for this number within the above list. Show

*all your working from the search, in particular, keep track of the value of**u,**l and**i. Note that your list indices are number from 1, even though the values start from 0, that is, L1 = 0 and L23 = 22.*

**Question 3.**

Consider the following algorithm that applies to non-empty lists of letters: For list [L1,….,LConsider the following algorithm that applies to non-empty lists of letters: For list [L1,….,L

*n].*

1. Put1. Put

*m=27,**i=1.*

2. While2. While

*i <**n*

o Foro For

*j =**i+1 to**n*

IfIf

*distance(L**i,L**j) <**m then**m = distance(L**i,L**j)*

oo

*i =**i+1*

3. Return3. Return

*m.*

In the algorithm, the functionIn 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 logina) 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 sizeb) 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?*
0

reply

Report

#2

No one is going to do your homework for you, so you need to say what you're stuck with. Here are some pointers for the first two.

1) Go through your username (absc941) and if it's a letter in an odd position of the alphabet add 11 onto the number you have (d).

2) Your number is 41. You already have your sorted list (0-99) so all you need to do is perform a simple binary search. This means you're looking for the number 41. A binary search means you select the value in the middle of your list (the 50th value) which is 49 and you compare it with what you're after (41). As your target is lower than your selected value you know you're not interested in the values above the selected number, so you can throw them away. We then select the 25th value in the list (24) and compare it with your target. This value is too low, so we throw away the numbers that are lower and split the list in half again and compare, throwing away the values we know it can't be. We keep doing this until you get lucky and hit the value you're searching for or until you throw away every value but the one you're searching for.

1) Go through your username (absc941) and if it's a letter in an odd position of the alphabet add 11 onto the number you have (d).

2) Your number is 41. You already have your sorted list (0-99) so all you need to do is perform a simple binary search. This means you're looking for the number 41. A binary search means you select the value in the middle of your list (the 50th value) which is 49 and you compare it with what you're after (41). As your target is lower than your selected value you know you're not interested in the values above the selected number, so you can throw them away. We then select the 25th value in the list (24) and compare it with your target. This value is too low, so we throw away the numbers that are lower and split the list in half again and compare, throwing away the values we know it can't be. We keep doing this until you get lucky and hit the value you're searching for or until you throw away every value but the one you're searching for.

0

reply

(Original post by

No one is going to do your homework for you, so you need to say what you're stuck with. Here are some pointers for the first two.

1) Go through your username (absc941) and if it's a letter in an odd position of the alphabet add 11 onto the number you have (d).

2) Your number is 41. You already have your sorted list (0-99) so all you need to do is perform a simple binary search. This means you're looking for the number 41. A binary search means you select the value in the middle of your list (the 50th value) which is 49 and you compare it with what you're after (41). As your target is lower than your selected value you know you're not interested in the values above the selected number, so you can throw them away. We then select the 25th value in the list (24) and compare it with your target. This value is too low, so we throw away the numbers that are lower and split the list in half again and compare, throwing away the values we know it can't be. We keep doing this until you get lucky and hit the value you're searching for or until you throw away every value but the one you're searching for.

**Push_More_Button**)No one is going to do your homework for you, so you need to say what you're stuck with. Here are some pointers for the first two.

1) Go through your username (absc941) and if it's a letter in an odd position of the alphabet add 11 onto the number you have (d).

2) Your number is 41. You already have your sorted list (0-99) so all you need to do is perform a simple binary search. This means you're looking for the number 41. A binary search means you select the value in the middle of your list (the 50th value) which is 49 and you compare it with what you're after (41). As your target is lower than your selected value you know you're not interested in the values above the selected number, so you can throw them away. We then select the 25th value in the list (24) and compare it with your target. This value is too low, so we throw away the numbers that are lower and split the list in half again and compare, throwing away the values we know it can't be. We keep doing this until you get lucky and hit the value you're searching for or until you throw away every value but the one you're searching for.

Posted from TSR Mobile

0

reply

Report

#4

Ok, so a more in depth explanation of the first one...

Each letter of the alphabet is assigned a number based on it's position. As A is the first number it is 1, B is the second so it's 2, C is 3, D is 4 and so on all the way to Z which is 26.

The username is 7 characters long: absc941

We're given a number (called

Our algorithm is:

The algorithm is an if statement checking whether the character we're looking at is a letter. It is so we continue with the next instruction.

We've now done our first iteration through the loop, so now

You do a similar thing if the character is a number in that you add

Each letter of the alphabet is assigned a number based on it's position. As A is the first number it is 1, B is the second so it's 2, C is 3, D is 4 and so on all the way to Z which is 26.

The username is 7 characters long: absc941

We're given a number (called

**d**) and we're told it's**1947**Our algorithm is:

**So this means we're going to do something 7 times (and our username is 7 characters long...)***For**i=1 to 7*

**This means as we're iterating through our loop we should check the corresponding letter. So for the first run through of the algorithm we look at the first character, the second run through the second character, until we've gone 7 iterations and we're looking at the last character in the username.***If the**ith element of the list is a letter then*

The algorithm is an if statement checking whether the character we're looking at is a letter. It is so we continue with the next instruction.

**So we need to take the number that is assigned to the letter and check whether it is odd. As***If the letter’s position in the alphabet is an odd number then*

**A**s number is**1**it is odd so we must continue with the next instruction.**This means***d =**d + 11*

**d**has 11 added onto it.We've now done our first iteration through the loop, so now

**i**becomes 2 and we look at the second character. You need to check if it's a letter. If it is then you need to check if the number assigned to it is odd and if it is**add 11**onto**d**. You then move onto the next character and do the same until you've done it to all the characters in your username. If the number assigned to the letter is even then you should just return the current value of**d**.You do a similar thing if the character is a number in that you add

**n**to**d**.**n**is the number you're currently checking.
2

reply

Report

#5

(Original post by

Ok, so a more in depth explanation of the first one...

Each letter of the alphabet is assigned a number based on it's position. As A is the first number it is 1, B is the second so it's 2, C is 3, D is 4 and so on all the way to Z which is 26.

The username is 7 characters long: absc941

We're given a number (called

Our algorithm is:

The algorithm is an if statement checking whether the character we're looking at is a letter. It is so we continue with the next instruction.

We've now done our first iteration through the loop, so now

You do a similar thing if the character is a number in that you add

**Push_More_Button**)Ok, so a more in depth explanation of the first one...

Each letter of the alphabet is assigned a number based on it's position. As A is the first number it is 1, B is the second so it's 2, C is 3, D is 4 and so on all the way to Z which is 26.

The username is 7 characters long: absc941

We're given a number (called

**d**) and we're told it's**1947**Our algorithm is:

**So this means we're going to do something 7 times (and our username is 7 characters long...)***For**i=1 to 7*

**This means as we're iterating through our loop we should check the corresponding letter. So for the first run through of the algorithm we look at the first character, the second run through the second character, until we've gone 7 iterations and we're looking at the last character in the username.***If the**ith element of the list is a letter then*

The algorithm is an if statement checking whether the character we're looking at is a letter. It is so we continue with the next instruction.

**So we need to take the number that is assigned to the letter and check whether it is odd. As***If the letter’s position in the alphabet is an odd number then*

**A**s number is**1**it is odd so we must continue with the next instruction.**This means***d =**d + 11*

**d**has 11 added onto it.We've now done our first iteration through the loop, so now

**i**becomes 2 and we look at the second character. You need to check if it's a letter. If it is then you need to check if the number assigned to it is odd and if it is**add 11**onto**d**. You then move onto the next character and do the same until you've done it to all the characters in your username. If the number assigned to the letter is even then you should just return the current value of**d**.You do a similar thing if the character is a number in that you add

**n**to**d**. Though your question doesn't say what**n**is so it's possibly an error and it means**i**or it's in another part of your question...**n**refers to the value of the character if it's a

**n**umber

EDIT: OP actually says "numeral

**n**"

1

reply

But thank you so much for your help, I will go over this asap and hopefully understand it better than before, also are there any pointers on question three because that seems even worse than the first two? If not thank you once again for the detailed explanations you've written, really helped me out there

0

reply

Report

#8

You would add 9.

Have a try at question 3 and if you need help explain which part you're stuck on. It's a similar problem, you need to go through each character and do something with it.

Have a try at question 3 and if you need help explain which part you're stuck on. It's a similar problem, you need to go through each character and do something with it.

0

reply

(Original post by

You would add 9.

Have a try at question 3 and if you need help explain which part you're stuck on. It's a similar problem, you need to go through each character and do something with it.

**Push_More_Button**)You would add 9.

Have a try at question 3 and if you need help explain which part you're stuck on. It's a similar problem, you need to go through each character and do something with it.

0

reply

Report

#10

I'm guessing your lecture notes or beginning of the worksheet will say what L U and I is but I don't know. I'd guess that L is the list index you're currently using.

You'll need to write down what you're doing step-by-step, most likely.

You'll need to write down what you're doing step-by-step, most likely.

0

reply

(Original post by

I'm guessing your lecture notes or beginning of the worksheet will say what L U and I is but I don't know. I'd guess that L is the list index you're currently using.

You'll need to write down what you're doing step-by-step, most likely.

**Push_More_Button**)I'm guessing your lecture notes or beginning of the worksheet will say what L U and I is but I don't know. I'd guess that L is the list index you're currently using.

You'll need to write down what you're doing step-by-step, most likely.

– a list of

*n*elements being searched [L1,….,L

*n*]

– the quarry, K

– a variable

*i*. This variable holds the current position (index) in the list being searched

– variable

*found*a boolean variable for whether or not the quarry has been found.

– the algorithm terminates immediately when it finds K (or when there are no items left)

Not too sure what the "quarry" part means?

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top