Thu Dec 5 16:24:16 2024
EVENTS
 FREE
SOFTWARE
INSTITUTE

POLITICS
JOBS
MEMBERS'
CORNER

MAILING
LIST

NYLXS Mailing Lists and Archives
NYLXS Members have a lot to say and share but we don't keep many secrets. Join the Hangout Mailing List and say your peice.

DATE 2015-05-01

LEARN

2024-12-05 | 2024-11-05 | 2024-10-05 | 2024-09-05 | 2024-08-05 | 2024-07-05 | 2024-06-05 | 2024-05-05 | 2024-04-05 | 2024-03-05 | 2024-02-05 | 2024-01-05 | 2023-12-05 | 2023-11-05 | 2023-10-05 | 2023-09-05 | 2023-08-05 | 2023-07-05 | 2023-06-05 | 2023-05-05 | 2023-04-05 | 2023-03-05 | 2023-02-05 | 2023-01-05 | 2022-12-05 | 2022-11-05 | 2022-10-05 | 2022-09-05 | 2022-08-05 | 2022-07-05 | 2022-06-05 | 2022-05-05 | 2022-04-05 | 2022-03-05 | 2022-02-05 | 2022-01-05 | 2021-12-05 | 2021-11-05 | 2021-10-05 | 2021-09-05 | 2021-08-05 | 2021-07-05 | 2021-06-05 | 2021-05-05 | 2021-04-05 | 2021-03-05 | 2021-02-05 | 2021-01-05 | 2020-12-05 | 2020-11-05 | 2020-10-05 | 2020-09-05 | 2020-08-05 | 2020-07-05 | 2020-06-05 | 2020-05-05 | 2020-04-05 | 2020-03-05 | 2020-02-05 | 2020-01-05 | 2019-12-05 | 2019-11-05 | 2019-10-05 | 2019-09-05 | 2019-08-05 | 2019-07-05 | 2019-06-05 | 2019-05-05 | 2019-04-05 | 2019-03-05 | 2019-02-05 | 2019-01-05 | 2018-12-05 | 2018-11-05 | 2018-10-05 | 2018-09-05 | 2018-08-05 | 2018-07-05 | 2018-06-05 | 2018-05-05 | 2018-04-05 | 2018-03-05 | 2018-02-05 | 2018-01-05 | 2017-12-05 | 2017-11-05 | 2017-10-05 | 2017-09-05 | 2017-08-05 | 2017-07-05 | 2017-06-05 | 2017-05-05 | 2017-04-05 | 2017-03-05 | 2017-02-05 | 2017-01-05 | 2016-12-05 | 2016-11-05 | 2016-10-05 | 2016-09-05 | 2016-08-05 | 2016-07-05 | 2016-06-05 | 2016-05-05 | 2016-04-05 | 2016-03-05 | 2016-02-05 | 2016-01-05 | 2015-12-05 | 2015-11-05 | 2015-10-05 | 2015-09-05 | 2015-08-05 | 2015-07-05 | 2015-06-05 | 2015-05-05 | 2015-04-05 | 2015-03-05 | 2015-02-05 | 2015-01-05 | 2014-12-05 | 2014-11-05 | 2014-10-05

Key: Value:

Key: Value:

MESSAGE
DATE 2015-05-05
FROM Ruben
SUBJECT Re: [LIU Comp Sci] Fibonacci trees
From owner-learn-outgoing-at-mrbrklyn.com Tue May 5 23:37:43 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 98ADF1612E1; Tue, 5 May 2015 23:37:43 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id 867831612ED; Tue, 5 May 2015 23:37:43 -0400 (EDT)
Delivered-To: learn-at-mrbrklyn.com
Received: from mail-qk0-f169.google.com (mail-qk0-f169.google.com [209.85.220.169])
by mrbrklyn.com (Postfix) with ESMTP id DDF401612E1
for ; Tue, 5 May 2015 23:37:19 -0400 (EDT)
Received: by qkgx75 with SMTP id x75so120501571qkg.1
for ; Tue, 05 May 2015 20:37:18 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to
:subject:references:in-reply-to:content-type
:content-transfer-encoding;
bh=CJPFqyko5CyXj47N+kRO1DZDfvSwtlwlBYu9srUeoXY=;
b=ZkDx00bahTV9wG7ktcnTw0IZwsPl0ZDordJ6eXCxLQ8hC2P+kicbA23OIxGvx9GMII
yBpK7kjvxVDNwPeVNvQLrvqpv1qjmv8eJxvseUeIxtN/wRmeF678l4HxGMYuYprUl/nY
8eYtdzWimiOaocnF9S7l0dTFILNmXqBCd1pyix1sJgNI50TOHg53BDfBH00MaxO4t5vK
u+7kEm4Jw2SHzV06HmwHJjpc8m9vI7qlMw1KEvSqg/BbaBsNYlGbTBn3gXlMP1VsHSrE
yQAmbbMAu7o3v9DTUEH1GhgiXkH1bF39gwqLdo3rk5hfn+qLivVcq1Nv95jJufSWchLs
Mu7g==
X-Gm-Message-State: ALoCoQnOB0rCoA4xF2SDIAz5NMn7XjIVOGe8EngImGboMPdOkR1XfW9qvNhNm/FeuRb8/PqOAwJF
X-Received: by 10.140.39.164 with SMTP id v33mr36766043qgv.80.1430883438203;
Tue, 05 May 2015 20:37:18 -0700 (PDT)
Received: from [10.0.0.19] (www.mrbrklyn.com. [96.57.23.82])
by mx.google.com with ESMTPSA id f9sm346571qhe.34.2015.05.05.20.37.17
(version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Tue, 05 May 2015 20:37:17 -0700 (PDT)
Message-ID: <55498C6D.4070404-at-my.liu.edu>
Date: Tue, 05 May 2015 23:37:17 -0400
From: Ruben
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: "Jose A. Rodriguez"
Subject: Re: [LIU Comp Sci] Fibonacci trees
References: <55498808.7030608-at-panix.com>
In-Reply-To: <55498808.7030608-at-panix.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com


I think the answer of this problem in the notes is wrong

You are given that
F0 = 1
F1 = 2

|Fh| = Fh-1 + Fh-2

F2 = F1 + F0 + 1
2 + 1 + 1 = 4

F3 = F2 + F1 + 1
4 + 2 + 1 = 7

F4 = F3 + F2 + 1
7 + 4 + 1= 12

F5 = F4 + F3 + 1
12 + 7 + 1 = 20

F6 = F5 + F4 + 1
20 + 12 + 1= 33

F7 = F5 + F3 + 1
33 + 20 + 1 = 54 <=====

In other words, I think you misnumbered them starting with 3 instead of two.

Or I don't understand something very important.

Ruben



On 05/05/2015 11:18 PM, Ruben Safir wrote:
> OK - so here is from the notes:
>
>
> The inequalitiy also holds for h = 0 and h = 1, so by induction it holds for
> all h ? 0. Therefore, given a height-balanced tree on n nodes having
> height h we
> have n ? |Fh | ? 2?h. Taking log we obtain ?h ? log(n) or h ? (1/?)
> log(n). We
> have (1/?) is about 1.44042009 . . . < 1.45. So we conclude that h ?
> 1.45 log(n),
> that is, a height-balance binary tree is at most 45% taller than its
> perfectly
> balanced counterpart on the same number of nodes. The height of an AVL tree
> will in practice be a lot less than what this upper bound indicates.
>
>
> I don't understand this part
>
> n ? |Fh | ? 2?h
>
>
> Fh is defined as the smallest number of nodes for balanced AVL tree
> so how can is be GREATER than 2?h
>
>
> ??
>
>
>
>

  1. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] debuging methods
  2. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Excellent article on Virtual Paging and OS memory
  3. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Great Article on Software Concordance program writing
  4. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Semephores and what the heck are those things?
  5. 2015-05-03 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Go Language tutorials
  6. 2015-05-04 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] ACL and beyound security in linux
  7. 2015-05-04 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: [Perlweekly] #197 - YAPC::EU Master classes - talks - hackathons
  8. 2015-05-05 Ruben <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] Fibonacci trees
  9. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Examination Question for Allogorthims
  10. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fibonacci trees
  11. 2015-05-05 Ruben <ruben.safir-at-my.liu.edu> Subject: [LIU Comp Sci] Fwd: Internships with Oracle, Amtrak, The Nature Conservancy & more
  12. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Nice possible project for NYLXS or others
  13. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  14. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  15. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  16. 2015-05-06 Ruben <ruben.safir-at-my.liu.edu> Subject: [LIU Comp Sci] Fwd: Re: [opensuse] Re: no space left on the device
  17. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] hashing multiplication
  18. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Kernel Scheduling and wait queues
  19. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: Kernel Scheduler and wiat queues
  20. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: [NYLXS - HANGOUT] Things to study over the summer
  21. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Things to study over the summer
  22. 2015-05-10 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  23. 2015-05-10 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] scheduler Slides
  24. 2015-05-11 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] scheduler Slides
  25. 2015-05-11 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] scheduler Slides
  26. 2015-05-11 Justin Lau <justinml-at-gmail.com> Re: [LIU Comp Sci] scheduler Slides
  27. 2015-05-11 Justin Lau <justinml-at-gmail.com> Re: [LIU Comp Sci] scheduler Slides
  28. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  29. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  30. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  31. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Job sound like this evenings lectures
  32. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] jobs
  33. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] LAMP Jobs
  34. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] April Journal is Available
  35. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Tomorrow: You and 256 others are going to "Btrfs"
  36. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Malloc systemtap probes: an example
  37. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Stackiq - Educational Program
  38. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Student Lab and Club House
  39. 2015-05-13 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [member-at-linkedin.com: RE: April Journal is Available]
  40. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] [mrbrklyn-at-panix.com: Re: [NYLXS - HANGOUT] Things to study over the
  41. 2015-05-14 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Weekly Education Meeting
  42. 2015-05-18 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [jkeen-at-verizon.net: ny.pm Technical Meeting Wed May 20 6:15 pm]
  43. 2015-05-25 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Summer NYLXS Study Schedule
  44. 2015-05-28 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  45. 2015-05-28 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  46. 2015-05-28 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  47. 2015-05-28 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  48. 2015-05-28 Ruben <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: Programming Position
  49. 2015-05-28 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [ruben-at-www.mrbrklyn.com: Linux 1 Book]
  50. 2015-05-31 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule

NYLXS are Do'ers and the first step of Doing is Joining! Join NYLXS and make a difference in your community today!