### Create a StudySoup account

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

Already have a StudySoup account? Login here

# DATA STRUCTURES CS 261

OSU

GPA 3.95

### View Full Document

## 10

## 0

## Popular in Course

## Popular in ComputerScienence

This 14 page Class Notes was uploaded by Mrs. Maximo Lueilwitz on Monday October 19, 2015. The Class Notes belongs to CS 261 at Oregon State University taught by R. Metoyer in Fall. Since its upload, it has received 10 views. For similar materials see /class/224497/cs-261-oregon-state-university in ComputerScienence at Oregon State University.

## Reviews for DATA STRUCTURES

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

Chapter 3 Debugging Testing and Proving Correctness In this chapter we investigate tools that will help you to produce reliable and correct programs During development of any program you will undoubtedly need to remove errors and this will involve debugging Once you believe your program or portions of it is correct you will want to increase your con dence in the program by systematic testing Typically testing will uncover errors which will lead to further debugging Finally the most powerful tool you can use to increase your con dence in a program or function is a proof of correctness All of these tools are useful and none should be considered to be a substitute for the others Hints on Debugging There is no question that programming is a dif cult task Few nontrivial programs can be expected to run correctly the rst time without error Fortunately there are many hints that can be used to help make debugging easier Here are some of the more useful suggestions Test small sections of a program in isolation When you can identify a section of a program that is doing a speci c task this could be a loop or a function write a small bit of code that tests this functionality Gain con dence in the small pieces before considering the larger whole When you see an error produced for a given input try to nd the simplest input that consistently reproduces the same error Errors that cannot be reproduced are very dif cult to eliminate and simple inputs are much easier to reason about than more complex inputs Once you have a simple test input that you know is handled incorrectly play the role of the computer in your mind and simulate execution of this test input This will frequently lead you the location of your logical error Think about what occurs before the point the error is noticed An incorrect result is simply the symptom and you must look earlier to find the cause Use breakpoints or print statements to view the state of the computation in the middle Starting with an input that produces the wrong result try to reason backwards and determine what the values of variables would need to be to produce the output you see Then check the state using break points or print statements This can help isolate the portion of the program that contains the error Don t assume that just because one input is handled correctly that your program is correct Chapter 3 Debugging Testing and Proofs of Correctness 1 Use assertions and invariants to reason logically about your program Most importantly make sure you have the right mindset Don t naturally assume that just because one section of a program works for most inputs it must be correct Question everything Be open to any possibility Look everywhere Assertions and Invariants When analyzing algorithms two questions are important Is the algorithm correct and how fast does it run In this chapter we are describing techniques that can be used to address the first The second will be the subject of the next chapter One of the most powerful tools used to analyze algorithms is an assertion An assertion is simply a comment that explains what you know to be true when execution reaches a speci c point in the program Assertions can include information you know from a specific statement as well as information you know from tracing a ow of control ml triangle nt 31 ml by W C For example suppose you have written the function If f 2quot t 1 shown at the left The program takes three integer el equot re um values representing the sides ofatriangle and is return 2 intended to return a value that is 1 if the triangle is else if b 0 equilateral 2 if it is isosceles two sides equal in remm 2 length and 3 if it is scalene no sides are equal How else would you increase your confidence that you have return 3 written the correct function Assertions keep track of the information you mt triangleant a mt by int 0 know from following a path through the If a z we know a z program For example after the first if if b 0 we know ab amp bc statement we know that a is the same as b return 1 After the second statement we know that b is elset ngnow azzb and b I C V the same as c but we also remember the elserff 1225 we know alzb and b C information from the first Since a is equal to return 2 b and b is equal to c it must be the case that else we know a b and b o all three are equal Along the else path return 3 ERROR however we know that the original condition must be false and so we can carry along that information In this program keeping track of this information leads to the discovery of an error After the last else statement we know that a is not equal to b and that b is not equal to c But this does not imply as the program is claiming that all three values are different It could still be the case that a is equal to c The detection of this error has been simplified by explicitly keeping track of information using assertions Chapter 3 Debugging Testing and Proofs of Correctness 2 Assertions become most useful when they are combined with loops An assertion inside a loop is often termed an invariant since it must describe a condition that does not vary during the course of executing the loop To discover an invariant simply ask yourself why you think a program loop is doing the right thing and then try to express right thing as a statement For example the function at right is computing the sum of an array of values It does this by computing a double sum double data iht h double s 0 l s is the sum of an empty array for int i 0 i lt h i 2 s is the sum of values from 0 to i l s s datai 3 s is the sum of values from 0 to i 4 s is the sum from 0 to h l return s partial sum a sum up to a given point So assertion number 3 is the easiest to discover Once you discover assertion 3 then assertion 2 becomes clear 7 it is whatever is needed to ensure that assertion 3 will be true after the assignment Assertion 4 is stating the expected result while assertion l is asserting what is true before the loop begins Later in this chapter you will learn how to use invariants and assertions to prove that an algorithm or program is correct void bubbleSort double data int n for int i h l i gt 0 i for ihtj 0 lt i j datai is largest value in 0 j if datai gt datai1 swapdata j j1 datai l is largest value in 0 j l datai is largest value in 0 i array is sorted Notice how assertions require you to understand a high level description of what the algorithm is trying to do and not simply a low level understanding of what the individual statements are doing For example consider the bubble sort algorithm shown at left Bubble sort has two nested loops The outer loop is the position of the array being filled The inner loop is bubbling the largest element into this position So once again at the end of the inner loop you want to make an assertion not only about the particular values at index locations j and jl but about everything the loop has seen before namely the elements with index values less than j Once you identify this assertion then the assertion at the beginning of the loop must be whatever is needed to prove the assertion at the end of the loop and together these must be whatever is necessary to prove the assertion at the end of the outer loop In Worksheet 4 you will practice any writing invariants and assertions that could be used to prove the correctness Bubble Sort and Sorting Bubble sort is the first of many sorting algorithms we will encounter in this book Bubble sort is examined not because it is useful it is not but because it is very simple to analyze and understand But there are many other sorting algorithms that are far more efficient You should never use bubble sort for better alternatives real application since there are many of a variety of programs Chapter 3 Debugging Testing and Proofs of Correctness Assertions and the assertion statement Most programming languages include a statement often termed the assertion statement that performs a task that is similar but not exactly the same as the concept of the assertion described above The assertions described here are written as comments and are not executed by the program during execution They need not be written in an executable form The assertion statement on the other hand takes as argument an expression and typically will halt execution and print an error message if the statement is not true This can be very useful for verifying that input values satisfy whatever conditions are necessary for execution Our square root example from the previous chapter for example could use an assertion statement to check that the input is a positive number double sqrt double val assert val gt 0 halt execution if value is not legal Because assertion statements are executed at run time and halt execution if they are not satisfied they should be used sparingly but can be useful during debugging The wikipedia entry for assertions contains a good discussion of assertions as used for program proofs compared with assertions used for routine error checking Introduction to the Binary Search Algorithm An important algorithm that we will see many times in many different forms is the binary search algorithm Binary search is similar to the way you guess a number if somebody says I m thinking of a value between 0 and 100 Can you find my number If you have played this game you know the optimal strategy is to guess the value in the middle Is it larger or smaller than 50 Suppose the other person answers smaller Then you again divide the range is it larger or smaller than 25 By repeatedly apply this technique you very quickly find the hidden value The binary search algorithm works in a similar fashion but instead of numbers it looks for a specific value in an array of sorted numbers Like the guessing game it starts in the middle of the array in one question eliminating one half of the possibilities then in the next question breaking that subsection in half and so on One VerSIOH ofthe blnary search int binarySearchdouble data int n double test algorithm is shown at right Here data is size n sorted array n represents the number of values W W 0 in the sorted data array and the W h39gh nr whrle low lt hrgh var1able test 1s the value berng mid low high 2 seamhed for You can Verlfy that if datamid test return 1 true the algorithm is correct using the if datamid lt testValue following invariant OW mld else Biliary Search Invariant All values with index positions return 0 fase smaller than low are less than test and all values with index Chapter 3 Debugging Testing and Proofs of Correctness 4 positions larger than or equal to high are larger than or equal to test Prove to your satisfaction that the invariant is true at the beginning of the program immediately after the assignments to low and high and that it remains true at the end of the loop Note that initially the variable high is not a legal index and so the set of values with index positions larger than or equal to high is an empty set In exercises at the end of the chapter we will use these to prove the algorithm is correct Testing and Boundary Cases After you have translated an algorithm into a function or program using assertions and invariants to increase your confidence in the correctness of your code you should then always use testing to further assure yourself that your program works correctly Testing is performed at many levels You can and should test individual functions before you int main have a working application This is termed double dataSetOne 10 20 30 40 50 unit testing To perform a test you need a dQUb39ensm summataSetOne 5 H main method This is different from the main prmtlmoresun 1 ShOUId be 15 398 g 8m method you will eventually use for your um program A special purpose main method used in testing is termed a test harness The test harness will feed one or more values into the function under test and check the result The box shows a test harness for the summation program given earlier in this chapter You should never content yourself with just one test case A single test case cannot exercise all the possible ways a function can be used As you develop test cases think about the input data If there are limits to the data try to exercise values that are just at the edge of the limits If the program uses conditional statements use some data values that evaluate the condition true and others that evaluate the condition false This process is termed boundary testing For example think about testing the method min given earlier Will the method find the correct value if the minimum is the first element in the array If it is the last If it is in the middle If all values are the same What about if there is only one element What if there are no elements Create a test case for each condition and verify the result is correct A collection of test cases is termed a test suite int main double test1 10 20 30 smallest first double test2 30 20 10 smallest last double test3 20 10 30 smallest middle double test4 30 10 10 20 repeated smallest double test5 no elements double t1 t2 t3 t4 t5 t1 mintest1 3 t2 mintest2 3 t3 mintest3 3 t4 mintest4 4 printf test cases 1 2 3 and 4 g g g g n t1 t2 t3 t4 t5 mintest5 0 should generate assertion error Chapter 3 Debugging Testing and Proofs of Correctness 5 printf test case 5 g n t5 re urn 0 Notice that we expected one of these data sets to halt execution with an assertion error After verifying that this is correct you can comment out that particular test case while the others are processed In the test harness shown above we simply print the result and count on the programmer running the test harness to verify the result Sometimes it is possible to check the result directly For example if you were testing a method to compute a square root you could simply multiply the result by itself and verify that it produced the original number Question Think about testing a sorting algorithm Can you write a function that would test the result rather than simply printing it out for the user to validate Once you are convinced that individual functions are working correctly the next step is to combine calls on functions into more complex programs Again you should perform testing to increase your confidence in the result This is termed integration testing Often you will uncover errors during integration testing Once you fix these you should go back and reexecute the earlier test harness to ensure that the changes have not inadvertently introduced any new errors This process is termed regression testing Some testing considers only the structure of the input and output values and ignores the algorithm used to produce the result This is termed black box testing Other times you want to consider the structure of the function for example to ensure that every if statement is exercised both with a value that makes it true and a value that makes it false This is termed white box testing Goals for white box testing should include that every statement is executed and that every condition is evaluated both true and false Other more complex test conditions can test the boundaries of a computation Testing alone should never be used to guarantee a program is working correctly The famous computer scientist Edsger Dijkstra pointed out that testing can show the presence of errors but never their absence Testing should be used in combination with logical thought assertions invariants and proofs of correctness All have a part to play in the development of a reliable program In worksheet 5 you will think about test cases for a variety of simple programs More on Program Proofs We noted earlier in this chapter that the most powerful way to gain confidence in the correctness of a function or program is to develop a proof that the function is correct In this section we will investigate this process in more detail by examining another classic algorithm a sorting algorithm named selection sort Selection sort is easy to describe which is why we study it But like bubble sort it is also slow so is not generally used in practice In later lessons we will examine faster algorithms Chapter 3 Debugging Testing and Proofs of Correctness 6 How to sort an array using selection sort Find the index of the largest element in an array Swap the largest value into the nal location in the array Then do the same with the next largest element Then the next largest and so on until you reach the smallest element At that point the array will be sorted To develop this algorithm as executable code the first step is to isolate the smallest portion of the problem description that could be independently programmed tested and debugged In this case you might select that first sentence find the index of the largest element in an array How do you do that The best way seems to be a loop double storage size is n How do we know this small bit of code is correct As we discussed in the previous lessons there are two general techniques that forntI 1ilt n1i d d h M l b h f if storagei gt storageindeXLargest are use an you S 0u a ways use or 0 indexLargest i them These two techn1ques are proofs and testing intindexLargest 0 A proof of correctness is an informal argument that explains why you believe the code is correct As you learned earlier such proofs are built around assertions which are statements that describe the relationships between variables when the computer reaches a point in execution Using assertions you simulate the execution of the algorithm in your mind and argue both that the assertions are valid and that they lead to the correct outcome In the code fragment above we know that in the middle of execution the variable i represents some indefrnite memory location We have examined all values up to i and indexLargest represents the largest value in that range The values beyond index i have not yet been examined and are therefore unknown A drawing helps illustrate the relationships What can you say about the relationship between i indexLargest and the data array Invariants are written as comments as in the following double storage int position n 1 int indexLargest 0 for int i 1 i lt position i inv indexLargest is the index ofthe largest element in the range 0 i1 see 39 if storagei gt storageindeXLargest indexLargest i inv indexLargest is the index of the largest element in the range 0 i Chapter 3 Debugging Testing and Proofs of Correctness 7 Notice how the invariant that comes after the if statement is a simple variation on the one that comes before This is almost always the case Once you nd the pattern then it becomes clear what the assertions must be that begin and end the loop The first asserts what must be true before the loop starts and the last must be what we want to be true after the loop nishes which is normally the outcome we desire These could be written as follows We have numbered the invariants to help in the subsequent discussion double storage int indexLargest 0 int position n 1 l indexLargest is the index of the largest element in the range 0 0 for int i 1 i lt position i 2 indexLargest is the index of the largest element in the range 0 i1 if storagei gt storageindexLargest indexLargest i 3 indexLargest is the index of the largest element in the range 0 i 4 indexLargest is index of largest element in the range 0 storagelength l Identifying invariants is the first step The next step is to form these into a proof that the program fragment produces the correct outcome This is accomplished by a series of small arguments Each argument moves from one invariant to the next and use the knowledge you have of how the programming language changes the value of variables as execution progresses Typically these arguments are very simple From invariant 2 to invariant 3 Here we assume invariant 2 is true and that we know nothing more about the variable i But the if statement is checking the value of storage location i If location i is the new largest element the value of indexLargest is changed If it is not then the previous largest value remains the correct index Hence if invariant 2 is true prior to the if statement then invariant 3 must be true following the statement From invariant 3 back to invariant 2 This moves from the bottom of the loop back to the top But during this process variable i is incremented by one So if invariant 3 is true and i is incremented then invariant 2 is asserting the same thing All this may seem like a lot of work but with practice loop invariants and proofs of correctness can become second nature and seldom require as much analysis as we have presented here We return now to the development of the selection sort algorithm How to sort an array using selection sort Find the index of the largest element in an array Swap this value into the final location in the array Then do the same with the next largest element Then the next largest and so on until you reach the smallest element At that point the array will be sorted Chapter 3 Debugging Testing and Proofs of Correctness 8 Finding the largest value is a task that must be performed repeatedly It is rst performed to nd the largest element in the array and then the next largest and then the one before that and so on So again a loop seems to be called for Since we are looking for the largest value to ll a given position let us name this loop variable position The loop that is lling this variable looks as follows for position n 1 position gt 0 position find the largest element in 0 position int indeXLargest 0 IIIthen swap into place swapstorage indexLargest position what is the invariant here Question What can you say is true when execution reaches the comment at the end of the loop What is true the rst time the loop is executed What can you say about the elements with index values larger than or equal to position after each succeeding iteration The selection sort algorithm combines the outer loop with the code developed earlier wrapping this into a general method that we will name selectionSort In worksheets 6 and 7 you gain more experience working with invariants and proofs of correctness These will introduce you to yet more sorting algorithms termed gnome sort and insertion sort The latter is very practical and is often used to sort small arrays We will subsequently describe other algorithms that are even more ef cient on large collections Proofs involving Multiple Functions When a function calls another function a proof assumes the called function will work as advertised Assume that you have v0id printPrimes int n prevrously veri ed that the for int i 2 i z n i isPrime function works correctly if isPrimeim Y Use this fact to show the Systemoutprintln Number i is prime following prints the values of all the prime numbers from 2 to n A special case is the analysis of recursive functions Here you rst argue that the base case is correct and then argue that the recursive case must be correct assuming that the base case void printBinary int i performs as de ned Provide assertions that 559 0 gt 0 demonstrate the following prints the binary If 019 H I z 1 representation of a number assuming that the egg 0 argument is positive printBinaMVZx printi2 Chapter 3 Debugging Testing and Proofs of Correctness 9 Recursion and Mathematical Induction The analysis of recursive functions frequently mirrors the technique of mathematical induction Both work by establishing a base case then reducing other inputs until they reach the base case In the printBinary function shown above the base cases are the values zero and one These are handed as a special case All other values are handed by stripping off one binary digit then invoking the lnction with a smaller number Since on each iteration the number is smaller it must eventually reach the base case To illustrate the similarities recall the mathematical induction proof that the sum 1 2 n is n n 1 2 To prove this we rst verify that it is true for simple base cases such as n0 nl and n2 Next we will assume that it is true for all values smaller than n and prove it is true for n But if we have a sum from 1 to n we can group all but the last term together l2 n1 2 nln Our induction hypothesis tells us that the rst part is n l n 2 So the entire sum is n 7 l n 2 n Simple arithmetic then shows that this is n n 1 2 The argument shows that the result will hold for all positive integers Compare the structure of the preceding argument to the type of analysis you would do on a dQUble eXP dOUble av int n recursive function Suppose for example we f n n 0 return 10 tt h thtth f t39 h t 39 ht quotcm retuma wan o s ow a e unc lon s owtn a mg 0 z 2 return expand m2 computes the value a raised to the n power To ese return a eXpay n4 prove this we rst verify that it works for simple base cases such as n0 and nl Next we will assume that it works correctly for all values less than n and prove that the function works correctly for II To do this we note two simple observations If n is even then an is the same as aaquot2 And ifn is odd then an is the same as a aquot391 Since both ofthese have exponents that are smaller than n our assumption tells us that they will be correctly handled Therefore the correct result is produced In later chapters we will encounter many recursive algorithms and so it is important to become comfortable with the technique and understand the analysis of these functions Self Study Questions 1 What does it mean to say you are debugging a function 2 What are some useful hints to help you debug a function or program 3 What is an assertion 4 What is an invariant Chapter 3 Debugging Testing and Proofs of Correctness 10 5 Once you have identi ed assertions and invariants how do you create a proof of correctness 6 How is an assertion different from an assertion statement 7 What is testing 8 What is unit testing 9 What is a test harness 10 What is boundary testing 11 What are some example boundary conditions 12 What is a test suite 13 What is integration testing 14 What is regression testing and why is it performed 15 What is black box testing 16 What is white box testing 17 Give an informal description in English not code explaining how the bubble sort algorithm operates 18 Give a similar description of the selection sorting algorithm 19 In what ways does the analysis of recursive algorithms mirror the idea of mathematical induction Exercises 1 Using only the specification that is black box testing what are some test cases for the sqrt function described in the previous chapter 2 What would be some good test cases for the min function described in the previous chapter 3 Using assertions and invariants prove that the min function described in the previous Chapter 3 Debugging Testing and Proofs of Correctness chapter produces the correct result 4 V39 The GCD function in the previous chapter required the input values to be positive but did not check this condition Add assertion statements that will verify this property Prove by mathematical induction that the sum of powers of 2 is one less than the next higher power That is for any nonnegative integer n sum I 0 to n of 21 equals 2 1 1 Analysis Exercises N E 4 V39 0 gt1 9 0 Compare the selection sort algorithm with the bubble sort algorithm described in Lesson 4 How are they similar How are they different What would be good test cases to exercise the bubble sort algorithm Explain what property is being tested by our test cases What would be good test cases to exercise the selection sort algorithm From the specifications alone develop test cases for the triangle program Then determine what value the program would produce for your test cases Would your test cases have exposed the error What would be good test cases to exercise the binary search algorithm Explain what property is being tested by each test case Using the invariants you discovered earlier provide a proof of correctness for bubble sort Do this by showing arguments that link each invariant to the next Using the invariant described in the section on binary search provide a proof of correctness Do this by showing the invariant is true at the start of execution remains true after each execution of the while loop and is still true when the while loop terminates In worksheet 4 you are asked to develop invariants for a number of functions Having done so number your invariants and provide short proofs for each path that leads from one invariant to the next Finish writing the invariants for selection sort and then provide a proof of correctness by presenting arguments that link each invariant to the next Although Euclids GCD algorithm described in the previous chapter is one of the first algorithms a proof of correctness is subtle Traditionally it is divided into two steps First showing that the algorithm produces a value that is the divisor of the two input values Second showing that it is the smallest such number We will show how to do the first The argument begins with the assumption that the divisor exists even if we do not yet know its value Let us call this divisor d From basic arithmetic we Chapter 3 Debugging Testing and Proofs of Correctness 12 know that if a and b are integers and a gt b and d divides both a and b then d must also divide ab Using this hint show that if d is a divisor of n and m when the function is first called then d will be a divisor of n and m at each iteration of the while loop The algorithm halts when n is equal to m and so d is a divisor to both A sorting algorithm is said to be stable if two equal values retain their same relative ordering after sorting Can you prove that bubble sort is stable What about insertion sort The wikipedia entry for bubble sort includes a Boolean variable named swapped that is initially false inside the inner loop and set to true if any two values are swapped Explain why this can be used to improve the speed of the algorithm What is wrong with the following induction proof that for all positive numbers a and integer n it must be true that aquot391 is 1 For the base case have that for n l aquot391 is a0 which is 1 For the induction case assume it is true for l 2 3 II To verify the condition for n1 we have an171anan1gtxlt a 391a 39z 1 ll1 Explain why the following inductive argument cannot be used to demonstrate that all horses in a given corral are the same color Suppose there is one horse in a correct and that it is white Thus we have a base case since for N equal to 1 all horses in the correct are white Now add a second horse The corral still contains the first horse so we remove it We have now reduced to our base case and the horse that we removed was white so both horses must be white So for N equal to 2 we have our proof We can continue in this fashion and show no matter how many horses are in the corral that they are all white Programming Assignments N E 4 Create a test harness to test the bubble sort algorithm Feed the algorithm a variety of test cases and verify that it produces the correct result Can you write a function that verifies the correct result instead of simply printing the values and asking the programmer if they are correct Do a similar task for the selection sort algorithm Compare empirically the running time of bubble sort and insertion sort Do this by creating an array of size N containing random values then time the sorting algorithm as it sorts the array Print out the times for values of N ranging from 100 to 1000 in increments of 100 In the next chapter we will show that the running time of both bubble sort and selection sort is proportional to the square of the number of elements You can easily Chapter 3 Debugging Testing and Proofs of Correctness 13 see this empirically Program a test harness that creates an array of random values of size n Then time the execution of the bubble sort algorithm as it sorts this random array Plot the running times for n 100 200 300 up to 1000 and see what sort of graph this resembles On the Web Wikipedia includes a very complete discussion of testing under the entry Software Testing Related entries include test case Unit test integration test white box testing black box testing debugging and Software Veri cation The entry for bubble sort includes an interactive demonstration as well as detailed discussions of why it is not a good algorithm in practice Selection sort is also the topic of a wikipedia entry The wikipedia entry on assertions contains a link to an excellent article by computer science pioneer Tony Hoare on the development and use of assertions Chapter 3 Debugging Testing and Proofs of Correctness 14

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

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

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

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