×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Shlomo Oved

40

0

6

# Week 3 Discrete Math MA-UY 2314

Marketplace > New York University > Mathematics > MA-UY 2314 > Week 3 Discrete Math
Shlomo Oved
NYU

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

Covers Lecture and Recitation for Week 3
COURSE
Discrete Mathematics
PROF.
Dr Nasir Memon
TYPE
Class Notes
PAGES
6
WORDS
KARMA
25 ?

## Popular in Mathematics

This 6 page Class Notes was uploaded by Shlomo Oved on Sunday September 25, 2016. The Class Notes belongs to MA-UY 2314 at New York University taught by Dr Nasir Memon in Fall 2016. Since its upload, it has received 40 views. For similar materials see Discrete Mathematics in Mathematics at New York University.

×

## Reviews for Week 3 Discrete Math

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/25/16
Shlomi  Oved   Discrete  Mathematics     09/19/16  Lecture  (Week  3)   • Quiz  1  is  graded   • Quiz  2  is  on  Wednesday  (Based  on  HW#2)     • Quiz  1   • Find  the  inverse  of  the  function  f  or  else  explain  why  the  function  has  no   inverse.   • ????:???? → ????,????ℎ????????????  ???? ???? = 3???? − 5   • ???? = {…− 3,−2,−1,0,1,2,3…}     • Definition  of  a  Function-­‐  Let  A  and  B  be  non-­‐empty  sets.  A  function  from  A  to   B  is  an  assignment  of  exactly  one  element  of  B  to  each  element  of  A.   • ???? ???? = ????,      ????:???? ???????????????????????? → ????(???????? − ????????????????????????)   • Definition  of  One  to  One-­‐  A  function  is  said  to  be  one  to  one  if  and  only  if   ???? ???? = ????(????)  implies  that  ???? = ????  for  all  a  and  b  in  the  domain  of  f.   • Definition  of  Onto-­‐A  function  f  from  A  to  B  is  called  onto  if  and  only  if  for   every  element  ???? ∈ ????  there  is  an  element  ???? ∈ ????  such  that  ???? ???? = ????.   • Definition-­‐  A  function  is  said  to  be  one  to  one  correspondence  if  it  is  both  one   to  one  and  onto   • Definition-­‐  Let  f  be  a  one  to  one  correspondence  from  the  Set  A  to  the  Set  B.   The  inverse  function  that  assigns  GET  THE  REST  FROM  SLIDES       • ????:???? → ????,????ℎ????????  ???? ???? = 3???? − 5   • Does  this  have  an  inverse?   • Is  it  one  to  one?   • Assume  f(a)=  f(b)   • 3???? − 5 = 3???? − 5   • therefore  a  =  b       • It  is  onto?   • ???? → ????,???? = 3???? − 5   • When  getting  the  inverse,  you  can  map  to  zero,  so  it  is  not  onto.       • Proofs-­‐     • ????ℎ???????????????????? → ????????????????????   • Conjecture   • Lemma  (formal  proof)   • Corollary  (formal  proof)       • ???????????????????????????????????????????? → ????ℎ???????????????????? − ???????????????????????????????????? → ????????????????????????????  ????????????????????\     • Definition-­‐  An  integer  n  is  even  if  ∃???? ∈ ????  such  that  ???? = 2????.   • Definition-­‐  An  integer  n  is  odd  if  ∃???? ∈ ????  such  that  ???? = 2???? + 1.   • Theorem-­‐  If  n  is  an  odd  integer  then  ???? is  an  odd  integer.   Shlomi  Oved   Discrete  Mathematics     • Proof-­‐     • n  is  odd   • ???? = 2???? + 1  ????????????  ????????????????  ???? ∈ ????   • ???? = 2???? + 1   ▯ ▯ ▯ • ???? = 4???? + 4???? + 1   • ???? = 2 2???? + 2???? + 1,      ????????????????  ????????????  ???? = 2???? + 2????   • ???? = 2???? + 1     • Definition-­‐  An integer a is said to be perfect square if  ∃  ????  ????????????ℎ  ????ℎ????????  ???? = ????  ????????????  ???? ∈ ????   • Theorem-­‐  If  m  and  n  are  perfect  squares  then  mn  is  also  a  perfect  square   (????,????   ∈ ????)   • Proof-­‐     ▯ • ???? = ???? ▯   • ???? = ????   • ???????? = ???? ????   • ???????? = ????????  ▯ ▯ • ???????? = ????    ????????????  ???? = ????????       • Theorem-­‐  If  n  is  an  integer  and  3n+2  is  odd  then  n  is  odd.   • Proof-­‐   • ???????? + ???? = ???????? + ????   ????????▯???? • ???? = ????    (Dead  end)     • ????????????????????  ????????  ????????????????????????????????????????????????????     • 3???? + 2  ????????  ????????????   • 3???? + 2 → ????  ????????????  ????????  ????????????ℎ????????  ????????????????  ????????  ????????????   • assume  n  is  even   • ???? = 2????   • 3 2???? + 2 = 2 3???? + 1 → 3???? + 2  ????????  ????????????????‼   • ????ℎ????????  ????????  ????  ????????????????????  ????????????????????????????????????????,????ℎ????????????  ????????????  ????????????????????????????????????????  ????ℎ????????  ????  ????????  ????????????????  ????????????????  ????????  ????????????????????.     • ????????  ????????????????????????????  ????  ????ℎ????????????????????????????  ????????????????  ????????  ????????????.     • Algorithms-­‐   • Definition-­‐  An  algorithm  is  a  finite  sequence  of  precise  instruction  for   performing  a  computation   • Ex:  Pick  maximum  from  a  list     • Procedure  max  (???? ,▯ ,…▯???? :????????????▯????????????)   • ???????????? = ???? ▯ • ????????????  ???? ≔ 2  ????????  ????   •      ????????  ▯???????? < ????  ????ℎ????????  ???????????? ▯  ????   • ????????????????????????  ????????????   Shlomi  Oved   Discrete  Mathematics         • Important  aspects  of  an  algorithm:   • 1.  Input   • 2.  Output   • 3.  Definiteness   • 4.  Correctness   • 5.  Finiteness   • 6.  Effectiveness       • Ex:   • Consider  the  problem  of  making  change  of  n  cents  with  quarters,  dimes,   nickels,  and  pennies  using  the  most  total  number  of  coins.   • 222  ????????????????????  ????????????  ????????  ????????????????  ???????? → 222  ????????????????????????????,4  ???????????????????????????????? + 122  ????????????????????????????,…????????????     • ????ℎ????  ????????????????  ????????????  ℎ???????????????????????? → 222  ???????????????????? = 8  ???????????????????????????????? + 2  ???????????????????? + 2  ????????????????????????????   • Total  of  12  coins.       • Algorithm-­‐  greedy  change  maker   • Procedure  change(n:  a  positive  integer,   ???? ,???? ,???? ,…???? :????????????  ????????????????????????  ????????  ????ℎ????  ????????????????????  ????????????ℎ  ???? > ???? > ⋯???? )     ▯ ▯ ▯ ▯ ▯ ▯ ▯ • for  i=1  to  r   •  ▯      ???? = 0;   •    ????ℎ????????????  ???? ▯ ????   •                  ???? += ???? + 1   ▯ ▯ •         ▯        ???? = ???? − ????   • ????▯  ????????  ????ℎ????  ????????????????????????  ????????  ????????????????????  ????????  ????????????????????????????????????????????????  ????   ▯   • Lemma-­‐   • If  n  is  a  positive  integer,  the  n  cents  in  change  using  quarters,  dimes,  nickels,   and  pennies  using  the  fewest  possible  total  number  of  coins  has:   • 1.  At  most  2  dimes   • 2.  At  most  1  nickel   • 3.  At  most  4  pennies   • 4.  It  can  have  2  dimes  and  one  nickel   • 5.  Total  change  using  dimes,  nickels,  and  pennies  can’t  exceed  24.   • Prove  each  by  contradiction       • Theorem-­‐  The  greedy  algorithm  produces  change  using  the  fewest  coins   possible.     • 09/20/16  Recitation  (Week  3)   • Problem-­‐  Metal  rails  (5000  meters  long  each)  are  placed  on  railroad  tracks   and  fastened  to  the  ground  at  each  end.  In  the  heat  of  the  night  each  rail   Shlomi  Oved   Discrete  Mathematics     expands  by  1  meter  at  each  end  and  buckles  in  the  middle.  How  high   (approximately)  does  it  buckle.   • It  creates  a  triangle  where  A  is  lower  left  angle,  B  is  lower  right  angle  and  C  is   angle  of  buckle.  When  you  split  the  triangle  in  two,  you  get  two  right   triangles.     • ???? = 2500   ????????????????????????  ???????????????? ,???? = ℎ????????????ℎ????,???? = 2501  (ℎ????????????????????????????????????)   • ????▯ ????????  ????▯????????  ????▯  ????????????  ????????????????????????  ????????  ????????????????   • ???? = ???? − ????   • ???? = ???? − ???? ???? + ????   • ???? = (2501 − 2500)(2501 + 5000)   • ???? ≈ 86.6  ????????????????????????       • ???? ????,???? = ????!  ▯! • ???? ????,???? =   ▯▯▯ ! • ???? ????,1 = ????   • ???? ????,???? = 1   • ???? ????,???? = ▯!   ▯▯▯ !▯! • ???? ????,1 = ????       • How  many  nine-­‐digit  numbers  are  divisible  by  2?   • ???????????????? = ???? ∗ 1000 + ???? ∗ 100 + ???? ∗ 10 + ????   • ???????????????? = 2 ???? ∗ 500 + ???? ∗ 50 + ???? ∗ 5 + ????   • In  order  to  know  if  a  number  is  divisible  by  2,  the  last  digit  must  be  divisible   by  2   • Possible  ways:   • 8 ∗ 7 ∗ 6 ∗ 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1 ∗ 4  (4  at  the  end  signifies  all  the  possible  even   numbers)       • How  many  nine  digit  numbers  are  divisible  by  3?   • ???????????????? = ???? ∗ 1000 + ???? ∗ 100 + ???? ∗ 10 + ????   • ???????????????? = ???? ∗ 999 + ???? ∗ 99 + ???? ∗ 9 + ???? + ???? + ???? + ????   • ???????????????? = 3 ???? ∗ 333 + ???? ∗ 33 + ???? ∗ 3 + ???? + ???? + ???? + ????  (????????????  ????????  ????,????,????,????  ????????????????  ????????  ????????????????????????????????????  ????????  3)       • Problem:  You  have  5  seats  and  12  people.  How  many  different  seating   arrangements  are  possible?   • ???? 12,5 = ▯▯!    ????????  12 ∗ 11 ∗ 10 ∗ 9 ∗ 8   ▯!   • Problem:  Ways  to  arrange  26  letters  where  the  vowels  are  adjacent   • 22! ∗ 5!       Shlomi  Oved   Discrete  Mathematics     • Problem:  How  many  ways  can  you  have  26  letters  where  a  and  b  are  not   adjacent?   • 26! − 2 ∗ 25!   • (????????????????????????????????  ????????????????  ????????  ????????????????????????????  26  ???????????????????????????? − (????????????????????????????????  ????????????????  ????????  ℎ????????????  ????  ????????????????  ????????  ????)     09/21/16  Lecture  (Week  3)     •    Chapters  3.1  and  1.6-­‐1.7-­‐  Algorithms  and  Proofs   • Stable  Matching  Problem  (Marriage)-­‐   • Stable  matching-­‐  Each  man  and  each  women  have  a  preference  ranking  list.   • Given  matching  M   • ???? = { ???? ,???? , ???? ▯???? ,… ▯ ,???? } ▯ ▯ ▯ ▯ • A  pair  (m,  w)    is  said  to  be  a  blocking  pair  of  m  prefers  w over  w  and  w   i j i j   i j prefers  m  iver  m. j • ???? ,▯  ????????▯  (???? ,???? )   ▯ ▯     • Stable  Matching   • If  a  man  m  and  a  woman  w  are  paired  together,  then  at  least  one  of  the   following  is  true   • 1.  m  prefers  w  over  all  other  women   • 2.  If  m  prefers  w’  over  w,  then  it  is  certain  that  w’  prefers  some  other  m  over   m’   • Ex:   • Men  Preferences  of  Women   M   Women   1   2   4   1   3   2   3   1   4   2   3   2   3   1   4   4   4   1   3   2   • Women  Preferences  of  Men   W   Men   1   2   1   4   3   2   4   3   1   2   3   1   4   3   2   4   2   1   4   3   • The  following  matching  is  stable:  (m,w)   • {   1,4 , 2,3 , 3,2 , 4,1 }   • The  following  matching  is  unstable:   • {   1,1 , 2,3 , 3,2 , 4,4 }   • (1,4)-­‐>  Block  pair  (They  prefer  each  other  more  than  who  they  are  matched   with.       • Gale  and  Shapely  (1962)   • Man  oriented  gale-­‐shapely  algorithm   Shlomi  Oved   Discrete  Mathematics     • 1.  Assign  each  person  as  free   • 2.  While  some  man  m  is  free   • do   • begin   • w:=  first  woman  in  the  list  that  m  has  not  proposed  to   • If  w  is  free  then  assign  m  and  w  as  paired   • Else  if  w  prefers  m  to  her  current  partner  m’  then  assign  w  to  m  and  m’  is  set   to  free   • Else  w  rejects  m   • End   •

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Anthony Lee UC Santa Barbara

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Bentley McCaw University of Florida

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com