iKnowAll
Badges: 0
Rep:
?
#1
Report Thread starter 5 years ago
#1
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 d = 1947
1. For i=1 to 7
If the ith element of the list is a letter then
If the letter’s position in the alphabet is an odd number then
d = d + 11


else



2. Return d.


If 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.



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. 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,….,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?
0
reply
Push_More_Button
Badges: 10
Rep:
?
#2
Report 5 years ago
#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.
0
reply
iKnowAll
Badges: 0
Rep:
?
#3
Report Thread starter 5 years ago
#3
(Original post by 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.
Hi..thanks for replying I just don't understand how to work any of it out I just need explanation especially on the first one I don't really understand the basics and textbooks are just too complicated imo :dontknow:

Posted from TSR Mobile
0
reply
Push_More_Button
Badges: 10
Rep:
?
#4
Report 5 years ago
#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 d) and we're told it's 1947

Our algorithm is:
For i=1 to 7
So this means we're going to do something 7 times (and our username is 7 characters long...)
If the ith element of the list is a letter then
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.
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.
If the letter’s position in the alphabet is an odd number then
So we need to take the number that is assigned to the letter and check whether it is odd. As As number is 1 it is odd so we must continue with the next instruction.
d = d + 11
This means 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
TheGrinningSkull
Badges: 18
Rep:
?
#5
Report 5 years ago
#5
(Original post by 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:
For i=1 to 7
So this means we're going to do something 7 times (and our username is 7 characters long...)
If the ith element of the list is a letter then
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.
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.
If the letter’s position in the alphabet is an odd number then
So we need to take the number that is assigned to the letter and check whether it is odd. As As number is 1 it is odd so we must continue with the next instruction.
d = d + 11
This means 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...
To add to your last point, it could be n refers to the value of the character if it's a number

EDIT: OP actually says "numeral n"
1
reply
Push_More_Button
Badges: 10
Rep:
?
#6
Report 5 years ago
#6
Ahh well spotted, missed that.

Have edited it in, thanks.
0
reply
iKnowAll
Badges: 0
Rep:
?
#7
Report Thread starter 5 years ago
#7
(Original post by Push_More_Button)
n is the number you're currently checking.
Do you mean I would add 9 on once I get to the 5th character or add 5 itself?

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
Push_More_Button
Badges: 10
Rep:
?
#8
Report 5 years ago
#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.
0
reply
iKnowAll
Badges: 0
Rep:
?
#9
Report Thread starter 5 years ago
#9
(Original post by 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.
Thanks I'll have a shot, also in question two, what does it mean keep track of value U, L and I? I understand the rest of the question but I'm slightly confused as to what those three letters mean
0
reply
Push_More_Button
Badges: 10
Rep:
?
#10
Report 5 years ago
#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.
0
reply
iKnowAll
Badges: 0
Rep:
?
#11
Report Thread starter 5 years ago
#11
(Original post by 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.
I managed to finally get some more time to look at the questions I still don't understand question three to be honest, also I did get some more information about the binary search:


–  a list of n elements being searched [L1,….,Ln]
–  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
Push_More_Button
Badges: 10
Rep:
?
#12
Report 5 years ago
#12
The quarry is the thing you are looking for.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • Regent's University London
    Postgraduate Open Evening Postgraduate
    Thu, 19 Sep '19
  • Durham University
    Pre-Application Open Days Undergraduate
    Fri, 20 Sep '19
  • Loughborough University
    Undergraduate Open Day Undergraduate
    Fri, 20 Sep '19

What's your favourite genre?

Rock (190)
24.05%
Pop (192)
24.3%
Jazz (30)
3.8%
Classical (46)
5.82%
Hip-Hop (150)
18.99%
Electronic (53)
6.71%
Indie (129)
16.33%

Watched Threads

View All