×

Let's log you in.

or

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

×

Create a StudySoup account

Be part of our community, it's free to join!

or

By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

by: Shlomo Oved

48

0

9

Data Structures Week 2 CS UY 2134

Marketplace > New York University > CS UY 2134 > Data Structures Week 2
Shlomo Oved
NYU

Preview These Notes for FREE

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

×
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

About this Document

These Cover Monday and Wednesday Lectures
COURSE
Data Structures & Algorithms
PROF.
Linda M Sellie
TYPE
Class Notes
PAGES
9
WORDS
KARMA
25 ?

Popular in Department

This 9 page Class Notes was uploaded by Shlomo Oved on Saturday September 17, 2016. The Class Notes belongs to CS UY 2134 at New York University taught by Linda M Sellie in Fall 2016. Since its upload, it has received 48 views.

×

Reviews for Data Structures Week 2

×

×

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/17/16
Shlomi  Oved   Data  Structures  and  Algorithms   09/07/16   Lecture  09/12/16  (Week  2)     Formal  Definition  of  Big  Oh:   • Definition:  (Big-­‐Oh)  T(n)  is  O(g(n))  if  there  are  posit0ve  c  and  n  such  that   ???? ???? ≤ ???????? ????      ????ℎ????????  ???? ≥ ????   ▯ • While  3n  is  O(2n),  DO  NOT  WRITE  THIS!   • 3n  is  O(n)   • While  3n  +  10n  is  O(n+n )  DO  NOT  WRITE  THIS!   • 3n  +  10n  is  O(n )     • To  prove  T(n)  is  O(g(n)),  we  state  witnesses 0 c  and  n  that  prove    ???? ???? ≤ ???????? ????      ????ℎ????????  ???? ≥ ????    using  algebraic  manipulation   ▯   • 3???? + 10????  ????????  ???? ????  ▯ • Why?  Let  c=11  and 0  n =3   ▯ ▯ • If  ???? ≥ 3,????ℎ????????  3???? + 10????  ≤ 11????   • Iff  3???? ≤ ????    ????????????  3 ≤ ????     • For  the  same  problem  there  are  different  algorithms,  some  of  which  are   substantially  better  than  others  to  solve  it   • Static  Searching  (data  doesn’t  change)   o If  key  x  is  in  array  a,  return  its  position;  else  indicate  that  its  not  there   • Recall  Sequential  Search:  O(n)   • If  array  is  sorted  we  can  use  binary  search.     • Running  time  of  Binary  Search   • Worst  Case  running  time   o After  first  comparison,  how  many  items  left?  n/2   o After  second,  n/2  items  left   o After  third,  n/2  items  left   th k o After  the  k  comparison,  n/2  items  left   • How  many  comparisons  till  one-­‐item  remains?  [log(n)]     • Total  number  of  comparisons?  [log(n)]+1     • Useful  Facts  About  Logs   ▯ • log ▯ = ????log ????   ▯ • log ▯????) = log ????/lo▯ ????   ▯   • Big  Oh  Logs   • log ▯ = ???? log ????   • log ???? ▯ = ???? log ????   ▯ • Bases  can  be  switched  by  multiplying  by  constants     Shlomi  Oved   Data  Structures  and  Algorithms   09/07/16   • Exponential  functions  grows  very  fast,  while  logarithmic  functions  grow  very   slow.  Programs  with  exponential  running  time  are  very  slow,  and  logarithmic   functions  are  very  fast.     • Repeated  Halving  and  Doubling   • For  (i=n;  i>1;  i=i/2)  O(log(n))   • For  (i=n;  i>1;  i=i*2)  O(log(n))   • Always  log(n)     Estimating  Running  Times   For  (i=1;  i<n;  i=2*i)     Sum+=  a[i];   O(log(n))     For(  i=1;  i<n;  i=4*i)     Sum+=  a[i]   O(log(n))     For  (i=n;  i>1;  i/=4)     Sum+=a[i]   O(log(n))     Floors  and  Ceilings   ????????????????????  ????????   ????????????????????  ????????????????     For  a  linear  algorithm  time,  when  we  double  the  input  size,  we  roughly  double  the   number  of  steps.   ???? ????????(????)  ????ℎ????????????  ????  ????????  ????????????????????????????????  ????????????  ????  ????????  ????ℎ????  ????????????????????????????????  ????ℎ????????  ????ℎ????  ????????????????????  ????????????????  ????????  ????ℎ????????????????????   ▯   For  a  quadratic  algorithm  time   ???? ▯ ????(????)  ????ℎ????????????  ????  ????????  ????????????????????????????????  ????????????  ????  ????????  ????ℎ????  ????????????????????????????????  ????ℎ????????  ????ℎ????  ????????????????????  ????????????????  ????????  ????ℎ????????????????????       Estimating  Run  Times   If  the  algorithm  is  O(n ),   And  it  takes  0.0073  seconds  when  n=2   7 How  long  should  it  take  when  n=2 8   It  will  take  4  times  as  long:  .0292     If  the  algorithm  is  O(n ),   And  it  takes  0.0073  seconds  when  n=2   7 8   How  long  should  it  take  when  n=2 It  will  take  8  times  as  long:  .0584     In  general,  to  compute  the  ratio  ???? = ???? /????   ▯ ▯ Shlomi  Oved   Data  Structures  and  Algorithms   09/07/16   Program  will  take  about  ???? ∗ ???? ▯     Using  outputs  we  can  figure  out  what  the  running  time  is  by  dividing  by  the  Big-­‐Oh   you  think  it  is.  For  example  if  your  run  time  is  .00024  and  you  think  it’s  a  quadratic.   If  you  are  correct  and  you  divide  by  the  square  of  your  input  it  will  converge.  If  you   are  wrong  it  will  diverge.     Max  Contiguous  Subsequence  Problem   One  problem  and  three  solutions   Given  a  sequence  of  numbers,  A1,  ….,An  of  numbers  of  find  i  and  j  such  that  Ai  +  …   +Aj  is  maximal   1,  2,  -­‐4,  1,  2,  -­‐1,  4,  -­‐2,  1   st 3  1  Solution-­‐  Brute  Force-­‐  Computing  all  subsequences.  Running  time  is  O(n )   2  Solution-­‐  Compute  all  the  subsequences  but  keep  the  previously  computed  sums.   O(n )   3  Solution-­‐  Don’t  have  a  subsequence  that  start  or  end  in  negative  numbers.  Linear       09/14/16  Lecture  (Week  2)   Topics   • Stack  and  Heap   • Pointers   • The  Big  Five   • Tremplate   • Functors   • stringstreams     • Storing  Information   • Computer  stores  information  in  a  Bit  of  8  Bytes  (Zeros  and  Ones)   • Every  letter  is  given  its  own  number,  and  the  computer  is  told  to  interpret  it   as  a  letter  and  not  a  number.  On  my  computer,  C++  uses  1  byte  to  store  a   character.   • Memory  Layout   •  First  there  is  the  actual  code,  then  under  it  the  static  data,  then  the  heap,  and   then  the  stack  (function  calls).   • Dynamic  Memory  and  the  Heap   • Accessing  Data  by  its  address:  Pointers   • Value  of  a  pointer  variable  is  a  memory  address  or  nullptr   • Pointer  declarations  based  on  type  of  object  the  pointer  references:   • C  *p,  *q     • Operations:     • *p  //dereference  –  gives  object  at  address  p     • *p=*q  //  assignment  of  objects  of  class  C     • p=q  //  assignment  of  pointers.  Creates  alias     Shlomi  Oved   Data  Structures  and  Algorithms   09/07/16   • p  =  &x  //  where  x  is  object  of  class  C     • p-­‐>f  //  shorthand  for  (*p).f  where  f  is  member  of  C   •   • Memory  Management  and  the  Heap   • C  *p;   • p=  new  C;  //calls  constructor  of  class  C   • delete  p;         • int  main(){   • int*  total=nullptr;   • total=  new  double;   • cin  >>  *total;   • delete  total;   • total=nullptr;     • C  *p;   • p=new  C[n];   • delete  []  p;   •   • int  main(){   • int  numDays;   • int  count;   • double  *  sales=nullptr   • cin  >>  numDays;   • sales=  new  double[numDays]   • for  (count=0;  count  <  numDays;  count++){  cin  >>  sales[count]}   • delete  []  sales;   • sales=nullptr;   • }         • References   •  lvalue  references  &  rvalue  references     • Beware  of:  dangling  references  double  delete  garbage  (memory  leaks)       • lvalue  References   • pointer  constant  that  is  always  implicitly  dereferenced   • creates  alias     • useful  for  call  by  reference       • int  x=0;   • int&  y=x  (y  is  only  an  “alias”  of  x)   • y++;  //increments  x   • cout  <<  x;   Shlomi  Oved   Data  Structures  and  Algorithms   09/07/16     • Parameter  Passing   • Call  by  value  (default)   • Allocates  parameter  and  initializes  it  by  copying  argument  (actual   parameter)   • Changes  to  parameter  do  not  affect  argument     • Call  by  lvalue  reference   • Creates  alias  between  argument  and  parameter   • Changes  to  parameter  DO  affect  argument   • Appropriate  for  all  objects  that  may  be  changed     • Call  by  const  lvalue  reference   • Call  by  reference,  but  compiler  prevents  modification  of  the  parameter   • Appropriate  for  large  objects  that  should  not  be  changed  and  are  expensive   to  copy       • Call  by  rvalue  reference   • If  the  item  passed  as  a  parameter  is  a  temporary  object  that  is  about  to  be   destroyed   • Most  common  use  is  overloading  operators  and  copy  constructor     • When  do  you  think  it  would  be  safe  to  recycle/steal  resources?   • Anytime  you  have  an  object  that  is  temporary  and  will  disappear,  then  its  ok   • Move  Semantics-­‐   • “  a  way  of  transmitting  information  without  copying”   • works  by  not  moving  the  primary  data  instead  changes  ownership  of  the   data.   • To  understand  move  semantics  you  need  to  understand  which  expressions   are  lvalues  and  which  are  rvalues.       • Lvalues  and  rvalues   • In  general-­‐   • lvalues  are  objects  you  can  take  the  address  of.   •  e.g.  named  objects,  objects  accessible  from  a  pointer  or  reference  objects.   • String  &  f(const  string  &  s)   • Vector<string>  a(10)   • Const  double  z;   • Bool  r;   • Not  permitted  to  be  moved       • Rvalues  are  objects  you  can’t  take  the  address  of.  E.g.  temporary  objects   • String  f  (const  string  &  s);   • Const  double  z=  3.14;   Shlomi  Oved   Data  Structures  and  Algorithms   09/07/16   • Bool  r=true;   • May  be  moved  from     • Int  x;  (lvalue)   • X=1;  (rvalue)     • Return  value  is  an  rvalue.   • It  is  possible  to  cast  an  lvalue  to  an  rvalue     • Lvalue  and  rvalue  reference  types  &,  &&   • Lvalues  references  (what  you  have  been  using):   • Rvalues  may  bind  to  const  lvalue  references       • String  s=  “hello”   • String  &  greeting  =  s;   • Bool  same=  (&s==&greetings)     • Rvalue  references  (the  new  type  of  reference):   • Rvalues  may  bind  to  rvalue  reference   • Lvalues  may  not  bind  to  rvalue  references       • String  &&  greeting  1=s  +  “!”;   • String  &&  greeting  2=  greeting.substr(0,3);       • Reference  Types  lvalue  &,  rvalue  &&   • Every  expression  is  a  lvalue  or  rvalue     • Void  f(string  &v)   • {cout  <<  “lvalue  reference”;}     • void  f(string  &&  v)   • {cout  <<  “rvalue  reference”;}     • void  main(){   • string  s=  “hello!”;   • f(s);  (lvalue  one  called)   • f(string(“Hello”));  (rvalue  one  is  called     • Changing  from  an  lvalue  to  an  rvalue   • Vector<int>  b={1,  2,3  ,4};   • Vecor<int>  a;   • a=  static_cast<vector<int>  &&>(b);   • Move  function-­‐  the  move  function  doesn’t  move  anything.  It  just  does  an   rcast   Shlomi  Oved   Data  Structures  and  Algorithms   09/07/16   • Void  swap(vector<int>  &  a,  vector<int>  &  b){   • Vector<int>  tmp(std::move(a));   • a=std::move(b);   • b=std::move(tmp);   • }   • int  main(){   • vector<int>  x(303);   • vector<int>  y(200);   • //code  …   • swap  (x,y);   • }     • C++  Classes   • C++  classes  have  five  functions  already  created:   • Copy  Assignment  operator=   • Move  Assignment  operator=   • Copy  Constructor   • Move  Constructor   • Destructor     • Using  when  you  use  some  of  these  you  really  need  all  of  them.     • Creation  of  a  very  simple  class   • Class  IntCell   • {   • public:   • Destructor   • ~IntCell();   • Constructor   •        explicit  IntCell(int  initialValue=0)   •            {storedValue  =  new  int(initialValue);}   • Copy  Constructor   •      IntCell(const  IntCell&  rhs);   • Move  Constructor   •      IntCell(IntCell  &&  rhs);   • Copy  Assignment  Operator   •      IntCell  &  operator=(const  IntCell  &  rhs);   • Move  Assignment  Operator   •      IntCell  &  operator=(IntCell  &&  rhs);   •   •      int  read()  const  {return  *storedValue;}   •      void  write(int  x)  {*storedValue=x;}   •   • private:   Shlomi  Oved   Data  Structures  and  Algorithms   09/07/16   •        int*  storedValue:   • };     • Copy  Assignment  Operator   • IntCell  &  Intcell::operator=(const  IntCell&  rhs)   • {   • if  (this  !=  &rhs)  {   •        *storedValue  =  *rhs.storedValue;   • return  *this;   • }   •     • Copy  Constructor   • IntCell::IntCell(const  IntCell  &rhs){   •          storedValue  =  new  int(*rhs.storedValue);   • }   • Move  Constructor   • IntCell::IntCell(IntCell  &&  rhs):storedValue(rhs.storedValue){   •        rhs.storedValue  =nullptr;   • }   • Move  Assignment  Operator   • IntCell  &  IntCell::operator=(IntCell  &&  rhs){   • Int*  tmp(storedValue);   • storedValue=rhs.storedValue;   • rhs.storedValue  =  tmp;   • return  *this;   • }       • Destructor   • IntCell::~IntCell(){   • Delete  storedValue;   • }     • int  main{   • IntCell  obj1;   • IntCell  obj2;   • Cout  <<  obj1.read()  <<  endl;   • Obj2  =  obj1;   • Obj2.write(3);   • Cout  <<  obj1.read()  <<  endl;       • }       Shlomi  Oved   Data  Structures  and  Algorithms   09/07/16

×

×

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

×

You're already Subscribed!

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

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.