### Create a StudySoup account

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

Already have a StudySoup account? Login here

# ANALYSIS OF PROGRAMS C S 336

UT

GPA 3.8

### View Full Document

## 28

## 0

## Popular in Course

## Popular in ComputerScienence

This 6 page Class Notes was uploaded by Ryley Lang on Sunday September 6, 2015. The Class Notes belongs to C S 336 at University of Texas at Austin taught by Alan Cline in Fall. Since its upload, it has received 28 views. For similar materials see /class/181666/c-s-336-university-of-texas-at-austin in ComputerScienence at University of Texas at Austin.

## Popular in ComputerScienence

## Reviews for ANALYSIS OF PROGRAMS

### 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: 09/06/15

3 b Present a combinatorial argument that for all positive integers 71 271 71 2 2 71 71 2 Consider two distinct setsl and B each of size 71 Since they are distinct the cardinality of A U B is 2 The number of ways of choosing a pair of elements 211 from A U B is 2 Alternatively recognize that to get such a pair of elements from A U B one might choose both from A both from B or one from each If 71 both come from A there are 2 possibilities We get the same number if both elements come from B Finally if one element comes from each off and B then 2 4 Using a combinatorial argument prove that for n 2 l 67 2quot k0 k 7 Let A and B be disjoint sets of cardinality 71 each and C AUB How many subsets of C are there of cardinality n We are selecting elements for such a n 211 there are n2 possibilities The total is 2 J n2 and this must equal 2 subset without repletion not with concern for order so there are 2 such subsets Alternatively let k represent the number of elements in such a subset that were selected from A The value of k may vary from 0 to 71 There are such selections of the k elements from A Now select which k elements from B will not be in the subset the k that remain will thus be in the subset There are 2 2 of selecting these so ways of selecting the subset and ways overall This must equal 7 3 Present a combinatorial argument that for all n 2 l n Elk 3 Letl M h c and consider all strings of length n using elements ofl Since there are three options for each component of the string there are 3quot such strings Alternatively consider first consider the positions of any 639s in the string Let k represent the number of 1391013916395 ie a39s and 539s in the string Clearly k could range 71 from 0 through 71 For a xed value of k there are k ways to choose the positions for the 1391013916395 Then for each of the k positions there are two options ie a or b for the character in the position The remaining nk positions must be n H occupied by c39s Thus there are k ways to assign elements to the positions quot n k n With k 1391013916395 The total is Z k 2 and this must equal 3 k0 b Present a combinatorial argument that for all nonnegative integers p r and n satisfying psSn lquotllquot Pll quot YPHl KPJK S J KPHJK P J Hint Consider choosing two subsets Let a setl have n elements and consider how many ways there are to select disjoint subsets B and C off so that B has p elements and C has 5 elements First we could 71 select the 7 elements for B in ways and then select the 5 elements for C from P n P the remaining np elements of A N B in ways Together this yields 3 n n p such selections Alternatively we could first select the 73 elements p s n for B UC in ways and then select the 7 elements for B from B UC in p s p s n p s ways There are thus such selections and this must equal P P p s n n p p s 8 3 Present a combinatorial argument that for all n 2 1 Z quotl 2quot 1 W Note The summation begins with k 1 Consider the cardinality of the set of nonempty subsets of a set A of n elements For each element of A there are two options either be present in a subset or not Thus there are 2quot total subsets but one of these is empty so there are 2quot 1 non empty subsets of A Alternatively let k indicate the cardinality of the subset Since we are counting nonempty subsets k ranges from 1 to n For a xed value of k 71 there are ways of selecting the k subset elements from the 71 total elements of n A Adding this to include all possible cases of k we obtainZ kJ and this must k1 equal 2quot l b Present a combinatorial argument that for all integers k and n satisfying 3 S k S n n n 3 n 3 n 3 n 3 3 3 k k k 1 k 2 k 3 Hint Consider three special elements Consider the number of subsets of size k of a set E of cardinality 71 Since 71 Z 3 we may select three elements b1 b2 b3 of B and let C EN b1 b2 b3 Thus C has n cardinality n3 and B C Ub1 b2 b3 We know there are k such subsets Alternatively to select k elements of B for a subset there are four options all k come from C kl come from C and the kth is either b1 b2 or b3 kZcome from C and the klst and kth are exactly two of b1 b2 or b3 or k3 come from C and all n 3 of b1b2 and b3 are present For the first option there are k J possibilities since all k come from C For the second option there are possibilities since kl elements are selected from C and one from the three of b1 b2 or b3 For the third option there are possibilities since kZ elements are selected from C and one from the three of b b or b3 is not selected Lastly if k3 come 1 2 3 from C and all of b1b2 and b3 are present then there are 3 options The n 3 n 3 n 3 n 3 71 total is 3 3 and this must equal k k l k 2 k 3 k 9 Present a combinatorial argument that for all positive integers mn and r satisfying rSminmn mn m n l r mum Hint Consider selecting from two sets Let A and B be disjoint sets of cardinalities m and 71 respectively Let C A U3 and consider the number of subsets of C of cardinality r Since l C ll A l 3 m 71 there are m n such subsets Alternatively let k be the r number of elements in a subset that came from A The value of k can range from m 0 to r For a xed value of k there are k ways to select the k elements from n A and k ways to select the remammg r k elements from B thus r m n m 71 2 total ways Th1s must equal H k r k r Combinatorial Arguments These are not algebraic arguments There may be a tiny bit of algebra involved but in general the entirety of the argument hangs on combinatorics The format for the proofis this a Present a model ie a combinatorial problem quotHow many subsets quot quothow many strings quot whatever b Solve the problem with an answer that looks like the left hand side of the equation c Solve the problem with an answer that looks like the right hand side of the equation Since the problem has only one solution the right side must equal the left side The way to figure out the model is to sure at both sides and see if one side sugests itself as the count of something When you see products and powers you know that suggest independent options When you see sums you know that suggests eitheror type of cases Examples 1 2quot How I figured it out I see the 2quot and immediately think that there are 2 options on each of 7 choices Like maybe having a bit string oflength 71 since for each position there is the option of having a 0 or a 1 I look at the left hand side and see the summation That suggest cases 7 and the cases are indexed by the Variable e Lastly e takes on all Values from 0 through 71 So how could I bust the bit string problem into such cases Idea let e be the 7 number of 139s present in the bit string There are 71 positions in the string and k ways to select the k positions holding 139s so this fits That was the thinking Here is the Proof Consider a model of strings oflength n containing either 039s or 139s Since for each of the npositions there are two options 7 and the options are independent there are 2quot such strings This agrees with the right hand side To argue the left hand side let e be the number of 139s in such a string The number of 139s Varies from 0 through 71 and for a fixed number e quotl quot quotl of 139s there are Kk ways to position the 139s Thus the summation from must equal 160 2quot

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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

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