Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MCD4710 Introduction to Algorithms and Programming

Tutorial 2

Warm-up

Do not solve these questions by running in Python.

Conditionals: What is returned by each function call?

a) def  is_prime(x):

response = ‘unknown’

if x%2  == 0:

response  = ‘is even’

elif x%3 == 0 or x%5 == 0 or x%7 == 0:

response   = ‘is composite’

elif  x  < 13:

response = ‘is prime’

else:

response = ‘is too big’

return  response

is_prime(15)

b) def  is_date(date,  month):

if (month==4 or month==6 or month==9 or month==11):

return 0

if month==2:

return date<=28

return (0

is_date(31, 9)

is_date(8,  7)

Code trace: What is returned by each function call?

1) def mystery1(word, letter):

i = 0

while  i < len(word):

if word[i] == letter:

return True

i +=  1

return False

mystery1(‘anyway’, ‘e’)

2) def mystery2(word, letter):

i = 0

count  =  0

while  i < len(word):

if word[i] == letter:

count += 1

i +=  1

return count

mystery2(‘anyway’, ‘a’)

Task 1 - Real Roots

1.    Write an algorithm in English for finding the real roots (x-intercepts) of a quadratic equation ax2  + bx + c = 0 for arbitrary real coefficients a, band c. Things to note:

(a)  The quadratic formula is

(b) There exist 0, 1, or 2 real roots in any quadratic equation, depending on what is yielded by b2  - 4ac .

(a) The number of real roots affectshow the quadratic formula should be used.

(b) Determining how many real roots you are trying to find should occur somewhere in the algorithm.

2.  Structure your algorithm as a function real_roots(a, b, c) which takes as input the

three coefficients of a polynomial and returns a list of the roots. If there are no roots, the list should be empty.

3.  Implement your algorithm in Python.

Task 2 - Unscrambling   Code

In this task you will try to unscramble lines of code to create a function with the desired behaviour. Feel free to either write each line onto a sheet of paper and cut it into separate lines, or to simply write down the unscrambled function directly. Remember to ensure your indentation is correct.

Extension: Some of these implementations are unnecessarily verbose. Try to make them more succinct.

Part A - Magic Number

Arrange the lines such that you produce a function that takes three integers, x, y, and n, that returns True if one of x or y is n, or if x and y add to n, or if their difference is   n.

❼               return True

❼               return False

❼               return True

❼          else:

❼               def magic num(x, y, n):

❼               return True

❼ elif x+y == n:

❼ if x == n or y == n:

❼ elif x-y == n or y-x == n:

Part B - Icecream

Arrange the lines such that you produce a function that takes an integer, x, and a boolean, summer, that returns the number of icecreams you need to buy. The input x tells you how many icecreams you already have, and summer tells you whether it is summer. You must always have at least 2 icecreams, except during summer when you must have 10. If you have enough or more than enough icecreams, you do not need to buy any.

❼               return 0

❼ if 10-x > 0:

❼ return 2-x

❼ def icecreams(x, summer):

❼ return 10-x

❼ elif 2-x > 0:

❼ if summer:

Part C - Rounding

Arrange the lines such that you produce a function that takes an integer n and returns that number rounded to its nearest 10. If the number in the ones column is greater than 5, round up; if the number in the ones column is less than 5, round down. If the number in the ones column is 5, round in such away that the number in the tens column is even.

❼ num = n-remainder

❼             elif remainder > 5:

❼ if remainder < 5:

❼ if num//10%2 == 0:

❼ return num

❼          else:

❼ return num

❼ remainder = n%10

❼ return num + 10

❼          else:

❼ return num + 10

❼ def rounding(n):

Extension Questions

1.  Describe the standard algorithm for finding the decimal representation of a positive binary number.  (For example, how to convert 100101 to 37. If you are unsure how to convert a binary number to its decimal representation, ask your tutor for guidance.) Write the algorithm in English, and then implement your algorithm in Python.

2.  Describe in English an algorithm for taking an unsorted sequence of numbers and sorting them into ascending order. Be as specific as possible.

3.  Use these puzzles to start practicing open-ended problem solving. None of these are examinable, and solutions will not be provided.

a) Over a 24 hour period, how many times will the hour hand and the minute hand overlap on an analogue clock?

b)  99 unique numbers between 1 and 100 are listed one by one, with five second pause after every number. If you are not allowed to take any notes, what is the best way to determine which is the missing number?

c) You have a drawer with 10 pairs of black socks and 10 pairs of white socks.  How many times do you need to grab a sock, to be sure that you have a matching pair?

d) Is the number 9991 prime?

e) There are n closed doors in a hallway, numbered sequentially from 1 to n. You walk down the corridor n times, and at the end of the corridor you run back to the start. On your ith trip down the hall you toggle every ith door (open it if it’s closed, close if it’s opened). After the last trip down the corridor, which doors are opened, and which are closed?

f)  You are trying to get a wolf, a goat, and a cabbage across a river. You have a boat that can only hold two entities at once. If you leave the wolf alone with the goat, the wolf will eat the goat. If you leave the goat alone with the cabbage, the goat will eat the cabbage. What do you do?

g) Mario asks a tutor to conduct a poll at their consultation for which day of the week the final exam should be held on. The tutor reports back the following: 73% say Monday, 58% say Wednesday, and 32% say Friday. The tutor admits they were a little lazy in their reporting, and simply dropped all decimal values (i.e. both 5.01% and 5.99% would have been reported as 5%). Mario realises two things: firstly, some students must have voted more than once; and secondly, he can now see whether the consult was well attended. What was the minimum number of students at the consult?