### Create a StudySoup account

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

Already have a StudySoup account? Login here

# LOGIC, SETS, AND FUNCTIONS C S 313K

UT

GPA 3.8

### View Full Document

## 32

## 0

## Popular in Course

## Popular in ComputerScienence

This 4 page Class Notes was uploaded by Ryley Lang on Sunday September 6, 2015. The Class Notes belongs to C S 313K at University of Texas at Austin taught by Vladimir Lifschitz in Fall. Since its upload, it has received 32 views. For similar materials see /class/181668/c-s-313k-university-of-texas-at-austin in ComputerScienence at University of Texas at Austin.

## Popular in ComputerScienence

## Reviews for LOGIC, SETS, AND FUNCTIONS

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

CS313K Logic Sets and Functions Fall 2010 Problem Set 1 In nite Sequences The in nite sequence of numbers A1 A2 is de ned by the condition A 7 n 1 if n is even F n 7 1 otherwise 11 Calculate the rst 6 members of this sequence 11123456 A Find a single formula for An that works for all numbers both even and odd 12 Find all values of n for which An lt 5 13 Sequence A contains every integer that is greater than 1 True or false 14 Number 10 occurs in sequence A two times True or false By Bn we denote the sum of all numbers from 1 to n Bnl2n On stands for the sum of the squares of these numbers and Dn for the sum of their cubes 0 1222 n2 Dn1323n3 Numbers B On Dn can be also described using sigma notation77 For instance the formula D100 13231003 written in sigma notation looks like this 100 43 D100 E i i1 C8313K Logic Sets and Functions Fall 2010 Problem Set 3 Recursive De nitions A function is a rule that applies to a number and produces a number If a function f is applicable to a number x then we say that f is de ned on m The result of applying 1 to z is called the value of f at z and denoted by 1 lf the numbers that f is de ned on are arbitrary positive integers then we can think of f as an in nite sequence of values 17 27 A recursive de nition of a function 1 shows how to compute x if we know the values of f at some points other than m For example7 a function 1 de ned on all positive integers can be characterized by two equations one for 17 and the other de ning fn 1 in terms of Here is a recursive de nition of the sequence B from Problem Set 1 B1 17 Bn1 Bnn 1 There are two ways to nd B5 using this de nition One is to nd rst B27 B3 and B4 B2B121237 B3B233367 B4B3464107 B5B45105l5 The other possibility is to form a chain of equalities that begins with B5 and ends with a number B5 B4 5 B345Bs9 Bz39B212 B1212B114 1 14 15 31 Here is a recursive de nition of the factorial function 0 17 71 1 71 71 1 Show how to calculate 5 using each of the two methods above 32 Consider the function de ned by the formulas f 0 0 m 1 M Find f1 and f2 De ne 1 using sigma notation instead of recursion 33 For any nonnegative integer 71 let n be the product of all odd numbers from 1 to 271 1 fn1352n1 Give a recursive de nition of this function and check that your de nition gives the correct value for f 34 Express the function from the previous problem in terms of factorials Check that your formula gives the correct value for f 35 Consider the function de ned by the formulas f0 0 m 1 W 1 Find fn for n 1 4 Guess what a formula for fn might be Prove that this formula is correct 36 Consider the function de ned by the formulas f0 1 m 1 2M 71 Find fn for n 1 4 Guess which values of n satisfy the condition n gt 2 Prove your conjecture Recursive de nitions can be written in a different format as a set of cases instead of a set of equations For instance the recursive de nition of factorial can be rewritten as 1 if n 0 nl i n 7 1 71 otherw1se Recursive de nitions in the case format can be easily translated into Java for instance public static int factint n if n0 return 1 else return factn1n 37 Rewrite the recursive de nitions of sequence B and of the function from Problem 5 in the case format The Fibonacci numbers are de ned by the recursive equations f11 n 2 M NH 38 Find the rst 10 Fibonacci numbers Rewrite the de nition of Fibonacci numbers in the case format 39 A function 1 de ned on nonnegative integers7 satis es the Fibonacci equation fn2fnfn1 If f1 1 and f4 2 then what is the value of f0 310 The function f is de ned by the condition 7 7710 ifngt1007 n 7 ffn 117 otherwise for any nonnegative integer 71 Find f98

### 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 used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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

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