1 Solving Recurrences - Stanford University

2y ago
42 Views
2 Downloads
917.60 KB
10 Pages
Last View : 1d ago
Last Download : 2m ago
Upload by : Noelle Grant
Transcription

tant time. Lines 4 and 5 take T (bn/2c)and T (dn/2e) time, since each of the subproblems has that many elements. The FindMaxCrossingSubarray procedure takes Θ(n) time, and the rest of the code takes Θ(1) time. SoT (n) Θ(1) T (bn/2c) T (dn/2e) Θ(n) Θ(1) 2T (n/2) Θ(n) (ignoring the floorsand ceilings).By case 2 of the master theorem, this recurrence has the solution T (n) Θ(n log n).8

CS 161 Lecture 333.1Jessica Su (some parts copied from CLRS)If we have extra timeChange of variables (substitution method) T (n) 2T (b nc) log n.For now don’t worry about rounding off values to be integers.Let m log n, i.e. n 2m . Then T (2m ) 2T (2m/2 ) m.Now let S(m) T (2m ). Then S(m) 2S(m/2) m.This recurrence has the solution S(m) O(m log m).So T (n) T (2m ) S(m) O(m log m) O(log n log log n).3.2Extra recursion tree problemConsider the recurrence T (n) T (n/3) T (2n/3) O(n). Let c represent the constantfactor in the O(n) term.The longest simple path from the root to a leaf is n (2/3)n (2/3)2 n · · · 1. Since(2/3)k n 1 when k log3/2 n, the height of the tree is log3/2 n.We get that each level costs at most cn, but as we go down from the root, more and moreinternal nodes are absent, so the costs become smaller. Fortunately we only care about an9

CS 161 Lecture 3Jessica Su (some parts copied from CLRS)upper bound.Based on this we can guess O(n log n) as an upper bound, and verify this by the substitutionmethod.when d c/(log 3 (2/3)).Note that we should be proving that the claim holds for the base case as well. You shoulddo this in your homework.10

and when to sell to maximize your pro t. Note that you cannot sell before you buy (so you can’t just sell on the highest day and buy on the lowest day). Naive strategy: Try all pairs of (buy, sell) dates, where the buy date must be before the sell date. This takes ( n2) time. bestProfit -MAX_INT bestBuyDate None

Related Documents:

SEISMIC: A Self-Exciting Point Process Model for Predicting Tweet Popularity Qingyuan Zhao Stanford University qyzhao@stanford.edu Murat A. Erdogdu Stanford University erdogdu@stanford.edu Hera Y. He Stanford University yhe1@stanford.edu Anand Rajaraman Stanford University anand@cs.stanford.edu Jure Leskovec Stanford University jure@cs.stanford .

Algorithms Appendix II: Solving Recurrences [Fa’13] We were right! Hooray, we’re done! Another way we can guess the solution is by unrolling the recurrence, by substituting it into itself: T(n) 2T(n 1) 1 2(2T(n 2) 1) 1 4T(n 2) 3 4(2T(n 3) 1) 3 8T(n 3) 7 It looks like unrolling the initial Hanoi rec

Computer Science Stanford University ymaniyar@stanford.edu Madhu Karra Computer Science Stanford University mkarra@stanford.edu Arvind Subramanian Computer Science Stanford University arvindvs@stanford.edu 1 Problem Description Most existing COVID-19 tests use nasal swabs and a polymerase chain reaction to detect the virus in a sample. We aim to

Domain Adversarial Training for QA Systems Stanford CS224N Default Project Mentor: Gita Krishna Danny Schwartz Brynne Hurst Grace Wang Stanford University Stanford University Stanford University deschwa2@stanford.edu brynnemh@stanford.edu gracenol@stanford.edu Abstract In this project, we exa

Stanford University Stanford, CA 94305 bowang@stanford.edu Min Liu Department of Statistics Stanford University Stanford, CA 94305 liumin@stanford.edu Abstract Sentiment analysis is an important task in natural language understanding and has a wide range of real-world applications. The typical sentiment analysis focus on

Mar 28, 2013 · 13.3.4 Other Spatial Data Structures 463 13.4 Further Reading 463 13.5 Exercises 464 13.6 Projects 465 V Theory of Algorithms 469 14 Analysis Techniques 471 14.1 Summation Techniques 472 14.2 Recurrence Relations 477 14.2.1 Estimating Upper and Lower Bounds 477 14.2.2 Expanding Recurrences 480 14.2.3 Divide and Conquer Recurrences 482 14.2.4 .

Stanford Health Care Organizational Overview 3 Contract Administration is a Shared Service of Stanford Health Care to Eight Other Stanford Medicine Entities Stanford Health are ("SH")is the flagship academic medical center associated with the Stanford University School of Medicine. SHC has 15,232 employees and volunteers, 613 licensed

9.1 Properties of Radicals 9.2 Solving Quadratic Equations by Graphing 9.3 Solving Quadratic Equations Using Square Roots 9.4 Solving Quadratic Equations by Completing the Square 9.5 Solving Quadratic Equations Using the Quadratic Formula 9.6 Solving Nonlinear Systems of Equations 9 Solving Quadratic Equations