# MAT2440 Discrete Structures & Algorithms I

Professor Kate Poirier, Spring 2017

Your final grades have been submitted to the registrar. You can see the grade breakdown in Blackboard’s gradebook. Check the OpenLab grading page for the grading scheme. The item labelled “Spring Break Project” is the maximum of two grades, either your code-breaking assignment or your Quiz #7 (the one based on your independent study over spring break).

A number of you have final exam grades that are better than your in-class test grades. I’m glad you prepared so well! Please remember that you are all capable of earning the grades that you want, it just takes consistent hard work throughout the semester. Have a great summer and best of luck in the future!

FRONT OF ROOM

Mahrukh Chris Ka Yat Juliano  Syed          Tariq Javed  Christian Francis Shannon

Lillian Kemoy Mario David Kazi         Yaqoob Joshua  Shah Kenny Jose

2) MNULNYX ZLIG NBY VINNIG HIQ QY BYLY. MNULNYX ZLIG NBY VINNIG HIQ GS QBIFY NYUG BYLY.

a) +6

b) Unencrypted ABCDEFGHIJKLMNOPQRSTUVWXYZ
Encrypted       GHIJKLMNOPQRSTUVWXYZABCDEF

c) STARTED FROM THE BOTTOM NOW WE HERE. STARTED FROM THE BOTTOM NOW MY WHOLE TEAM HERE.

Using hashing function h(k)=k mod 5 to determine the memory locations of the following identification numbers.

ID Number            Memory Location

034567891            1

183211232            2

220195477            2, but 2 is taken, so 3

987255355            0

104578890            0 , but 0 is taken, so 4

The course outline contains a list of all textbook sections that can appear on the final exam. Your exam will not have questions from 11.3, 11.4, or 11.5, but all other sections are fair game.

Remember that Tuesday’s class is reserved as a review session. I am not preparing anything for this class. You should pretend that the final exam is on Tuesday. That way we can use the time to discuss only the topics that you all are still struggling with. Practice problems from the homework, quizzes, and tests.

I will hold my usual office hours on Tuesday: 11am-1pm in N707.

Your final exam will be given during usual class time on Thursday, May 25 (only one more week!).

Please go ahead and submit solutions for Test #3 questions as OpenLab posts. Don’t forget to select the “Test #3” category from the right-hand side of the screen before publishing your post.

The deadline to post is 2:15pm on Thursday, May 25.

Just a reminder…from section 5.4

• subtract #30, 46, 50-52

The updated homework list is then

#1-5 (odd), 7-10, 16, 18, 21, 22, 29, 36

This week’s math club talk is about Turing Machines and should be of interest to those studying computer science or computer systems.

The club meets on Thursdays in N719 from 12:45 to 2pm (and provides you with free pizza!).

You can find the abstract for all the talks here: https://sites.google.com/site/mathclubcitytech/

2)

a) Determine whether f is invertible. If f is invertible, find it’s inverse f^-1. Explain your answer.

f(x) = 2x+1 is one-to-one

f^-1(x) = (x-1)/2

check:

(f^-1 o f)(x) = (2x + 1 – 1) / 2

= 2x/2

= x

(f o f^-1)(x) = 2 ((x-1)/2) + 1

= x – 1 + 1

= x

If f: f -> f^-1 is one-to-one, it is invertible. It’s inverse f^-1 is the function f^-1:f^-1 o f such that f -> f^-1 o f -> f^1 and f^-1 -> f o f^-1 -> f are identify functions.

Xn = Xn-1 + (1 + n)

X0 = 3
X1 = 3 + (1 + 1) = 5
X2 = 5 + (1 + 2) = 8
X3 = 8 + (1 + 3) = 12

Theme by Anders NorenUp ↑