×

### Let's log you in.

or

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

×

or

by: Shlomo Oved

7

0

5

# Discrete Mathematics Week 4 Notes MA-UY 2314

Marketplace > New York University > Mathematics > MA-UY 2314 > Discrete Mathematics Week 4 Notes
Shlomo Oved
NYU

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

×
Unlock Preview

Discrete Mathematics Week 4 Notes
COURSE
Discrete Mathematics
PROF.
Dr Nasir Memon
TYPE
Class Notes
PAGES
5
WORDS
KARMA
25 ?

## Popular in Mathematics

This 5 page Class Notes was uploaded by Shlomo Oved on Saturday October 8, 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 7 views. For similar materials see Discrete Mathematics in Mathematics at New York University.

×

## Reviews for Discrete Mathematics Week 4 Notes

×

×

### 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: 10/08/16
Shlomo  Oved   Discrete  Mathematics  Notes   10/03/16   09/26/16  Lecture  (Week  4)   • Algorithms  +  growth,  Functions,  and  Proofs       • Suppose  coin  denominations  were:   • 25,  14,  1   • If  you  have  28  cents,  then  greedy  algorithm  would  produce   • 28 → 25 + 3 ∗ 1 = 4  ????????????????????   • but  you  could  have  only  2  coins   • 28 → 14 + 14     • Conjecture:  ????▯≥ ???? ▯▯▯ ∗ 2   • ????() → ????????????  ????ℎ       • Computing  maximum  element  in  a  list.   • First  assume  that  the  first  element  is  a  max,  then  iterate  through  the  code   and  compare  until  you  find  the  max.   • Computational  complexity-­‐>  depends  on  the  size  of  the  list   • Space  complexity   • Tasks:   • 1  –  write   • 2(n-­‐1)  –  comparisons   • n-­‐1-­‐  increments   ▯ • ▯ − ????????????????????????????????????????????   • ???? −  reads   • All  equivalent  to  about  C*n       • Definition-­‐  Let  f  and  g  be  functions  from  R-­‐>R  we  say  that   ???? ???? ????????  ???? ???? ???? (????????????  ????ℎ!)  if  there  are  constants  C  and  K  such  that   • ????(????) ≤ ???? ∗ ???? ???? ,????ℎ????????  ???? > ????   • Example-­‐     ▯ ▯ • ???? ???? = ???? + 2???? + 1  ????????  ????(???? )   • 4???? > ???? + 2???? + 1,????????????  ????????????????  ???? > ????   • ???? + 2???? + 1 ≤ ???? + 2???? + ????   ▯ ▯ ▯ • ???? + 2???? + 1 ≤ 4????     • Technically   • Is  ???? → ???? ???? ▯ − ????????????!   ▯ ▯ • Is  ???? → ???? ???? − ????????!       • Example-­‐   ▯ • Show  that  ????  is  not  O(n)   • Proof  by  Contradiction   • ????????????  ???? = ????(????)   Shlomo  Oved   Discrete  Mathematics  Notes   10/03/16   • ∃  ????  ????  ????????????  ????  ????  ????????????ℎ  ????ℎ????????     ▯ • ???? ≤ ????????  ????????????  ???? > ????   • ???? ≤ ????      ????????????  ???? > ???? → ????????????  ????????????????????????????????       • Definition-­‐  We  say  that  two  functions  f  and  g  from  R-­‐>R  are  of  the  same  order   if  ???? ???? = ???? ???? ????  ????????????  ???? ???? = ????(???? ???? )   • Theorem-­‐  Let  ???? ???? = ???? ???? + ???? ????▯▯▯ + ⋯+ ???? ???? + ????   ▯ ▯ ▯▯▯ ▯ ▯ • Then  ???? ???? = ???? ????   • Proof-­‐   ????(????) =▯???? ???? + ???? ▯▯▯???? ▯▯▯ + ⋯+ ???? ????▯+ ???? ▯  • ( ???? + ???? ≤ ???? + ???? )   • ????(????) ≤ ???? ???? ▯ ▯ + ???? ▯▯▯ ????▯▯▯ + ⋯+ ???? ???? ▯ ????   ▯ ▯ ▯▯▯▯ ▯▯ ▯▯ • ????(????) ≤ ???? ???? ▯ + ▯ + ⋯+ ▯▯▯ + ▯   ▯ ▯ ▯ ▯▯ ▯ • ???? ▯ ????▯ + ▯▯▯ + ⋯+ ▯▯▯ + ▯ ≤ ???? ▯ ????▯ + ???? ▯▯▯ + ⋯+ ???? + ????▯ ▯   ▯▯ ▯▯ ▯ • ???? ▯ ????▯ + ▯▯▯ + ⋯+ ▯ + ▯ ≤ ???? ∗ ????  ????????????  ???? ≥ 1   ▯▯ ▯▯▯▯ ▯▯ • There  O(n^2)   •   • Proofs   • 1.  Direct  Proofs   • 2.  Proofs  by  Contradiction   • 3.  Proof  by  Counter  Example   • Example:   • Every  positive  integer  is  the  sum  of  the  squares  of  two  integers.   ▯ ▯ • 1 = 0 + 1   • 2 = 1 + 1   • 3 − ????????????????????????  ????????     • Every  positive  integer  is  the  sum  of  squares  of  three  integers.   • 1 = 0 + 0 + 1   ▯ ▯ ▯ • 2 = 0 + 1 + 1   • 3 = 1 + 1 + 1   • 4 = 0 + 0 + 0   • 5 = 0 + 1 + 2   • 6 = 1 + 1 + 2   • 7 = ????????????????????????  ????????  ????????????????       • Every  positive  integer  is  the  sum  of  squares  of  four  integers.   • It  is  true  for  four  integers.       • 4.  Exhaustive  Proofs   •  Example-­‐  The  final  decimal  digit  of  a  perfect  square  is  one  of  0,1,4,5,6  or  9.   • Proof-­‐   • ???? = 10???? + ????   Shlomo  Oved   Discrete  Mathematics  Notes   10/03/16   • ???? = 10???? + ????   ▯ • ???? = 100???? + 20???????? + ????   ▯ ▯ ▯ ▯ • ???? = 10 10???? + 2???????? + ????     • ???? = 0 → 0   • ???? = 1 → 1   • ???? = 2 → 4   • ???? = 3 → 9   • ???? = 4 → 16   • ???? = 5 → 25   • ???? = 6 → 36   • ???? = 7 → 49   • ???? = 8 → 64   • ???? = 9 → 81     • 5.  Existence  Proofs   • constructive  proofs   • non-­‐constructive  proofs   ▯ • Example-­‐  Show  that  there  exists  irrational  numbers  x  and  y  such  that  ????  is   rational.   • Proof-­‐   • Let’s  look  at   2   • 2  ????????  ????????????????????  ????????  ????????  ????????????????????????????????????????   ▯ • How  about   2  rational?  Or  irrational?   • Conclusion-­‐   • ???????????????????????????????? → ????ℎ????????????????????  ????????????????????????   ▯ ▯ • ???????????????????????????????????????? → ????ℎ????????  ????????????????  ????????   2 = 2       • 09/27/16-­‐  Recitation   • Proofs  of  Inference-­‐   • Problem:  Rewrite  the  following  statements  without  using  conditionals   • A.  If  it  is  cold,  he  wears  a  hat   • B.  If  productivity  increases,  then  wages  rise   • ???? → ???? = ???? ∨ ????     • A.  It  is  not  cold  or  he  wears  a  hat   • B.  Productivity  decreases  or  wages  rise.       • Direct  Proofs   • Problem:  If  m  and  n  are  integers  divisible  by  3,  prove  that  (m+n)  is  divisible   by  3.   • ???? = 3????                                      ???? = 3????   Shlomo  Oved   Discrete  Mathematics  Notes   10/03/16   • ???? + ???? = 3???? + 3????   • ???? + ???? = 3(???? + ????)     • Problem:  Prove  that  can  integer  is  divisible  by  2  if  its  unit  digit  is  divisible  by   2  (0,  2,  4,  6,  8).   • ???????????????? = ???? ∗ 1000 + ???? ∗ 100 + ???? ∗ 10 + ????   • ???????????????? = 2 ???? ∗ 500 + ???? ∗ 50 + ???? ∗ 5 + ????     • Problem:  Prove  that  an  integer  is  divisible  by  5  if  the  sum  of  its  digits  is   divisible  by  5.   • ???????????????? = ???? ∗ 1000 + ???? ∗ 100 + ???? ∗ 10 + ????   • ???????????????? = 5 ???? ∗ 200 + ???? ∗ 20 + ???? ∗ 2 + ????     • Prove:  ???????????????? + ???????????????? = ????????????????   • ???????????? ± ???????????? = ????????????????   • ???? + ???? = 2???? + 2???? = 2(???? + ????)   • ???? + ???? = 2???? + 1 2???? + 1 = 2???? + 2???? + 2 = 2(???? + ???? + 1)   • ???????????????? ± ???????????? = ????????????   • 2???? + 2???? + 1 = 2???? + 2???? + 2 ???? + ???? + 1        ????????????       ▯ • Prove:  If  n  is  an  even  integer  then  ????  is  even   • ???? = 2????   • ???? = 2???? ▯ = 4???? = 2(2???? )  ▯ • Prove  by  contradiction  that  if  n  is  an  integer  and  3n+2  is  even,  then  n  is  also   even  3???? + 2 → 3????,  is  even.  If  you  subtract  even  from  even,  still  even.   • Assume  n  is  odd   • 3???? − ???? = 2????   • even  –  odd=  odd   • but  2n  is  even  so  can’t  be  true.       • 09/28/16  Lecture  (Week  4)   • Definition-­‐  Let  f  and  g  be  functions  from  ???? → ????  we  say  that  ???? ???? = Ω(???? ???? )  if   these  are  positive  constants  c  and  k  such  that   • ????(????) ≥ ???? ???? ???? ,????ℎ????????  ???? > ????   • Ex:   ▯ ▯ • ???? ???? = 8???? + 5???? + 7   • is  this  Ω ???? ?   • 8???? + 5???? + 7 ≥≥ ???? ,????ℎ????????  ???? > 1   • Definition-­‐  Let  f  and  g  be  functions  from  ???? → ????,  we  say  that  f(x)  is  Θ(???? ???? )  if   f(x)  is  O(g(x))  and  f(x)  is  Ω(???? ???? )   • Ex:   • 3???? + 8???????????????? ????  ????????  Θ(???? )  ▯   Shlomo  Oved   Discrete  Mathematics  Notes   10/03/16   • Theorem-­‐  Suppose  that ▯  ???? ????  ????????  ????▯???? ????  ????????????  ????▯????  ????????  ???? ???? ????▯,????ℎ????????   ???? + ▯ ???? ????  ????????  ????(max  ( ???? ???? , ???? ???? )   ▯ ▯ ▯ • Theorem-­‐  Suppose  that   ????▯????  ????????  ???? ???? ????▯  ????????????  ???? ????  ▯????  ???? ???? ???? ,????ℎ▯????  ???? ???? ???? = ????(????▯ ▯∗ ???? ???? )   ▯ ▯     • Sorting  Algorithms-­‐   • Bubble  Sort-­‐   • ???????????????????????????????? → ???? − 1  ????????????????????????????????????????????   • ????????????????????  ???????????????? → ????  ????????????????????????????????????????????   ▯▯▯ • ????????????????????????????  ???????????????? → ▯   • Insertions  Sort-­‐   • ????????????????  ???????????????? → Ω(????)   • ????????????????  ???????????????? → ????(???? )     • Closest  Pair  of  points   • Procedure  closestPairOfElem   • ???????????? = ∞   • ????????????  ???? = 1  ????????  ???? − 1   •                    ???? = ???? + 1  ????????  ????   •                    ???????? − ???? − ???? ▯ < ????????????   ▯ ▯ ▯ ▯ •                     ▯   ▯    ▯   ▯   ????ℎ????????   ???? ,???? , ???? ,????  ????????  ????????????????????????????  ????????????????   •            ????ℎ????????????????  ????????  ????????????  ????????????  ????????????????????

×

×

### 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

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Jennifer McGill UCSF Med School

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over \$500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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!"

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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