### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction to Computing Explorations in Language, Logic, and Machines CS 1120

UVA

GPA 3.71

### View Full Document

## 6

## 0

## Popular in Course

## Popular in ComputerScienence

This 19 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 1120 at University of Virginia taught by David Evans in Fall. Since its upload, it has received 6 views. For similar materials see /class/209651/cs-1120-university-of-virginia in ComputerScienence at University of Virginia.

## Reviews for Introduction to Computing Explorations in Language, Logic, and Machines

### 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/21/15

Chapter 4 Procedures A great discovery solves a great problem but there is a grain of discovery in the solution of any problem Your problem may be modest but if it challenges your curiosity and brings into play your inventive faculties and if you solve it by your own means you may experience the tension and enjoy the triumph of discovery George Polya Computers are tools for performing computations The reason we want to perform a computation is to solve a problem In this chapter we consider what it means to solve a problem and explore some strategies for constructing procedures that solve problems 41 Solving Problems Traditionally a problem is an obstacle to overcome or some question to answer Once the question is answered or the obstacle circumvented the problem is solved and we can move on to the next one When we talk about writing programs to solve problems however we usually have a larger goal We don t just want to solve one instance of a problem we want a procedure that can solve all instances of a problem A problem is de ned by its inputs and the desired property of the output A solution to a problem is a procedure that produces a correct output for all possible 41 4 2 CHAPTER 4 PROCEDURES Input Output Procedure Figure 41 Procedure inputs to the problem as shown in Figure 41 For the procedure to be useful it should also have the property that it always pro duces an output 7 that is it always nishes executing A procedure that solves a problem and is guaranteed to always nish is called an algorithm The name al gorithm is a Latinization of the name of the Persian mathematician and scientist Muhammad ibn Musa al Khwarizmi who published a book in 825 on calcula tion with Hindu numerals Al Khwarizmi was also the responsible for de ning algebra Although the name was not adopted until after al Khwarizmi s book al gorithms go back much further than that The ancient Babylonians had algorithms for nding square roots more than 3500 years agol Some programs are intended to provide a service rather than just one output For example a web server is a program that is intended to run forever not to nish and produce an output It keeps running and responding to new requests as they come in Even programs that are services however involve algorithms Each individual web request is a problem and the server program should respond to it with a particular output sending the requested page within a nite amount of time Our goal in solving a problem is to devise a procedure that takes inputs that de ne a problem instance and produces as output the solution to the problem There is no magic wand for solving all problems but at its core most problem solving involves breaking problems you does not yet know how to solve into simpler prob lems until you nd problems simple enough that you already know how to solve them The trick is to nd the right subproblems so that they can be combined to 1Donald E Knuth Ancient Babylonian Algorithms Communications of the ACM July 1972 42 COMPOSING PROCEDURES 4 3 Input Output Figure 42 Composition solve the original problem The following sections describe a few techniques for solving problems and illustrate them with some simple examples We will use these same problem solving techniques over and over throughout this book In the examples here we limit ourselves to simple data all of the problems have one or more numbers as their input and produce a number as output In the next chapter we introduce structured data and revisit these problem solving techniques 42 Composing Procedures One way to divide a problem is to split it into steps where the output of the rst step is the input to the second step and the output of the second step is the solution to the problem Each step can be de ned by one procedure and the two procedures can be combined to create one procedure that solves the problem Figure 42 shows a composition of two functions f and g The output off is the input to g We can express this composition with the Scheme expression g f x where x is the input The order appears to be reversed from Figure 42 That is because we apply a procedure to the values of its subexpressions That means although f appears to the right of g in the expression the subexpression f x is evaluated rst since the evaluation rule for the outer application expression is to rst evaluate all the subexpressions We can de ne a procedure that implements the composed procedure by making X a parameter 44 CHAPTER 4 PROCEDURES define foq lambda x g f x This de nes f oq as a procedure that takes one input and produces as output the composition of f and g applied to the input parameter The works for any two procedures as long as both procedures take a single input parameter For example we could compose the square and cube procedures from Chapter 3 as define sixthipower lambda x cube square x So sixthipower 2 evaluates to 64 421 Procedures as Inputs and Outputs So far all the inputs we have seen have been numbers But the subexpressions of an application can be any expression including a procedure We call a procedure that takes other procedures as inputs or that produces a procedure as its output a higherorder procedure Higher order procedures give us the ability to write general procedures that behave differently based on not just number value inputs but based on procedures that are passed as inputs to the general procedure For example we can create a generic composition procedure by making f and g parameters define foq lambda f q x q f x The f oq procedure takes three parameters The rst two are both procedures that take one input The third parameter is a value that can be the input to the rst procedure For example gt foq square cube 2 gt foq lambda x x 1 square 2 9 42 COMPOSING PROCEDURES 4 5 In the second example the rst parameter is a new procedure lambda X X 1 This procedure takes a number as input and produces as output that number plus one We de ne inc short for increment to name this procedure define inc lambda X X l A more useful composition procedure would separate the input value X from the composition It takes two procedures as inputs and produce as output a procedure that is their composition define compose lambda f g lambda X g f X The body of the compo se procedure itself makes a procedure Hence the result of applying compose to two procedures is not a simple value but a procedure To get a value we need to apply the result of the application of compose to a value For example gt compose inc inc ltproceduregt gt compose inc inc 1 gt define siXthipower compose square cube gt siXthipower 3 Exercise 41 a What does compose lambda X X X 2 lambda X X 2H 4 6 CHAPTER 4 PROCEDURES evaluate to 9 What does compose lambda X X 2 lambda X X 2 150 evaluate to What does 5 compose compose inc inc inc 2 evaluate to Exercise 42 Suppose we de ne se 1 f ecompo s e as a procedure that composes a procedure with itself define selficompose f compose f f Explain how compose selficompose selficompose inc 1 would be evaluated I Exercise 43 De ne a procedure compo se 3 that takes three procedures as input and produces as output a procedure that is the composition of the three input pro cedures For example compo se3 abs inc square 75 should evalu ate to 36 Try de ning compo s e 3 rst without using compo s e and then de ne it using compose I 43 RECURSIVE PROBLEM SOLVING 4 7 Procedure Output Figure 43 Circular Composition 43 Recursive Problem Solving In the previous section we used functional composition to break a problem into two procedures that can be composed to produce the desired output A particularly useful variation on this is when we can break a problem into two problems where one of them is a smaller version of the original problem The goal is to be able to feed the output of one application of the procedure back into the same procedure as its input for the next application as shown in Fig ure 43 Here s what this would look like in a Scheme procedure define f lambda n f 7 n l Of course this doesn t work very well2 Every time an application of f is eval uated it results in another application of f to evaluate We keep evaluating new applications but never stop and can never produce an output What we need is a way of stopping The circular applications could stop when the input to the procedure is simple enough that we can produce the output without needing another application of the procedure This is called the base case simi larly to the grammar rules in Section 24 In our grammar examples the base case usually involved replacing the nonterminal with nothing eg moredigits 22 6 In problem solving the base case will be some input for which the problem is so 2The curious should try entering this de nition into a Scheme interpreter and evaluating an application of f 10 If you get tired of waiting for an output in DrScheIne you can click the Stop button in the upper right corner to interrupt the evaluation 4 8 CHAPTER 4 PROCEDURES simple we already know the answer When the input is a number this is often but not always when the input is zero To de ne a recursive procedure we need to use an if expression to test if the input matches the base case input If it does the consequent expression is the known answer for the base case Otherwise we enter the recursive case and apply the procedure again Each time we apply the procedure we need to make progress towards reaching the base case This means the input has to change in a way that gets closer to the base case input If the base case is a small number and the input starts greater than that number one way to get closer to the base case input is to subtract 1 from the input value with each recursive application Here is a procedure that does this define g lambda n if n O l g U l Unlike the earlier circular f procedure if we apply g to a positive number it will eventually produce an output For example consider evaluating g 3 When we evaluate the rst application the value of the parameter n is 3 so the predicate expression n O evaluates to f and the value of the procedure body is the value of the alternate expression g 7 n l The subexpression 7 n l evaluates to 2 so the result is the result of applying g to 2 As with the previous application this leads to the application g 7 n l but this time the value of n is 2 so 7 n l eval uates to 1 The next application leads to the application g 0 This time the predicate expression evaluates to t and we have reached the base case The con sequent expression is just 1 so no further applications of g are performed The value 1 is the result of the application g 0 This is returned as the result of the g l application in the previous recursive call and then as the result of the g 2 application and nally as the output of the original g 3 We can think of the recursive evaluation as winding until the base case is reached and then unwinding the outputs back to the original application For this pro cedure the output is not very interesting no matter what positive number we 43 RECURSIVE PROBLEM SOLVING 4 9 apply g to the eventual result is 1 To solve interesting problems with recursive procedures we need to accumulate results as the recursive applications wind or unwind Examples 43 and 44 illustrate recursive procedures that accumulate the result during the unwinding process Example illustrates a recursive procedure that accumulates the result during the winding process Example 41 Factorial How many different arrangements are there of a deck of 52 playing cards The top card in the deck can be any of the 52 cards so there are 52 possible choices for the top card The second card can be any of the cards except for the card that is the top card so there are 51 possible choices for the second card The third card can be any of the 50 remaining cards and so on until the last card for which there is only one choice remaining To determine the total number of possible arrangements we need to multiply the number of choices for each card 525l502l This is known as the factorial function denoted in mathematics using the excla mation point eg 52 It is de ned as l n 0 t 39 l fac Una n gtk factorialm 7 l n gt 0 The mathematical de nition of factorial is recursive so it is natural that we can de ne a recursive procedure that computes factorials define factorial n if n O l x n factorial 7 n l We can now determine the number of deck arrangements gt factorial 52 80658175170943878571660636856403766975289505440883277824000000000000 The f act ori al procedure has structure very similar to our earlier de nition of the useless recursive g procedure The only difference is the alternative expres sion for the if expression with q we used g 7 n l with factorial we added the outer application of 2 x n factorial 7 n l Instead 4 10 CHAPTER 4 PROCEDURES of just evaluating to the result of the recursive application we are now combin ing the output of the recursive evaluation with the input h using a multiplication application Exercise 44 When Karl Gauss was in elementary school his teacher as signed the class the task of summing the integers from 1 to 100 eg l 2 3 100 to keep them busy Being the future Prince of Mathematics Gauss developed the formula for calculating this sum that is now known as the Gauss sum Had he been a computer scientist however and had access to a Scheme interpreter in the late 1700s he could have instead de ned a recursive procedure to solve the problem De ne a recursive procedure gaussisum that takes a number n as its input parameter and evaluates to the sum of the integers from 1 to n as its output For example gaus sisum l O O should evaluate to 5050 I 44 Evaluating Recursive Applications Evaluating an application of a recursive procedure follows the evaluation rules just like any other expression evaluation It may be confusing however to see that this works because of the apparent circularity of the procedure de nition Here we show in detail the evaluation steps for evaluating factorial 2 The evaluation and application rules refer to the rules summary in Section 38 We rst show the complete evaluation following the substitution model evaluation rules in full gory detail and later consider a subset containing the most revealing steps The evaluation rule for an application expression does not specify the order in which the subexpressions are evaluated A Scheme interpreter is free to evaluate them in any order Here we choose to evaluate the subexpressions in the order that is most readable l factorial 2 Evaluation Rule 3a Application subexpressions 2 factorial 2 Evaluation Rule 2 Name 3 lambcla n if n O l x n factorial 7 n l 2 Evaluation Rule 4 Lambda 44 EVALUATING RECURSIVE APPLICATIONS 4 11 4 Iambda n if n O 1 n factorial n 1 2 Evaluation Rule 1 Primitive 5 Iambda n if n O 1 n factorial n 1 2 Evaluation Rule 3b Application Application Rule 2 6 if 2 O l r 2 factorial 7 2 1H Evaluation Rule 5a If predicate T if 2 0 l l 2 factorial 7 2 1n Evaluation Rule 3a Application subexpressions 8 if 3 2 g l l 2 factorial 7 2 1n Evaluation Rule 1 Primitive 9 if 2 O l r 2 factorial 7 2 l Evaluation Rule 3b Application Application Rule 1 10 if 1 2 factorial 7 2 1n Evaluation Rule 5b If alternate 11 2 factorial 7 2 1H Evaluation Rule 3a Application subexpressions 12 2 factorial 7 2 1H Evaluation Rule 1 Primitive 13 2 factorial 7 2 1 Evaluation Rule 3a Application subexpressions 14 2 factorial 7 2 1 Evaluation Rule 3a Application subexpressions 15 2 factorial 2 l Evaluation Rule 1 Primitive factorial 2 1 Evaluation Rule 3b Application Application Rule 1 factorial 1 Continuing Evaluation Rule 3a Evaluation Rule 2 Name lambda n if n O l t n factorial 7 n l 1 Evaluation Rule 4 Lambda Iambda n if n O 1 n factorial n 1 1 Evaluation Rule 3b Application Application Rule 2 1 1 53 a a N N 9 Aa N gt9 r N 20 2 if 1 0 l 1 factorial 7 1 l Evaluation Rule 5a If predicate 21 2 if 1 0 l l 1 factorial 7 1 l Evaluation Rule 3a Application subexpressions 22 2 if 1 g l l 1 factorial 7 1 l 23 24 25 26 27 28 29 N N N N N N N N N N N CHAPTER 4 PROCEDURES Evaluation Rule 1 Primitives if 10 l 1 factorial 711 Evaluation Rule 3b Application Rule 1 if 1 l 1 factorial 711nm Evaluation Rule 5b If alternate 1 factorial 1 l Evaluation Rule 3a Application 1 l factorial 1 l Evaluation Rule 1 Primitives 1 factorial 71 l Evaluation Rule 3a Application 1 factorial 71 l Evaluation Rule 3a Application 1 factorial 1i Evaluation Rule 1 Primitives 1 factorial 1 1 Evaluation Rule 3b Application Application Rule 1 1 factorial O Evaluation Rule 2 Name 1 lambda n if n 0 l Evaluation Rule 4 Lambda n factorial 0 J in l 1 Iambda n if n O 1 n factorial n 1 O Evaluation Rule 3b Application Rule 2 1 if O O l a O factorial 7 O l Evaluation Rule 5a If predicate if O O l k 0 factorial 7 O l Evaluation Rule 3a Application subexpressions if 3 O Q l a O factorial 7 O l Evaluation Rule 1 Primitives 1 if O O l a O factorial 7 O l Evaluation Rule 3b Application Application Rule 1 1 if 1 l 4x 0 factorial 7 O l Evaluation Rule 5b If consequent 1 l Evaluation Rule 1 Primitives 1 1 Evaluation Rule 3b Application Application Rule 1 44 EVALUATING RECURSIVE APPLICATIONS 4 13 41 2 1 Evaluation Rule 3b Application Application Rule 1 42 3 Value reached The key to evaluating applications of recursive procedures is the evaluation rule for the if special form If the if expression were evaluated like a regular appli cation all subexpressions would be evaluated and the alternative expression with the recursive call would never nish evaluating Since the evaluation rule for if requires that the predicate expression is evaluated and the alternative expression is not evaluated when the predicate expression is true the circularity in the de nition ends when the predicate expression evaluates to true This is the base case of the recursion when n O evaluates to true This occurs when factorial O is evaluated and instead of producing another recursive call it evaluates to the value of the consequent expression 1 Exercise 45 These exercises test your understanding of the f act ori al 2 evaluation Try to answer them yourself before reading the remainder of this section 9 In step 5 the second part of the application evaluation rule Rule 3b is used In which step does this evaluation rule complete 9 In step 11 the rst part of the application evaluation rule Rule 3a is used In which step is the following use of Rule 3b started 9 In step 25 the rst part of the application evaluation rule Rule 3a is used In which step is the following use of Rule 3b started 9 How many times is Evaluation Rule 5 If used in evaluating factorial 2 D In order to evaluate fact 0 ri al 3 how many times would Evaluation Rule 2 be used to evaluate the name f act 0 ri al Exercise 46 For what input values 11 with an evaluation of factorial n reach a value For values where the evaluation is guaranteed to nish make a 4 14 CHAPTER 4 PROCEDURES convincing argument why it must nish For values where the evaluation does not nish explain why I Example 42 Maximum In Chapter 3 we saw a procedure max that takes two inputs and evaluates to the greater input Here we consider the problem of de ning a procedure that takes as its input a procedure a low value and a high value and outputs the maximum value the input procedure produces when applied to an integer value between the low value and high value input We will name the inputs f l ow and high To nd the maximum the f inclemaximum procedure should evaluate the input procedure f at every integer value between the l ow and high and produce as output the greatest value found To de ne the procedure we need to think about this in a way that allows us to combine results from simpler problems to nd the result For the base case we need to identify a case so simple we already know the answer Consider the case when l ow and hi gh are equal Then there is only one value to use and we know the value of the maximum is f l ow So the base case is if low high f low Alternate Expression How to we make progress towards the base case Suppose the value of high is equal to the value of l ow plus 1 Then the maximum value is either the value of f low or the value of f low 1 We could select it using the max procedure max f low f low 1 Of course we can extend this to the case where high is equal to the value of l ow plus 2 max f low max f low 1 f low 2 The second operand for the outer max evaluation is the maximum value of the input procedure between the low value plus one and the high value input If we name the procedure we are de ning f inclemaximum then this is the result of findemaximum f low 1 high This works whether high is equal to l ow plus 1 or 1 ow plus 2 or any other value greater than high Putting things together we have our recursive de nition of f inclemaximum 44 EVALUATING RECURSIVE APPLICATIONS 4 15 define fihdimaximum f low high if low high f low max f low findimaximum f low 1 high Here are a few examples gt fihdimaximum lambda x x l 20 20 gt fihdimaximum lambda x 7 10 x l 20 gt fihdimaximum lambda x x x 7 10 x l 20 25 Exercise 47 ltgt To nd the maximum of a continuous function we need to evaluate at all numbers in the range not just the integers There are in nitely many numbers between any two numbers however so this is impossible We can approximate this however by evaluating the function at many numbers in the range De ne a procedure findimaximumicoritihuous that takes as input a func tion f a low range value low a high range value high and an increment inc and produces as output the maximum value of f in the range between l ow and high where f is evaluated at low low inc low inc inc low ihc ihc inc high Here are some examples gt findimaximumicOhtihuous lambda x x x 7 55 x l 10 l 75 gt findimaximumicOhtihuous lambda x x x 7 55 x l 10 00001 75625 4 16 CHAPTER 4 PROCEDURES As the value of increment decreases we expect to nd a more accurate maximum value I Exercise 48 The f indimaximum procedure we de ned evaluates to the maximum value of the input function in the range but does not provide the input value that produces that maximum output value De ne a procedure that nds the input in the range that produces the maximum output value I Exercise 49 De ne a f incliarea procedure that takes as input a function f a low range value low a high range value high and an increment inc and produces as output an estimate for the area under the curve produced by the function f between l ow and high using the inc value to determine how many points to evaluate I 441 The Evaluation Stack We can see the structure of the evaluation process better if we focus just on the most revealing stems Here are the evaluation steps that involve applications of the f a ct o r i a l procedure extracted from the full evaluation and indented to line up the steps from each application evaluation 1 factorial 2 l7 2 factorial 1 31 2 1 factorial O 40 2 1 1 41 2 1 42 3 In Step 1 we start to evaluate f act ori al 2 The nal result of this evalua tion is found in Step 42 To evaluate f act 0 ri al 2 we follow the evaluation rules eventually reaching the body expression of the if expression in the factorial de nition This is Step 17 2 factorial 1 To evaluate this expres sion we need to evaluate the f actori al 1 subexpression We can think of each of these application evaluations as a stack A stack has the property that the rst tray pushed on the stack will be the last tray removediall 44 EVALUATING RECURSIVE APPLICATIONS 4 17 the trays pushed on top of this one must be removed before this tray can be re moved For application evaluations the elements on the stack are expressions to evaluate instead of trays To nish evaluating the rst expression all of its com ponent subexpressions must be evaluated Hence the rst application evaluation started will be the last one to nish At Step 17 the rst evaluation is in progress but to complete it we need the value resulting from the second evaluation The second evaluation results in the body expression 1 factorial 0 shown for Step 31 At this point the evaluation of factorial 2 is stuck in Evaluation Rule 3 waiting for the value of factorial 1 subexpression The evaluation of the factorial 1 application leads to the factorial O subexpression which must be evaluated before the factorial 1 evaluation can complete In Step 40 the f act 0 ri al 0 subexpression evaluation has completed and produced the value 1 Now the factorial 1 evaluation can complete producing 1 as shown in Step 41 Once the factorial 1 evaluation completes all the subexpressions needed to evaluate the expression in Step 17 are now evaluated and the evaluation completes in Step 42 Example 43 Euclid s Algorithm In Book 7 of the Elements Euclid de scribes an algorithm for nding the greatest common divisor of two non zero in tegers The greatest common divisor is the greatest integer that divides both of the input numbers without leaving any remainder For example the greatest common divisor of 150 and 200 is 50 since 150 50 evaluates to 3 and 200 5 O evaluates to 4 and there is no number greater than 50 which can divide both 150 and 200 without leaving a remainder The modul o primitive procedure takes two integers as its inputs and evaluates to the remainder when the rst input is divided by the second input For example modulo 6 3 evaluates toO and modulo 7 3 evaluates to 1 Euclid s algorithm stems from two properties of integers 1 If modul o a b evaluates to 0 then b is the greatest common divisor of a and b 2 If modulo a b evaluates to a non zero integer r then the greatest common divisor of a and b is the greatest common divisor of b and r 4 18 CHAPTER 4 PROCEDURES We can de ne a recursive procedure for nding the greatest common divisor closely following Euclid s algorithm define god a b if modulo a b O b god b modulo a b The structure of the de nition is similar to the f aot ori al de nition the proce dure body is an if expression and the predicate tests for the base case For the god procedure the base case corresponds to the rst property above It occurs when b divides a evenly and the consequent expression is b The alternate expres sion god b modulo a b is the recursive application It differs from the alternate expression in the f aot o r1 al de nition in that there is no outer ap plication expression the application We do not need to combine the result of the recursive application with some other value as was done in the f aot ori al de nition the result of the recursive application is the nal result Unlike the factorial and findimaximum examples the god procedure produces the result in the base case and no further computation is necessary to produce the nal result When no further evaluation is necessary to get from the result of the recursive application to the nal result a recursive de nition is said to be tail recursive Exercise 410 Show the structure of the applications of god in evaluating god 6 9 I Exercise 411 Provide a convincing argument why the evaluation of god a b will always nish when the inputs are both positive integers I Exercise 412 Provide an alternate de nition of f aot ori al that is tail recursive To be tail recursive the expression containing the recursive application cannot be part of another application expression Hint de ne a f aot o r1 al ihe lpe r procedure that takes an extra parameter and then de ne faot ori al as 45 SUMMARY 4 19 define factorial n factorialihelper n 1 I Exercise 413 am Provide an alternate de nition of f indimax that is tail re cursive I Exercise 414 Provide a convincing argument why it is always possible to transform a recursive procedure into an equivalent procedure that is tail recursive I 45 Summary By breaking problems down into simpler problems we can develop solutions to complex problems Many problems can be solved by combining instances of the same problem on simpler inputs When we de ne a procedure to solve a problem this way it needs to have a predicate expression to determine when the base case has been reached a consequent expression that provides the value for the base case and an alternate expression that de nes the solution to the given input as an expression using a solution to a slightly smaller input Our general problem solving strategy is Be optimistic Assume you can solve it N Think of the simplest version of the problem something you can already solve This is the base case U Consider how you would solve a big version of the problem by using the result for a slightly smaller version of the problem This is the recursive case 5 Combine the base case and the recursive case to solve the problem For problems involving numbers the base case will often be when the input value is 0 but not always as we saw in the f indimaximum value where the base

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

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

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