### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Discrete Structures of CSCI CSCI 243

GPA 3.56

### View Full Document

## 32

## 0

## Popular in Course

## Popular in ComputerScienence

This 235 page Class Notes was uploaded by Aliza Ruecker on Thursday October 29, 2015. The Class Notes belongs to CSCI 243 at College of William and Mary taught by Staff in Fall. Since its upload, it has received 32 views. For similar materials see /class/231169/csci-243-college-of-william-and-mary in ComputerScienence at College of William and Mary.

## Reviews for Discrete Structures of CSCI

### What is Karma?

#### Karma is the currency of StudySoup.

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

Date Created: 10/29/15

CSci 243 Discrete Structures Lecture 29 Recurrence Relations II 1242002 1 Outline 0 Review Ad hoc Solution Methods BackSubstitution Dynamic Programming 0 Example Solving Fibonacci Recurrence Relation Linear Homogeneous Recurrence Relations Takeaway Message 1242002 2 quot Review Ad Hoc Solution Methods 0 Recall that a solution to a recurrence relation is a sequence where each term obeys the relation 0 Solution method we ve been using Write out the first few terms 0 Substitute previous terms Simplify to find a solution Telescoping or backsubstitution Works best when next value in terms of a single previous Example Investing Pn 115 Pn1 gt Pn115n P0 1242002 Review Number of Line Intersections Remember maximum number of intersections We derived a recurrence relation an an1 n 1 Writeafew terms a4a3 3 Buta3a22 a4a223 a4a1123 Buta10 a40123 So an sum1n 1 M 1242002 Review Ad Hoc Solution Methods 0 We can also solve any recurrence using dynamic programming 0 Sequence of steps where the state of the next step is computed from the previous steps 0 Compare to linear programmmg where we compute the values of variables to minimize a function int SolveRecurrenceRecFun recfun int numtosolve intn0 initialvalues termsiln0 initialvalues for i n01 to n termsi recfuntermsli l return terms 1242002 5 Review Ad Hoc Solution Methods 0 Example Fibonacci recurrence fibn fibm fibn2 lt0 1 1 2 3 5 8 gt int fibint terms return termsitermssize termsitermssize l solution SolveRecurrencefib num 01 0 Or using partial evaluation int SolveRecurrenceint numtosolve terms12 01 for i 3 to numtosolve termsii termsi 1 termsi 2 return terms 1242002 6 Solving Types of Rec Relations 0 But dynamic programming is just what we do by hand 0 Is there a better way Can we solve fib recurrence analytically Classify types of recurrence relations 0 Develop methods for each type 0 Example types Linear homogeneous easy Quadratic hard i I ll quot 1242002 7 39 32 Next up Linear Homogeneous RRs Mandelbrot set based on quadratic rec relation 0 Points C for which zI1 2quot C does not go to infinity ZNC complex numbers 20 0 124ZEIEIZ E Basic Idea 1 Assume solution of the form an r 39 am r 391an2 rnZ etc 2 Find all r s that seem to work 3 Modify assumed solution to a general solution an ocrn 1 Note higher degrees an oclr 0chn 4 Use initial conditions to find on and therefore the specific solution 1242002 9 Example Fibonacci Fibonacci recurrence fibn fibn1 fibn2 Assume solution of the form an r rn rquot391 rquot392 substituting an r rzrn392 rlrn392 r 392 factoring r2 r 1 dividing by rn39z This is the characterWC equation of the recurrence relation QC How do we solve for r 1242002 10 Example Fibonacci cont 2 Find all r s that seem to work 0 r2 r 1 1433 739 2 We ll call these solutions r1 and r2 1J r 1 J 2 2 2 1 1242002 Example Fibonacci cont 3 Now write general solution using r1 and r2 39 HWTWF W 2 2 0 Next we need to use a00 and a11 to find cal and a2 0 Note it doesn t matter which value we use for r1 and rZ oc1 and a2 will just be swapped too m l A 35quot 1242002 12 quot1 Example Fibonacci cont 4 Use initial conditions to find on and therefore the specific solution 0 a0 0 a1 1 0 1J 0 145 0 a Z 051 2 052 2 1 J 1 1 1 1 51 1 01 2 052 2 a2 1 1J quot 1 1 J quot 39 5 arc st 2 Wet 1242002 Linear Homogenous Recurrence Relations with Constant Coefficients We can generalize the previous example Linear mxb where m and b are constants H0m0geneousin this context only subscripted terms like an with coefficients Constant coe l39Cents coefficients are not fn Examples 0 an 3 an1 4 an3 OK Hn 2 Hn1 1 not OK not homogeneous an 3 an22 4 an3 not OK not linear an n an1 4 an3 not OK nonconst coeffquotquot quoti r l A 35quot 1242002 14 quot Linear Homogenous Recurrence Relations with Constant Coefficients Degree How far back in the sequence an4 is 4 0 Linear homogeneous recurrence relation of degree k with constant coe icents a recurrence relation of the form an clan1 cza2 ckank where c1 c2 ck are real numbers and ckth Examples 39 in fn1 fnZ degree 2 Pn 115Pn1 degree 1 QC What is the significance of ckth 1242002 15 Quick Check LHRR with CC or not If so what is the degree If not why not 0 an 3an1 4an2 5an3 an 2nan1 an2 an an1 2 an an32 an 4an1an2 an3 Li Erquot 1242002 16 55 Solving LHRR with CC S Can use the method from before 0 Theorem The sequence ltangt is a solution of the recurrence relation anc1an1c2an2 iff anoc1rlnoc2r2 Here r1 and r2 are the two distinct roots of rZ clr c20 n012 and allocz are constants Complications Repeated roots can handle this with some tricks 0 Complex roots just use complex numbers 1242002 17 Example Solve an an1 2an2 a0 2 a1 7 o r2 r 2 O characteristic equation r12 r2 1 solving for r c an a12n0L21 writing general solution 0 2 a1200L210 initial cases 7 a121oc211 0L1 3 a2 1 solving the linear eq s So an 32n 1n i Iiquot 1242002 18 quot55 Quick Check Solve an 5an1 6an2 a0 1 a1 O 1242002 19 CSci 243 Discrete Structures Lecture 2 Sets 942002 1 Outline 0 Introduction to Z 0 Definitions 0 Operations on sets 0 Applications 0 Power sets 0 Sets as Types Venn Diagrams 942002 Z Bonus Knowledge zed A formal specification language Good for specifying software Based on typed set theory and firstorder predicate logic the stuff you re learning Rant rant Are you a hacker software developer or software engineer l if 942002 3 gt L 395 Sets An unordered collection EX A 1 4 2 Can be finite or infinite EX Z 8 2 1 O 1 2 8 Can be empty A Q Aside N 0 1 2 8 Naturals start with 0 What about wholes 1 942002 4 39 5 Set Terminology EX A 1 4 2 7 9 B 4 11 7 3 Sets are equal if all elements match Cardinaity of a set A 5 An element ofa set 4 e A 13 e B Subset of a set 7 3 g B 4 11 7 3 g B Strict subset of a set 1 2 c A 5 942002 5 l I Set Operations EX A 1 4 2 7 9 B 4 11 7 3 Difference A B 1 2 9 Also AB Intersection A n B 4 7 Union A u B 14 2 11 7 9 3 P49 identities commutative distributive etc 54 942002 6 l I Quick Questions 0 Given A 1 4 2 7 9 B 4 11 7 3 C 1 4 2 ABmC o AmBUBmC 942002 More Set Terminology EX A 1 4 2 7 9 B 4 11 7 3 Sets are disjointif A n B Q Sets A and B partition C if A and B are disjoint and A u B C Complement of a set A A UA where U is some universal set 5 942002 8 l I Quick Questions TF cats and dogs are disjoint sets of animals 0 T F cats and dogs partition the set of mammals 942002 Application Type Theory 0 In programming languages a type is a set of values and the operations upon them 0 int x really says x e Inf 2 1 O 1 2 Inf Abstract data types ie classes 0 State variables and methods l 1 quot 942002 10 39 L 395 Power Sets 0 Power set the set of all subsets of a set EX P1 2 Q 1 2 12 EX P1 2 3 Q 1 2 3 12 13 23 123 For the typographically challenged P 12 Bonus how many sets in PA if An 5 942002 1 1 I x I Power Sets Example 0 Ex set of cats I own e IP all cats at Annie Kitten Kaboodle e Fifi MouserBobcatTwizzer Annie Kitten Kaboodle 942002 1 2 x Tuples What about ordered collections Tuples just write the items in parens 0 Ex 12 ordered pair 0 Ex 33 Note repetition Not a set 0 Aside A multiset or bag is a set which can have multiple elements 5 942002 13 I x I Cartesian Product EXA14 Babc A X B La Lb LC 46 4b 4C 0 Application geometry class computer graphics 0 Bonus Find out the difference between cartesian and cross product Try MathWorId 3 5 942002 14 gt L 395 Quick Questions oGiven A Z B Z 0 A x B you can abbreviate if your hand gets tired 0 Write the rationals as ordered pairs of numerators and denominators Hmm 942002 Aside Rationals are Countable A A A A A A A A A A A A quot quotquotn A L 7777 V V V V V L V V V V 942002 Types in Z 0 A set is a type operations not included 0 Declarations Cats given type x Z variable declaration mycats P Cats set variable 942002 Types in Z cont Schemas define types structure specification Pets cats P Cats clogs P Dogs alligators P Alligators o mypets Pets mypetscats Annie Kitten Kaboodle mypetsdogs Abbie mypetsaigators Q 3 5 942002 18 gt L 395 Defining Sets 0 Set builder or set comprehension notation Even Integers X Z X mod 2 O the set constructed with the integer X such that X mod 2 O 0 Z Subsequent number pairs xyZXy1Xy quot39I OI1 10 21 3 5 942002 19 gt L 395 Venn Diagrams oAmB V 15 942002 20 39 f Venn Diagrams cont A Aquot oAmBmC 15 942002 21 39 f Venn Diagrams cont A Aquot OAUC 151 942002 22 L CSci 243 Discrete Structures Lecture 28 Probability III Intro to Recurrence Relations 1222002 1 Outline 0 Review Probability o More on Random Variables o Variance o Recurrence Relations 1222002 Review Probability Conditional probability 39 pE1 0 E2 pE1 gtlt pE2E1 E2 amp E1 independent iff pE2E1 E2 amp pE1E2 E1 0 Random variables 0 Really an outcome functionquot Example Xs sum of numbers rolled with two dice 0 Expected values EltXgtZXltsgtplts seS Just the weighted average or mean u 1222002 Probability Distributions Probability Distribution forthe Sum of 2 Rolled Dice EX 7 736 4 POO 2 3 4 5 6 7 8 9 10 ii 12 Xs sum of numbers rolled on two dice iZZZEIEIZ 4 Probability Distributions cont E00 1100 1222002 Measuring Spread E00 1100 1222002 6 V39 L Variance How to measure spread Sum up the weighted distance of each value from the average Variance VX Z X s E x2 ps seS Standard deviation 0X 1 VX Theorem VX EX2 EX2 5 1222002 7 l 1 Variance Concept EX o I Em I EW 3 100 1222002 8 quot UL Example 1 0 Roll 2 clice What is the variance of X ij 2i where i is the number on the first die and j is the number on the second die 0 Outcomes ij and X ij 112 122 132 142 152 162 214 224 234 244 254 264 316 326 336 346 356 366 418 428 438 448 458 468 5110 5210 5310 5410 5510 5610 6112 6212 6312 6412 6512 6612 6 of 36 ways for X12 so pX12 636 1 quot 1222002 9 39 L 395 Example 1 cont pX2 pX4 pX6 pX8 pX10 pX12 636 16 EX 2x16 4x16 6x16 8x16 10x16 12x16 7 VltXgt Ems Ex2ps 2 72l36gtlt64 72136gtlt6 6 72136gtlt68 72136gtlt6 10 72136gtlt612 72136gtlt 6 353 1 1222002 10 K 39 Example 2 Same problem but solve using VX EXZ EX2 theorem EX 7 EXZ 22x16 42x16 62x16 82x16 102x16 122x16 1823 VX 1823 72 353 This way is easier 1 1222002 1 1 39 x 5 Quick Check 0 Consider two unfair coins First coin phead 23 ptail 13 0 Second coin phead 13 ptail 23 0 What is the expected number of heads when both coins are flipped o What is the variance of the distribution of the number of heads when both coins are flipped 1222002 Next up Recurrence Relations 122 02 13 Recurrence Relations 0 We ve already seen several bn fibn1 fibn2 maxintersforinesn maxintersforinesn1n1 Recurrence relation For the sequence ltangt an equation that expresses an in terms of one or more previous terms in the sequence 0 It kicks in when nn0 so we can do initial conditions 1222002 14 r Recurrence Relations cont 0 Solution of a recurrence relation a sequence whose terms satisfy the recurrence relation fib 1 1 2 3 5 8 n02 we start at a0 maxintersforines O 1 3 6 10 o Closedform a function which expresses an without using previous values in the sequence 1ampquot1amp quot74 2 i A 2 i maxintersforinesn n1 n 2 1222002 15 Example Interest You invest 10000 and get a 15 annual return How much will you have after 15 years PnPnL 015 Pn1115 Pn1 P1115 P0 P2115 P1 115115 P0 1152 Po P3115 P2 115115 P2 1153 Po Closed form Pn115n P0 P1511515 10000 quot 81370 3 5 1222002 16 gt L 395 Example Towers of Hanoi Let Hn be the number of moves to solve Towers of Hanoi with n discs 0 H1 2Hn1 1 But we know Hn1 2Hn2 1 Hn 22Hn211 22Hn2 2 1 But we know Hn2 2Hn3 1 Hn 222Hn3111 23Hn3 22 2 1 But we know Hn3 0 Closed form Hn 2n391H1 22 21 20 1222002 17 K 395 Example Towers of Hanoi o Hn 2n391H1 22 21 20 But we know H1 1 Hn2n391222120 Hn 2n 1 How do we prove 2n1 20 2n 1 Induction of course But we know how so skip it 1222002 CSci 243 Discrete Structures Lecture 5 Logic 1 962002 1 Outline Introduction Propositions Compound Propositions Truth Tables Tautologies and Contradictions Predicates and Quantification i 17 962002 2 55 Introduction to Logic Statements are either true or false Some statements are very hard to evaluate Ex x 2 has no integral solutions for X y and when ngt2 QC x2 322 2 2 X y 2 I39 have O39ISCO verep39 a truly remarkable roof rl Vhch tz hs margn IS 00 small to can an erma l 39 IT quot 962002 3 39 5 Introduction to Logic cont 0 We can 0 Abstract the details of a statement Perform meaningpreserving translations to simplify Maybe prove the argument invalid regardless of the detaYs or the truth of the details 0 Ex Bob is drunk or he s sleepy and needs a rest A or B and C 962002 4 Propositions Propositions My name is Maximillian 112 Not propositions Hello Where is McGIoughlinStreet 020 0 Stop sleeping 962002 Compound Propositions Easy Ones Assume P and Q are propositions P negation P is not true PAQ conjunction both P and Q are true PvQ disjunction either P or Q is true or that both are true PeaQ exclusive or either P or Q is true but not both are true e39 i 39 xi quot 962002 6 39 5 Compound Propositions Implication Assume P and Q are propositions P gtQ implication false if P is true and Q is false true otherwise 0 P is the antecedent or premise Q is the conclusion or consequence Z PgtQ because gt means a function i 39 xi quot 962002 7 39 5 Compound Propositions Implication false if P is true and Q is false true otherwise 0 Huh 0 Ex true gttrue true 962002 true gtfalse false false gttrue true false gtfalse true expected expected don t care don t care Compound Propositions Implication Given P gtQ Con verse Q gtP Contrapositve Q gt P Ex IfI have my umbrella it will rain If it will rain I will have my umbrella If it will not rain then I will not have my umbrella 962002 Compound Propositions Dbl Implic Assume P and Q are propositions PHQ biconditional true if P and Q values match false otherwise AKA double implication Note PHQ is really just P gtQQ gtP Z PcgtQ because H means a relation e39 l 39 IT quot 962002 10 39 5 Negation Fun 0 Can write with overbars P P DeMorgan s Laws 0 uPQ ltgt P v Q lt2gt IP IQ Negated Implication I P IQ We 7 prove this in a bit 962002 1 1 I Quick Question 0 Given It is not the case that the sky is always blue and dogs always chase cats Abstract Simplify Make Concrete 3 395 962002 12 55 Truth Tables 0 There are only two possible values for a proposition True or False Why not just enumerate all possibilities PQPAQ PQPvQ PQP gtQ TTT TTT TTT EXTFF TFT TFF FTF FTT FTT FFF FFF FFT 962002 13 Quick Question Prove P gtQ is the same as P Q 962002 14 i Tautologies and Contradictions Tautoogy always true regardless of the truth of the propositions EX P P Contradiction always false regardless of the truth of the propositions EX P P 39 723quot l k IT quot 962002 15 5 Quick Question 0 Is P P gtQ gt Q a tautology Li 2 3quot 962002 16 l 2 Predicates Predicate a property which may true or false 0 Ex Xgt3 X is the subject of the statement gt3 is the predicate Propositional function some proposition which depends on a variable Ex PXXgt3 Pgtlt is the value P is the func 3 395 962002 17 55 Quick Questions 0 Assume PXyz xyz True or False 39 P124 P458 v P112 962002 Quantification VX PX universal quanti cation the proposition that PX is true for all values of X EIX PX existential quantification the proposition that PX is true for some value of X Bound if we give a value free otherwise QC Given PX X2gtO is VX PX X in integers true e39 l 39 IT quot 962002 19 39 5 Quantification in Z 0 Recall set construction XZXgt1X2 Quantification VXIZ IX gt1 x2gt0 We can specify o The type of the variable A condition to limit the variable 962002 Negated Quantification VX PX EIX PX Ex Every dog has its day There exists a dog which does not have its day EIX PX VX PX Ex A president s name is Hoover All presidents do not have the name HOOVEhquot e39 i 39 xi quot 962002 21 39 5 Quick Questions Given PXy XyO What is the natural language translation of 3ny PXy True or false What is the natural language translation of VyEIX PXy True or false 3 393 962002 22 55 CSci 243 Discrete Structures Lecture 26 Probability I 11152002 1 Outline Motivation Basic Concepts and Terminology Application Gambling Probability of Combinations of Events Preview Probability Theory 55 11152002 2 39 I Motivation 0 What is the probability of having five kids all of which are boys 0 What are the odds that at least two people in this room share a birthday 0 What is the probability that fewer than 3 in 100 LCD screens are defective What s the probability of two avocados colliding in space a 3 5 11152002 3 gt L 395 Basic Concepts and Terminology Experiment a procedure with an outcome Example Flip 2 coins Sample space S set of all possible outcomes 0 headsheads headstails tailsheads tailstails Event E subset of the sample space 0 two heads headsheads IEI PI ObabIIW the odds of event E 19E 7 4 939 11152002 Examples 0 What is the probability of selecting a red ball from a bag with 3 red balls and 2 blue balls 0 How many total possible outcomes 0 How many outcomes of interest pred ball o What is the probability of getting two heads and a tail out of three coin tosses How many total possible outcomes 0 How many outcomes of interest ptwo heads and a tail 11152002 5 Quick Check 0 What is the probability of having five kids all of which are boys 15 11152002 6 39 f Application Gambling Primer Standard deck 0 52 cards each of a kind suit and color 0 13 kinds ace 210 jack queen king 0 4 suits clubs healts spades diamonds o 2 colors spades amp clubs are black healts amp diamonds are red 11152002 7 quot J Application Gambling Primer 5 card draw poker 5 cards dealt randomly to a player Ace high or low Interesting hands 1 pair 2 pair 3 of a kind 4 of a kind full house 2 pair and 3 pair straight flush straight flush R0 al flush 391 5 i 21 httpwwwexclamationpokercomguidehtm 11152002 8 i Application Gambling 0 What is the probability of 4 of a kind 0 Number of ways to get 4 cards of a kind 0 13 possible kinds and we choose 1 C131 13 o 4 possible cards and we choose 4 C44 1 Number of ways to get remaining card 0 48 cards left and we choose 1 C481 48 Total possible hands C525 52 52 5 5 2598960 p4 of a kind 1339139482598960 N 00024 3 5 11152002 9 gt L 395 Application Gambling 0 What is the probability of 2 pair 0 First choose the 2 kinds note no order 0 13 possible kinds and we choose 2 C132 78 0 Next choose the cards for each kind 4 cards in the first kind choose 2 C42 6 o 4 cards in the second kind choose 2 C42 6 0 Number of ways to get remaining card 0 44 cards left and we choose 1 C441 44 0 p2 pair 7839639639442598960 N 04753 1 1 11152002 10 K 39 Quick Check 0 What is the probability that a card taken from a deck is a black 2 o What is the probability of a full house three of one kind and two of another Note Order 11152002 The Probability of Combinations of Events Complementaly event The event that some other event does not occur p 1p Intersection of independent events The event that both of two independent events occur maoE9p oxpE9 0 Union of events The event that one or both of two other events occur mavE p opEQMEHEQ 3 5 11152002 12 I Example What is the probability that a poker hand contains at least one ace Could compute pl ace p2 aces Or compute 1 pno aces 1 C485C525 341 55 11152002 13 39x I Example Binary trees With a 50 chance of making a left child and a 50 chance of making a right child what is the chance that you make either peft u right peftpright peft 0 right Left and right child generation is independent peft u right 12 12 1212 34 N f 11152002 14 ch Quick Check 0 What is the probability that a random number between 1 and 100 inclusive is divisible by 2 or 5 o What is the probability of having five kids all of which are boys 1 1 11152002 15 39 x 5 Quick Check 0 What are the odds that two people in this room share a birthday 1 15 11152002 16 39 f CSci 243 Discrete Structures Lecture 21 Graphs V 10252002 1 Outline 0 Graph Coloring Cliques Implementing Graphs Project 3 10252002 Graph Coloring Graph coloring a function f from vertices V to colors C such that if V1 and V2 are adjacent fltv1 at W Le Adjacent vertices have different colors QC What is maximum C Chromatic number the minimal number of colors necessary to color a graph y 13139 quot 10252002 3 39 5 Coloring Planar Graphs Theorem The chromatic number for planar graphs is no more than 4 03 9 r r lt 6 zp 10252002 4 V Quick Questions 0 What is the chromatic number for Cn What is the chromatic number for Kn What is the chromatic number for Kmln 10252002 Cliques o Clique In a simple undirected graph a complete subgraph not in a larger complete subgraph o QC Name all the cliques 10252002 Implementing Graphs How do we use graphs in programs 0 Option 1 Buy don t build Brooks 1975 No graph in STL but people have added it 0 Option 2 Maybe use matrices Adjacency matrix rows and columns are vertices 1 in matrix means vertices are adjacent Incidence matrix rows are vertices columns are edges 1 in matrix means edge hits vertex l 13139 39i 10252002 7 39 5 Adjacency Matrix Example r Ar AOr Am t AOt AOO Dr r OU Unmgt OOHO o QC Structural theorems o QC What if there is a 1 on the diagonal o QC Directed graph Multigraph m252nn2 a CSci 243 Discrete Structures Lecture 20 Graphs IV 10232002 1 Outline Weighted Graphs Shortest Paths Dijkstra s Algorithm Application Traveling Salesman Problem Planar Graphs and Euler s Formula 10232002 2 55 Weighted Graphs Not all edges are equal Example 164 connects Williamsburg to Hampton and Williamsburg to Richmond Label an edge with the cost of crossing it Length of a path now refers to total cost Weighted graph a graph with weighted EdQES 1 39 IT quot 10232002 3 14 Example Flight Costs New ank Sun anmm 7quot Lm nu1m mas2mm A Shortest Path 0 What is the cheapest fare for NY to SF 0 What is the cheapest way to get from NY to SF Shortest path the path between two vertices which has the minimal total cost length 0 Can find the shortest path for unweighted graph by making it a weighted graph with edge cost1 Dijkstra s Algorithm finds the length of the shortest path Slight mod gets the path too i Wequot 10232002 5 Dijkstra s Algorithm findlowestcost Graph G vertex start vertex end S set of vertices L map from each vertex to the cost of getting there empty S for v in vertices if v start then Lv 0 else Lv infinity while end not in S u a vertex not in S where Lv is minimal add u to S for each vertex v not in S It may be cheaper now to get to other vertices if Lu edgeweightuv lt Lv then Lv Lu edgeweightuv return Lend 10232002 6 Dijkstra s Algorithm Example n2 Analysis of Dijkstra s Algorithm QC What is the algorithmic complexity of the algorithm QC What change could you make to make the average running time better QC What change could you make to compute the shortest path 10232002 Traveling Salesman Problem 77 34 m m mum 7 39 W t V F H m t in Hf v x 777 fantu m xx i Hamiltonian circuit with lowest cost 10232002 Traveling Salesman Problem cont TSP is NPComplete Recall NPComplete problems which can be solved with nondeterministic polytime algorithm clifficult egtltponentia in practice Exponential growth 25 cities gt 31X1023 paths IsATautology is NPComplete same as SAT pqr exist so that pAquvarAq True 0 We use heuristics for TSP BDDs for SAT 10232002 Next up Graph Planarity Coloring 39 II r 39n H I E III d I H E El rr39u39ma p E 9 10232002 1 1 Graph Planarity o Planar A graph is planar if it can be drawn without edge crossings 10232002 12 quot 2 Quick Questions 0 Is Cn planar Is K4 planar Is K5 planar 10232002 Euler s Formula 0 Region In a planar graph the areas between edges REV2 10232002 14 Proof of Euler s Formula Concept 0 By induction on the edges building subgraphs o Gk a subgraph with k edges Gk1 Gk but with 1 new connecting edge 39 IRkI IEkI IVkI 2 10232002 CSci 243 Discrete Structures Lecture 4 Summations Products Interesting Functions 942002 1 Outline Summation notation Product notation Some interesting functions Practice writing specifications in Z 942002 2 Summations Summation add up the numbers in a sequence 0 Use sigma notation end 2 functi0nloopvariable loopVariablestart 5111111 EXgi12345 942002 Quick Question Solve 25 1 i1i2 942002 Application Binary Trees Again 0 How many nodes are there in a tree of depth n 22 i0 Li 3139quot 942002 5 a 5 Sum of Geometric Series 0 Solving 22 for n1000 is not fun J0 n J o More generally 5 25 geometrC seres j0 Isn t there some nice formula for this 942002 Before we do the derivation 00909090909 what fraction 1 F 009090909 2 mutpy by 100 100 F 909090909 o3eq2 eq1 99F9 4 solve forF F 111 942002 7 quot3 Sum of Geometric Series n S 2 ar i0 942002 8 Double Summations Funny Looping 6 5 0 Double Summation 12 i1 2 0 Loop vars ZS se127 l 139 942002 Products 0 Product multiply the numbers in a sequence 0 Use pi notation end H functi0nloopvariable loopVariab1estart 5111111 x x x x 39EXgi12345 942002 Quick Question 4 4 Whatis ZHij 12 i1 942002 1 1 Interesting Functions Floor LxJ round down to nearest integer L19J 1 Ceiling x round up to nearest integer 22 3 Div Xdvy number of times y divides X 17 div 3 5 Mod xmoa y remainder after dividing y 17 mod 3 2 i 39 xi quot 942002 12 39 5 Interlude 942002 13 Writing Z Specifications Application Phone book for cell phones What are the key data types What are the relationships between data types What is the scope of our specification What is the level of detail 39 723quot l 39 IT quot 942002 14 39 5 CSci 243 Discrete Structures Lecture 8 Algorithms 1 9132002 1 Outline Definition Defining Characteristics Searching Algorithms Devising Algorithms ii 9132002 2 quot52 Definition 0 Algorithm a finite set of precise instructions for performing a computation or solving a problem 9132002 3 Example Searing a Steak 0 Pat steak dry and let sit for 15 minutes Coat steak thinly with vegetable oil Rub 12 tsp salt and 14 tsp pepper into both sides 0 Let steak sit for 5 minutes Meanwhile open a window 0 Heat pan until a water drop jumps in the pan 0 Cook on pan for 3 minutes Don t touch it Flip and cook for 3 more minutes Don t touch it Pull from pan and let rest for 5 minutes before eating Alton Brown 777 Just Here for the Food 9132002 4 Language of Operations From example pat coat rub heat cook flip Algorithms assume a set of operations sear steakis not useful if you don t know sear For computers it s all about shuffling data eg sorti517 vs move compare data Li 31739 9132002 5 55 Language of Operations cont At the lowest level Storage locations Inspect data Compare data Assign locations data values Copy data from one location to another Anything else 39 723quot l k IT quot 9132002 6 5 Example CISC vs RISC CISC complex instruction set computer eg VAX 300 instr polynomial eval linked lists Shorter code powerful instructions simpler compilers easier debugging fewer memory accesses RISC reduced instruction set computer eg Sparc PowerPC Easier to optimize fixed op times simpler chips simple ops very commonly used few args 0 Mix convert CISC to miniRISC eg Pentium Athlon Convert CISC gt RISC compatibility with speed 9132002 Algorithm Defining Characteristics 0 Input The original data 0 Output The resulting data solution Definiteness Every step is defined precisely Correctness Correct output for all inputs Finiteness A finite number of steps to result 0 Effectiveness Each step exactly in finite time Generality Applicable to similar problems not just one set of inputs i 13139 quot 9132002 8 39 5 Quick Question findmaxset of numbers max some number in numbers foreach anumber in numbers maX anumber if anumber gt maX return max 0 Input Output Definiteness Correctness Finiteness Effectiveness Generality 9132002 9 Not Definite findmaxset of numbers max maximumnumbers return max 9132002 Not Correct findmaxset of numbers max a number in numbers foreach anumber in numbers return anumber if anumber gt max return max QC What does this really do QC For what inputs does it actually work 9132002 1 1 Not Finite findmaxset of numbers max a number in numbers while size of numbers gt O anumber some number in numbers maX anumber if anumber gt maX return max QC Does it find the max 9132002 12 Not Effective Computer languages designed to run in finite time functionhatsfunction foo call foo return true 3 395 9132002 13 55 Not General findmax591372 return 13 QC When might you wantto hardcode answers Li 9132002 14 quot5 Searching Next up 91 32002 Search a Random List 0 You dropped your playing cards 0 How to find a joker find jokerist of cards foreach acard in cards if acard is a joker then return acard return NOTFOUND QC Does it work for sorted lists 9132002 Binary Search Example Informal E i C ent ags exp0ft structure in the input or probem Binary search for c in lt a b c cl e f g h gt Splitltabcdgtandltefghgt Compare c lt cl and choose lt a b c cl gt Splitltabgtandltcdgt Compare c gt b and choose ltc cl gt Splitltcgtandltdgt c c so found it 9132002 17 Binary Search Algorithm binarysearchtofindlist of elements Iowpoint 1 highpoint size of list of elements while Iowpoint lt highpoint pivot lboundlowpointhighpoint2 if tofind gt elementspivot Iowpoint pivot 1 else highpoint pivot if tofind elementslowpoint then return lowooint 9132002 Binary Search Example Algorithm 0 Search for CI in lt a b c cl e f g h ijgt Iowpoint 1 highpoint 10 pivot 5 cl lt e so highpoint 5 pivot 3 cl gt c so Iowpoint 4 pivot 4 cl lt cl so highpoint 4 cl cl so return 4 i If 395 9132002 19 55 Next up Devising Algorithms 9132002 sub reformat my coumns 39f 0ampamp 0 Ad 39lfsiarins airti W else coumns 80 my text join 39n39 my endingnewines text ns endingnewines quot unless defined endingnewines text sn Change all the newlines to spaces in preparation of reformatting text sn TextWrapco umns coumns my formatted wrap text Tack a newline on the end if the original had one formatted endingnewines return formatted Quick Question Devise an algorithm to determine if a list has a duplicate 9132002 21 CSci 243 Discrete Structures Lecture 1 Welcome and Introduction 942002 1 1 Outline Greeting 0 Photographs 0 Introductions Professor Grader Syllabus Walkthrough 0 Quiz 0 Teaching philosophy 0 What is discrete math r 1 l1 942002 2 I Discrete Math 0 Discrete not discreet 0 Definition Involving distinct elements 0 If you can count it it s discrete QC What are some examples of distinct elements in computer science 942002 3 3 Countable vs Uncountable An aside 0 Question Can you count integers Even numbers Fractions Real numbers 942002 Countable vs Uncountable cont 0 Reals are not countable 0 Proof by contradiction l e 0198123496234 2 e 0927834879343 3 e 0369834589346 4 ea 0735783458937 5 e 0368954543333 ea 023086 W LI 5quot quot 942002 5 30 Discrete Math and Comp Sci Discrete Math is the mathematical foundation of computer science Computers are nite machines Limited state QC What is the state of a computer i LI 5quot quot 942002 6 30 CSci 243 Discrete Structures Lecture 22 Trees 10282002 1 Outline 0 Introduction to Trees 0 Types of Trees 0 Application Binary Search Trees 0 Properties of Trees 0 Simple Theorems About Trees 0 Tree Traversal Application Logical Expressions l Elquot 10282002 2 55 Trees 0 Tree A connected undirected graph with no ymmedmmm 0 Recall simple circuits contain no edge twice G 3 G 10282002 Botanical Terminology Root a designated vertex Rooted tree A directed graph where all edges point away from the root Q 393 G 36 0 Internal vertex vertex with outedges o LeaE vertex with no outedges 10282002 4 V V Genealogical Terminology Parent the vertex with edge to a given vertex o 0770 a vertex with edge from a given vertex 0 5bI39ng another vertex with the same parent Descendant vertex with path from given vertex 0 Anceston a vertex for which given vertex is a descendant 10282002 5 quot 39k Some Types of Trees maj tree a tree in which every internal vertex has no more than m children Example binary tree has 5 2 children per node Ful maj tree every internal vertex has exactly m children Subtree a tree whose root is an internal vertex of a larger tree 10282002 6 Some Types of Trees cont 0 Ordered rooted tree an ordered tree where the children of each vertex are ordered 0 Ordered binary tree 0 Lefl 6770 subtree the first child or its subtree o Rig7t C770 subtree the second child or its subtree 10202002 7 quot Next up Bmary Search Trees Brookhaven National Laboratory Budget Office Bnan p Sack Assxstam Dwedm my Emengs a Admmstvatmn mags Maega mega omga sessn cesvss Admmstvatwe SMpPDn Edwavd mms oamw mega omga Snmvasan Ver Eamvmer sssemv 51mm vae amp Beam me ESEH new JaAnn Dumam Labmmaw mega suppgn Busmess suppgn e ALD ngamzatmns Ammne e Fndae Pam Gaga Ammne e msse gunman W Mmhae CavveH Bmce Penn Busmess Opa me Asst mega omga Asst mega omga S emsoevem mm Busmessopev ng Busmessopev ng App mdsm aYech D RECY PROGRAMS WREcr EXPENSE V P Enwemana Mgml ESHEQ 7 Banme McGahem oamw ms Opa ng 7 w Pamma Gwaca ane Gamma mg Open Eegumss a Opevatmns H 10282002 Binary Search Trees 0 Many algorithms can benefit from the proper data structure Binary decision diagrams represent logical exp s to reduce exponential behavior to poly on average Binary search use a binary search tree Elnay search tree an ordered binary tree 0 Each vertex is labeled with the name of an item The left child is less than the vertex The right child is more than the vertex 10282002 9 Binary Search Tree Examples 0 Consider 8 2 5 1 9 4 10282002 10 Building a Binary Search Tree Inserttree T item x if T is empty create new root vertex V set Vlabel x return V root of T while Vlabel x if x lt Vlabel if Vleftchild exists then V Vleftchild else create new vertex for left child of V set Vlabel x return else if Vrightchild exists then V Vrightchild else create new vertex for right child of V set Vlabel x return 10282002 Building a Binary Search Tree 0 Add 7 to the tree 10202002 12 quot Using a Binary Search Tree 0 Search for 4 9 QC Best case tree QC Worst case tree 10282002 13 Next up Tree Properties Traversal Pem sslmms Maximan Sine Time mmpa Direct painter at with black In llen pollute at data block Double ludlnecl pointer Mple indilmct pointer 10282002 Properties of Trees Leve the length of the path from the root to the vertex Heght the length of longest path from the root Balanced for a tree of height h all leaves are at level h or level h1 We wanted binary search tree to be balanced for good logn performance 39 723quot l 39 IT quot 10282002 15 39 32 Simple Theorems About Trees 0 A tree With n vertices has nJ edges 0 Proof associate all nonroot vertices with the parent edge There are n1 of these N0 edge for root 0 There are at most mh lea ves in an maj tree of heght h Example Full binary tree of height 3 has to 23 8 leaves o If an ma tree of height h has n lea ves then h 2 logmn For a full balanced tree h logmn 39 ii 2 5 10282002 i Next up Tree Traversal 10282002 17 Tree Traversal Let s say we have an ordered tree 0 How can we walk a tree and look at the data Preora er look at current vertex then look at children Inorder look at left child then look at current vertex then look at remaining children POSZ39OI O39EI look at children then look at current vertex i 19 10282002 18 39 15 Example Preorder 0 G G 6 ABDECFG V 1 mzazuuz 19 L Example Inorder 0 G G 6 DBEAFCG V 1 mzazuuz in L Example Postorder 0 G G 6 DEBFGCA V 1 mzazuuz 21 L Implementation Preorder Binary Trees binarypreordertree T r root of T if r has no children cout ltlt rlabel and return cout ltlt rlabel if left subtree exists l left subtree of r binarypreorderl if right subtree exists r right subtree of r binarypreorderr 10282002 22 Implementation Inorder Binary Trees binaryinordertree T r root of T if r has no children cout ltlt rlabel and return if left subtree exists l left subtree of r binaryinorderl cout ltlt rlabel if right subtree exists r right subtree of r binaryinorderr 10282002 23 Implementation Postorder Binary Trees binarypostordertree T r root of T if r has no children cout ltlt rlabel and return if left subtree exists l left subtree of r binarypostorderl if right subtree exists r right subtree of r binarypostorderr cout ltlt rlabel 10282002 24 CSci 243 Discrete Structures Lecture 9 Algorithms 2 Complexity 9162002 1 Outline Motivation Linear vs Binary Search Introduction to Complexity Characterizing Growth of Functions Back to Complexity P and NP 3 395 9162002 2 55 Searching Revisited If list is sorted is linear or binary search faster If unsorted would sorting the list then doing a binary search be faster than linear search What does faster mean anyway What about memory usage l 39 IT quot 9162002 3 39 5 Algorithmic Complexity 0 Computational complexW a measure of the time or space performance 0 Must be calibrated to be meaningful To relevant criteria eg number of comparisons To size of input input of size n elements To trivial differences define equivalence classes ComplexW analysis is useless if the algorithm is incorrect 9162002 4 Calibration of Search Algorithms Relevant criteria number of comparisons between list elements and element to find Size of input list of n elements To trivial differences 5 comparisons is okay Is X5 comparisons okay too We need a precise metric for comparing algorithms and io enz ijing similar ones 39 723quot l 39 rl quot 9162002 5 39 5 Next up Function Growth 9162002 6 39 Characterizing Function Growth Can write functions which characterize the behavior of the algorithms Example linear search is like fnn because we do one comparison for each of the n items Then classify long term behavior of functions asympz oz ic beha vior Note Sometimes we do care about short term i v 3751 l 7iquot quot 9162002 7 BigO Notation fx is O ggtlt if there exist constants C and k such that fgtlt S Cggtlt C Don t care how many times faster Plus need to compare X2 and x22 k The eventually point for X 0 Algorithm F fgtlt performs no worse than algorithm G ggtlt for large inputs 39 723quot l 39 IT quot 9162002 8 39 5 Example BigO Notation x4 is 0X2 fx x4 a x xquot2 0 C1 k3 9162002 9 Quick Question Is 52x 02x Li 2 9162002 10 5quot Example x3 is n0tO1000000 x2 Assume X3 S C1000000 X2 X3 S 1000000 C X2 positive for positive X X 5 1000000 C There is no value of C and k because 1000000C is a constant and X can be more than that constant 9162002 1 1 5 Application to Algorithmic Analysis HasDuplicatelist foreach location1 in list foreach location2 in list next location2 if location1 location2 return true if listlocation1 listlocation2 return false 0 Double loop amp two compares means 2nn total 0 Algorithm is 0n2 f1 l gt1 39 IT 9162002 12 39 5 BigOmega Notation fx is Q ggtlt if there exist constants C and k such that fgtlt 2 Cggtlt Just flipped comparison 0 Algorithm F fgtlt performs no betterthan algorithm G ggtlt for large inputs 39 723quot l 39 IT quot 9162002 13 39 5 BigTheta Notation fX is e gX if fX is 0 gX and fX is 2 9X Algorithm F fgtlt performs the same as algorithm G ggtlt for large inputs Lots of people say bigoh when they mean bigtheta Defines an equivalence class i If quot 9162002 14 39 1 BigTheta Arithmetic Assuming f1X is glgtlt 1300 is 992gtlt 39 121quot3912X is ex maXg1Xr 9200 39 1112X is ex 9100 9200 o If fX is a polyn of degree cl then fX is Xd If fX is gx and gX is hx then fX is hgtlt e39 i 39 xi quot 9162002 15 t 5 Next up Analysis of Algorithms Li Zr quot 7 9162002 16 5quot Analysis Example 1 foreach location in list istocation 1 foreach location in list istocation 2 Both loops are n Do one then the next so fgtlt ggtlt So algorithm is G maxnn Gn e39 l k IT quot 9162002 17 5 Analysis Example 2 functionist foreach location in list istocation 2 foreach location in list functionist Both loops are n 0 Do function for every outer loop so fX ggtlt So algorithm is G n n Gn2 e39 l k IT quot 9162002 18 5 Analysis Example 3 foreach location1 in list foreach location2 in list listlocation1 listlocation2 foreach location in list listlocation 3 QC Double loop is QC Single loop is QC Combined complexity is QC Polynomial rule says it is l k IT quot 9162002 19 5 Common Terminology fX is egx fX is 0f0r0 ergx fX is k a constant time algorithm fX is logn a logarithmic time algorithm fX is n a linear time algorithm fX is Gn2 a quadratic time algorithm fX is nk a polynomial time algorithm fX is kn a exponential time algorithm fX is n a factorial time algorithm l 39 IT quot 9162002 20 39 5 Common Terminology cont 0 Best W0r5t A verageCase the fewest most and average number of operations Tractabe Polynomial worstcase Intractabe Not polynomial worstcase Limit the input to make problem tractable Go for approximate solutions using tractable alg UnsoIabe No algorithm exists Example Halting problem 9162002 21 Quick Question 0 My dumb duplicate finder was OnZ Matt start j at i1 better but still On2 Stephen and John sort then compare X to x1 Sort is On log n compare is On Is the Stephen and John method better 39 723quot l k IT quot 9162002 22 55 Find Pairs WorstCase Performance Slow Double Loop Fast Double Loop Sort And Scan 8 nquot2 22 nquot2 8n logn U c o 2 L U o E o O O l ll ll l l lll ll ll llllill l lTTl39lTTTGTTFGTTGTTTUTT N 0 Vquot LO CO I 1 CD List Size No Duplicates 1000 random lists for each data point 9162002 Find Pairs Average Performance M00 00 OO 00 U c 0 U a U o E o O 0 39llqQrb39l 5099 614chng List Size 0 About 7 duplicates 1000 random lists for each data point 9162002 Slow Double Loop Fast Double Loop Sort And Scan 2 nquot2 8n logn CSci 243 Discrete Structures Lecture 6 Logic 2 992002 1 Outline 0 Review 0 Logic Proofs Without Tables 0 Some Practice Problems 992002 Review P NOT PVQI OR P Q XOR PAQ AND P gtQ IF PHQIFF Quantification VX PX FORALL EIX PX EXISTS Z Vx Type constraintx statementx Nega on lt2gt IP V IQ lt2gt IP IQ uVX PX ltgt EIX PX 43X PX ltgt VX PX 992002 Quick Question 0 Recall Fermat s Last Theorem x y 2 has no integral solutions for X y and 2 when ngt2 Rewrite using existential quantifiers Use Z notation for types and constraints 3 395 992002 4 55 Implication Reviewed Implication Cause and Effect 0 Not really No time involved QC Prove P gtQ is the same as P Q 992002 Proofs Using Laws Writing a table for a big expression is tedious Why not use laws like DeMorgan s Transform the equation preserving meaning Reach goal form or reach true or false 3 395 992002 6 55 Laws With Names page 17 Identity pATcgtp vacgtp Domination pAFCgtF vacgtT Idempotent pApcgtp pvpltgtp Double Neg p cgt p Commutative pchgtqu pvqcgtqvp Associative p A q A r cgt p A q A r pvqucgtpvltJvr Distributive p v q A r cgt p v q A p v r PAquCgtPAQvPAr Li 3r 395 992002 7 55 Laws Without Names page 18 p Ip C T pA pcgtF 39 P gtCCgt PCI 992002 Example Prove p v p q cgt p q 39 P v p A CD Cgt l3 v p A P v CI Cgt T A P v CI Cgt l3 v CI A T Cgt P v CI Q PA CI 992002 More Than One Way To Kill A Cat Prove p v p q cgt p q pv pAq CHPA HDAq CHEM pv q Q PAODV CI Cgt pApv pA q cgtFv p q ltgt p uqF Q PA CI L 39 IT quot 992002 10 39 5 Quick Question 0 Show that p q gt p q is a tautology don t look on p79 0 1 How to do it 0 2 DO it 992002 CSci 243 Discrete Structures Lecture 14 Mathematical Induction III 1042002 1 Outline Finish Line Crossings Problem Strong Induction When to Use Strong Induction Preview of Next Lecture ii 39i 1042002 2 quot54 0 Line crossings may be interesting Tron Light Cycles Line Crossings Ques 39 What is the maximum number of intersectio oints for a plane containing n Hnes f1 0 1042002 4 quot Line Crossings cont Ques 39 What is the maximum number of intersectio oints for a plane containin Hnes f1 0 f2 1 01 Li 3139quot 1042002 5 a 5 Line Crossings cont Ques 39 What is the maximum number of intersectio oints for a plane containin Hnes f3 3 12 f1 0 f2 1 01 L 31139 1042002 6 39 15 Line Cros ings cont What is the maximum number of oints for a plane containin f1 O f2 1 01 f3 3 12 f4 6 33 y 131739 104 02 7 3955 Line Cros ings cont What is the maximum number of oints for a plane containin 39 f2 1 0 f3 3 12 Y f4 6 33 f5 10 64 y 131739 104 02 8 3955 Recursive Definition of fn O A 5 v 9 Can express fn as a function of fnl and n fn But how do we get fn in terms of n only A closed form solution Li 17 7 1042002 9 55 ClosedForm for u fn1 n 1 0 f6 f5 5 But f5 f4 5 1 a 4 5 39 f6 f3 3 4 5 39f6f2 2345 f6f1 12345 But f1 O 39f60 12345 Just the sum from 1 to nl Li 31139 1042002 10 39 15 ClosedForm fn cont 39 Recall 123n I11 fn is the sum up to nl fn n 1n 1042002 But Is Our fn Guess Right 71 1n Is our guess f n right Prove by induction Base Case f1 O12 One line has no crossings Inductive Hypothesis Check fn gt fn1 1042002 12 55 But Is Our fn Guess Right cont n 1n is true If fn 1 quotn also true Is fn1 Direct proof start with Pn and prove Pn1 If we have n lines and then add one line As long as the new line is not parallel it will cross all the other n lines 7 new crossings 1 nquot I 1042002 13 3955 But Is Our fn Guess Right cont so fn1fnn 1042002 n 1nn fn1 2 Reuse Pn fltn1n 12n2n fn 1 W fn 1 nn 1 True 2

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

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

#### "I made $350 in just two days after posting my first study guide."

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

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

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