### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Data Struct & Algorithms CS 245

USF

GPA 3.7

### View Full Document

## 9

## 0

## Popular in Course

## Popular in ComputerScienence

This 225 page Class Notes was uploaded by Michele Herzog on Thursday October 29, 2015. The Class Notes belongs to CS 245 at University of San Francisco taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/231242/cs-245-university-of-san-francisco in ComputerScienence at University of San Francisco.

## Reviews for Data Struct & Algorithms

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

ALA L 1 1 Data Structures and Algorithms Ordered Lists and Binary Trees Chris Brooks Department of Computer Science University of San Francisco Department of Computer Science 7 University of San Francisco 7 p 16 60 Ordered Lists e We will often want to have a list in which all the elements are ordered e As we add or remove elements order is maintained A List of names in alphabetical order a List of files from smallest to largest A List of records from earliest to most recent Department of Computer Science University of San Francisco p261 61 Ordered List ADT Operations o Insert an element in the list 6 Check if an element is in the list o Remove an element from the list o Print out the contents of the list in order How to implement this Array or linked list Department of Computer Science University of San Francisco p361 62 Implementing Ordered List Using an Ordered Array Running times Check Insert Remove Print Department of Computer Science University of San Francisco p46 63 Implementing Ordered List Using an Ordered Array Running times Check lg n Insert n Remove n Print n Department of Computer Science University of San Francisco p56 64 Implementing Ordered List Using an Unordered Array Running times Check Insert Remove Print Department of Computer Science University of San Francisco p66 65 Implementing Ordered List Using an Unordered Array Running times Check n Insert 91 Remove n Print n lg n Given a fast sorting algorithm Keeping the array ordered makes insertion require n time Department of Computer Science University of San Francisco p76 66 Implementing Ordered List Using an Ordered Linked List Running times Check Insert Remove Print Department of Computer Science University of San Francisco p86 67 Implementing Ordered List Using an Ordered Linked List Running times Check n Insert n Remove n Print n With an unordered list insertion requires 91 time Department of Computer Science University of San Francisco p96 68 The Best of Both Worlds e Linked Lists Insert fast Find slow 6 Arrays Find fast Insert slow 6 The only way to examine nth element in a linked list is to traverse n1 other elements an H lgt12 lgt15 22H252 l o If we could leap to the middle of the list Department of Computer Science University of San Francisco p1061 69 The Best of Both Worlds an H H1 H15 H2 IgtIzs IgtI2s N Department of Computer Science University of San Francisco p 1 161 610 The Best of Both Worlds 44HmlwnwawnHwHMN Move the initial pointer to the middle of the list Jmel nNmahnHw hMN We ve cut our search time in half Have we changed the 90 running time Department of Computer Science University of San Francisco p1261 611 The Best of Both Worlds 44HmlwnwawnwaeMN Move the initial pointer to the middle of the list Jmel nNmahnHw hMN We ve cut our search time in half Have we changed the 90 running time Repeat the process Department of Computer Science University of San Francisco p1361 612 The Best of Both Worlds 4HIMnHHnHwHMN JmelwuNmenHmwMN JMIHAanNmanmlwwanN 4 ll 4 613 The Best of Both Worlds Grab the first element of the list JI4 i gti12 Nilif slli I22 ilt2 gti28 l 4 l I 4 Give it a good shake Department of Computer Science University of San Francisco p1561 614 Binary Trees Binary Trees are Recursive Data Structures 6 Base Case Empty Tree o Recursive Case Node consisting of A Left Child Tree A Right Child Tree A Data Department of Computer Science University of San Francisco p1661 615 Binary Tree Examples The following are all Binary Trees Though not Binary Search Trees Department of Computer Science University of San Francisco p1761 Parent Child Leafnode Root node Edge between nodes Path Ancestor Descendant Depth of a node n A Length of path from root to n Height of a tree A Depth of deepest node 1 616 Tree Terminology Department of Computer Science University of San Francisco p1861 617 Full Binary Tree 63 Each node has 0 or 2 children e Full Binary Trees M I Not Full Binary Trees Aamp Department of Computer Science University of San Francisco p1961 618 Complete Binary Tree e Can be build by starting at the root and filling the tree by levels from left to right 6 Complete Binary Trees Q g a Not Complete Binary Trees OR E Department of Computer Science University of San Francisco p2061 619 Binary Search Trees Binary Trees For each node n value stored at node n gt value stored in left subtree For each node n value stored at node n lt value stored in right subtree Department of Computer Science University of San Francisco p2161 620 Example Binary Search Trees Department of Computer Science University of San Francisco p2261 621 Implementing BS Ts Department of Computer Science University of San Francisco p2361 622 Finding an Element in a BST o Binary Search Trees are recursive data structures so most operations on them will be recursive as well o Recall how to write a recursive algorithm Department of Computer Science University of San Francisco p2461 623 Writing a Recursive Algorithm Determine a small version of the problem which can be solved immediately This is the base case 6 Determine how to make the problem smaller 6 Once the problem has been made smaller we can assume that the function that we are writing will work correctly on the smaller problem Recursive Leap of Faith a Determine how to use the solution to the smaller problem to solve the larger problem Department of Computer Science University of San Francisco p2561 624 Finding an Element in a BST e First the Base Case when is it easy to determine if an element is stored in a Binary Search Tree Department of Computer Science University of San Francisco p2661 625 Finding an Element in a BST e First the Base Case when is it easy to determine if an element is stored in a Binary Search Tree a If the tree is empty then the element can t be there a If the element is stored at the root then the element is there Department of Computer Science University of San Francisco p2761 626 Finding an Element in a BST o Next the Recursive Case how do we make the problem smaller Department of Computer Science University of San Francisco p2861 627 Finding an Element in a BST o Next the Recursive Case how do we make the problem smaller A Both the left and right subtrees are smaller versions of the problem Which one do we use Department of Computer Science University of San Francisco p2961 628 Finding an Element in a BST o Next the Recursive Case how do we make the problem smaller A Both the left and right subtrees are smaller versions of the problem Which one do we use A If the element we are trying to find is lt the element stored at the root use the left subtree Otherwise use the right subtree Department of Computer Science University of San Francisco p3061 629 Finding an Element in a BST o Next the Recursive Case how do we make the problem smaller A Both the left and right subtrees are smaller versions of the problem Which one do we use A If the element we are trying to find is lt the element stored at the root use the left subtree Otherwise use the right subtree o How do we use the solution to the subproblem to solve the original problem Department of Computer Science University of San Francisco p3161 630 Finding an Element in a BST o Next the Recursive Case how do we make the problem smaller A Both the left and right subtrees are smaller versions of the problem Which one do we use A If the element we are trying to find is lt the element stored at the root use the left subtree Otherwise use the right subtree o How do we use the solution to the subproblem to solve the original problem A The solution to the subproblem is the solution to the original problem this is not always the case in recursive algorithms Department of Computer Science University of San Francisco p3261 631 Finding an Element in a BST To find an element 6 in a Binary Search Tree T o HT is empty then 6 is not in T o If the root ofT contains 6 then 6 is in T o If e lt the element stored in the root ofT a Look for e in the left subtree of T OthenNise A Look for e in the right subtree ofT Department of Computer Science University of San Francisco p3361 boolean findNode tree if tree return if return if return else return elem elem 632 Finding an Element in a BST Comparable elem null false compareTotreeelement 0 true compareTotree lt O findtreeleft elem findtreeright elem Department of Computer Science University of San Francisco p346 633 Printing out a BST To print out all element in a BST o Print all elements in the left subtree in order 65 Print out the element at the root of the tree 6 Print all elements in the right subtree in order Department of Computer Science University of San Francisco p3561 634 Printing out a BST To print out all element in a BST o Print all elements in the left subtree in order 65 Print out the element at the root of the tree 6 Print all elements in the right subtree in order A Each subproblem is a smaller version of the original problem we can assume that a recursive call will work Department of Computer Science University of San Francisco p3661 635 Printing out a BST e What is the base case for printing out a Binary Search Tree what is an easy tree to print out Department of Computer Science University of San Francisco p3761 636 Printing out a BST o What is the base case for printing out a Binary Search Tree what is an easy tree to print out 6 An empty tree is extremely easy to print out do nothing 3 Code for printing a BST Department of Computer Science University of San Francisco p3861 637 Printing out a BST void printNode tree if tree 1 null printtreeleft Systemoutprinlntreeelement printtreeright Department of Computer Science University of San Francisco 33961 638 Printing out a BST Examples Department of Computer Science University of San Francisco p4061 639 Tree Traversals o PREORDER Traversal A Do operation on root of the tree A Traverse left subtree A Traverse right subtree o INORDER Traversal A Traverse left subtree A Do operation on root of the tree A Traverse right subtree POSTORDER Traversal A Traverse left subtree A Traverse right subtree A Do operation on root of the tree Department of Computer Science University of San Francisco p4161 640 PREORDER Examples Department of Computer Science University of San Francisco p4261 641 POSTORDER Examples Department of Computer Science University of San Francisco p4361 642 INORDER Examples Department of Computer Science University of San Francisco p4461 643 BST Minimal Element To find the minimal element in a BST 6 Base Case When is it easy to find the smallest element in a BST 6 Recursive Case How can we make the problem smaller How can we use the solution to the smaller problem to solve the original problem Department of Computer Science University of San Francisco p4561 644 BST Minimal Element To find the minimal element in 3 BST Base Case 6 When is it easy to find the smallest element in a BST Department of Computer Science University of San Francisco p4661 645 BST Minimal Element To find the minimal element in 3 BST Base Case 6 When is it easy to find the smallest element in a BST 5 When the left subtree is empty then the element stored at the root is the smallest element in the tree Department of Computer Science University of San Francisco p4761 646 BST Minimal Element To find the minimal element in 3 BST Recursive Case 6 How can we make the problem smaller Department of Computer Science University of San Francisco p4861 647 BST Minimal Element To find the minimal element in a BST Recursive Case 6 How can we make the problem smaller 5 Both the left and right subtrees are smaller versions of the same problem 6 How can we use the solution to a smaller problem to solve the original problem Department of Computer Science University of San Francisco p4961 648 BST Minimal Element To find the minimal element in a BST Recursive Case 6 How can we make the problem smaller 5 Both the left and right subtrees are smaller versions of the same problem 6 How can we use the solution to a smaller problem to solve the original problem A The smallest element in the left subtree is the smallest element in the tree Department of Computer Science University of San Francisco p5061 649 BST Minimal Element Comparable minimumNode tree if tree null return null if treeleft null return treeelement else return minimumtreeleft Department of Computer Science University of San Francisco p516 650 BST Minimal Element Iterative Version Comparable minimumNode tree if tree null return null while treeleft 1 null tree treeleft return treeelement Department of Computer Science University of San Francisco p526 651 Inserting a into BST T 5 What is the base case an easy tree to insert an element into Department of Computer Science University of San Francisco p5361 652 Inserting a into BST T o What is the base case an easy tree to insert an element into A An empty tree A Create a new tree containing the element 6 Department of Computer Science University of San Francisco p5461 653 Inserting a into BST T o Recursive Case How do we make the problem smaller Department of Computer Science University of San Francisco p5561 654 Inserting a into BST T o Recursive Case How do we make the problem smaller A The left and right subtrees are smaller versions of the same problem A How do we use these smaller versions of the problem Department of Computer Science University of San Francisco p5661 655 Inserting a into BST T o Recursive Case How do we make the problem smaller a The left and right subtrees are smaller versions of the same problem A Insert the element into the left subtree if e lt value stored at the root and insert the element into the right subtree if e gt value stored at the root Department of Computer Science University of San Francisco p5761 656 Inserting a into BST T 5 Base case T is empty A Create a new tree containing the element 6 c3 Recursive Case A If e is less than the element at the root of T insert 6 into left subtree A If e is greater than the element at the root of T insert 6 into the right subtree Department of Computer Science University of San Francisco p5861 657 Tree Manipulation in Java Tree manipulation functions return trees Insert method takes as input the old tree and the element to insert and returns the new tree with the element inserted A Old value preinsertion of tree will be destroyed To insert an element e into a tree T a T insertT e Department of Computer Science University of San Francisco p5961 658 Inserting 6 into BST T Node insertNode tree Comparable elem if tree null return new Nodeelem if elemcompareTotreeelement lt 0 treesetLeftinserttreeleft elem return tree else treesetRightinserttreeright elem return tree Department of Computer Science University of San Francisco p6061 659 Deleting From a BST e Removing a leaf a Remove element immediately Removing a node with one child a Just like removing from a linked list A Make parent point to child 6 Removing a node with two children A Replace node with largest element in left subtree or the smallest element in the right subtree Department of Computer Science University of San Francisco p6161 ALA L 1 1 Data Structures and Algorithms Spanning Trees Chris Brooks Department of Computer Science University of San Francisco Department of Computer Scwence 7 Unwersny of San Francwsco r p12 210 Spanning Trees o Given a connected undirected graph G a A subgraph of G contains a subset of the vertices and edges in G a A Spanning Tree T of G is subgraph of G contains all vertices in G 7 connected acyclic Department of Computer Science University of San Francisco p22 211 Spanning Tree Examples 4 5 6 Department of Computer Science University of San Francisco p32 212 Spanning Tree Examples 939 Spanning Tree 0 l Department of Computer Science University of San Francisco p42 213 Spanning Tree Examples 4 5 6 Department of Computer Science University of San Francisco p52 214 Spanning Tree Examples 3 Spanning Tree 0 1 2 3 5 6 Department of Computer Science University of San Francisco p62 4 215 Minimal Cost Spanning Tree e Minimal Cost Spanning Tree 13 Given a weighted undirected graph G a Spanning tree of G which minimizes the sum of all weights on edges of spanning tree Department of Computer Science University of San Francisco p72 216 MST Example xlx Department of Computer Science University of San Francisco p8239 217 MST Example Department of Computer Science University of San Francisco p9239 218 Minimal Cost Spanning Trees Can there be more than one minimal cost spanning tree for a particular graph Department of Computer Science University of San Francisco p102 219 Minimal Cost Spanning Trees e Can there be more than one minimal cost spanning tree for a particular graph 6 YES A What happens when all edges have unit cost Department of Computer Science University of San Francisco p112 2110 Minimal Cost Spanning Trees e Can there be more than one minimal cost spanning tree for a particular graph 6 YES A What happens when all edges have unit cost a All spanning trees are MSTs Department of Computer Science University of San Francisco p122 2111 Calculating MST o Two algorithms to calculate MST a Kruskal s Algorithm Build a forest of spanning trees Combine into one tree A Prims Algorithm Grow a single tree out from a start vertex Department of Computer Science University of San Francisco p132 2112 Kruskal s Algorithm c Start with an empty graph no edges e Sort the edges by cost 6 For each edge e in increasing order of cost A Add a to G if it would not cause a cycle Department of Computer Science University of San Francisco p142 2113 Kruskal s Algorithm Examples xlx Department of Computer Science University of San Francisco p15239 2114 Kruskal s Algorithm Proof by contradiction Assume that no optimal MST T contains the minimum cost edge 6 Add 6 to T which causes a cycle Remove an edge other than 6 to break the cycle cost T g T a contradiction Department of Computer Science University of San Francisco p162 2115 Kruskal s Algorithm e Coding Kruskal s Algorithm a Place all edges into a list A Sort list of edges by cost a For each edge in the list Select the edge if it does not form a cycle with previously selected edges How can we do this Department of Computer Science University of San Francisco p172 2116 Kruskal s Algorithm c Determining of adding an edge will cause a cycle A Start with a forest of V trees each containing one node Each added edge merges two trees into one tree An edge causes a cycle if both vertices are in the same tree A examples Department of Computer Science University of San Francisco p182 2117 Kruskal s Algorithm e We need to A Put each vertex in its own tree a Given any two vertices v1 and v2 determine if they are in the same tree 0 Given any two vertices v1 and v2 merge the tree containing v1 and the tree containing v2 6 sound familiar Department of Computer Science University of San Francisco p192 6 2118 Kruskal s Algorithm Disjoint sets Create a list of all edges Sort list of edges For each edge e v1 v2 in the list A ifFINDv1 FINDv2 Add 6 to spanning tree UNIONU1U2 Department of Computer Science University of San Francisco p202 2119 Prim s Algorithm o Grow that spanning tree out from an initial vertex 9 Divide the graph into two sets of vertices A vertices in the spanning tree A vertices not in the spanning tree 9 Initially Start vertex is in the spanning tree all other vertices are not in the tree A Pick the initial vertex arbitrarily Department of Computer Science University of San Francisco p212 2120 Prim s Algorithm e While there are vertices not in the spanning tree a Add the cheapest vertex to the spanning tree Department of Computer Science University of San Francisco p222 2121 Prims s Algorithm Examples xlx Department of Computer Science University of San Francisco p23239 2122 Prim s Algorithm e Use a table much like Dijkstra table a Path has the same meaning 6 Cost is for vertex vk A cost to add vk to the tree A instead of length of path to 1 Department of Computer Science University of San Francisco p242 2123 Prim s Algorithm e Code for Prim s algorithm is very similar to the code for Dijkstra s algorithm 6 Make one small Change to Dijkstra s algorithm to get Prim s algorithm Department of Computer Science University of San Francisco p252 2124 Dijkstra Code void DijkstraEdge G int 3 tableEntry T int i V Edge e fori0 iltGlength i T idistance Integer MAXVALUE ipath l iknown false Tsdistance O for i0 i lt G length i V minUnknoanerteXT Tvknown true for e GV e 1 null e enext if Te neighbordistance gt Tvdistance e cost Teneighbordistance Tvdistance e cost Teneighborpath v Department of Computer Science University of San Francisco p26239 ALA L Data Structures and Algorithms Recursive Sorting Chris Brooks Department of Computer Science University of San Francisco Department of Computer Science 7 University of San Francisco 7 p 149 120 Recursive Sorting Algorithms e Basic sorting algorithms all run in 012 time e We can do better by sorting sublists and combining results Department of Computer Science University of San Francisco p24t 121 Merge Sort Recursive Sorting e Base Case A A list of length 1 or length 0 is already sorted Recursive Case a Split the list in half A Recursiver sort two halves A Merge sorted halves together Department of Computer Science University of San Francisco p34f 122 Example 51826437 A5128 6437 51 28 64 37 05 1 2 8 6 4 3 7 15 28 46 37 51258 3467 6 12345678 Department of Computer Science University of San Francisco p44f 123 Merging Merge lists into a new list T Maintain three pointers indices z j and n A z is index of left hand list a j is index of right hand list A n is index of destination ist T fAz lt Aij A Tin Aiz increment n and 2 else a TM AU increment n andj Department of Computer Science University of San Francisco p54f 124 for Merge Sort TO cl for some constant cl T1 02 for some constant 02 Tn 7203 2Tn2 for some constant 03 Tn 7163 2Tn2 Department of Computer Science University of San Francisco p64 125 for Merge Sort TO cl for some constant cl T1 02 for some constant 02 Tn 7203 2Tn2 for some constant 03 Tn 7163 2Tn2 7163 2n203 2Tn4 27163 4Tn4 Department of Computer Science University of San Francisco p74 126 for Merge Sort TO cl for some constant cl T1 02 for some constant 02 Tn 7203 2Tn2 for some constant 03 Tn 7163 2Tn2 7163 2n203 2Tn4 27163 4Tn4 27163 401463 2Tn8 37163 8Tn8 Department of Computer Science University of San Francisco p84 127 for Merge Sort TO cl for some constant cl T1 02 for some constant 02 Tn 7203 2Tn2 for some constant 03 Tn 7163 2Tn2 7163 2n203 2Tn4 27163 4Tn4 27163 401463 2Tn8 37163 8Tn8 37lC3 801863 2Tn16 47163 16Tn16 Department of Computer Science University of San Francisco p94 128 for Merge Sort TO cl for some constant cl T1 02 for some constant 02 Tn 7203 2Tn2 for some constant 03 Tn 7163 2Tn2 7163 2n203 2Tn4 27163 4Tn4 27163 401463 2Tn8 37163 8Tn8 37lC3 801863 2Tn16 47163 16Tn16 57163 32Tn32 Department of Computer Science University of San Francisco p104 129 for Merge Sort TO cl for some constant cl T1 02 for some constant 02 Tn 7203 2Tn2 for some constant 03 Tn 7163 2Tn2 7163 2n203 2Tn4 27163 4Tn4 27163 401463 2Tn8 37163 8Tn8 37lC3 801863 2Tn16 47163 16Tn16 57163 32Tn32 Ing 2kTn2k Department of Computer Science University of San Francisco p 1 145 1210 for Merge Sort Tn Ing 2kTn2k Pick a value for k such that n2k 1 nZk 1 n 2k lgn k Tn 1g nn63 21g Tn21g 6ng lg n anlgnnT1 anlgn 0272 E 0n1gn Department of Computer Science University of San Francisco p124 1211 for Merge Sort Department of Computer Science University of San Francisco p134 1212 for Merge Sort cn TI12 TI12 Department of Computer Science University of San Francisco p144 1213 for Merge Sort cn Tn4 Tn4 Tn4 Tn4 Department of Computer Science University of San Francisco p154 1214 for Merge Sort Cn cn Cn2 7n2 cn C39W Cn4 cn4 cn4 cn Department of Computer Science University of San Francisco p164 1215 for Merge Sort 1g 1 leve Cn Cn Cn Cn Cn p174 University of San Francisco Department of Computer Science 1216 for Merge Sort Crl Cn 3 112 c n2 cn 1g leve cn4 cn4 cn4 cn4 cn Cn Total time cn lg n n lg II Department of Computer Science University of San Francisco p1845 1217 Divide amp Conquer Merge Sort e Divide the list two parts A No work required just calculate midpoint o Recursiver sort two parts 6 Combine sorted lists into one list a Some work required need to merge ists Department of Computer Science University of San Francisco p194f 1218 Divide amp Conquer Quick Sort 2 Divide the list two parts a Some work required Small elements in left sublist large elements in right sublist Recursiver sort two parts 6 Combine sorted ists into one list A No work required Department of Computer Science University of San Francisco p204f Pick a pivot element Reorder the list A All elements lt pivot A Pivot element a All elements gt pivot Recursiver sort elements lt pivot Recursiver sort elements gt pivot 1219 Quick Sort Department of Computer Science University of San Francisco p214f 1220 Example o Example3728146 Suppose 3 is our pivot A Splitinto3217846 Sort left half suppose 2 is the pivot e 1 2 3 7 Sort right half suppose 1 is the pivot 4 6 7 8 Recurse and merge Department of Computer Science University of San Francisco p224f 1221 Quick Sort Partitioning Basic Idea 6 Swap pivot element out of the way we ll swap it back later e Maintain two pointers z andj A 2 points to the beginning of the list a j points to the end of the list 6 Move 2 andj in to the middle of the list ensuring that all elements to the left ofz are lt the pivot and all elememnts to the right ofj are greater than the pivot e Swap pivot element back to middle of list Department of Computer Science University of San Francisco p234f 1222 Quick Sort Partitioning Pseudocode G J G Pick a pivot index Swap Apivotindex and Ahigh Setz lt low j lt high 1 wmmiltj A while Az lt Apivot incrementz39 A wmmz xAmNdeemememi a swap Az and AM Ainmenmntidemenmntj swap Az and Apivot Department of Computer Science University of San Francisco p244f 1223 90 for Quick Sort o Coming up with a recurrence relation for quicksort is harder than mergesort o How the problem is divided depends upon the data A Break list into size 0 size n 1 size 1 size n 2 size 71 1 2 i size n 1 21 size n 2 size 1 size n 1 size 0 Department of Computer Science University of San Francisco p254f 1224 for Quick Sort Worst case performance occurs when break list into size n 1 and size 0 TO cl for some constant cl T1 02 for some constant 02 Tn 7203 Tn 1 TO for some constant 03 Tn 7163 Tn 1 TO Tn 1n6362 Department of Computer Science University of San Francisco p264 1225 for Quick Sort Worst case Tn Tn 1 7103 02 T01 Tn 1n6362 Department of Computer Science University of San Francisco p274 1226 for Quick Sort Worst case Tn Tn 1 7103 02 n Tn 1n6362 Tn 2n 1Cg 62 7ng 62 n 2nn 1Cg202 Department of Computer Science University of San Francisco p284 1227 for Quick Sort Worst case Tn Tn 1 7103 02 n Tn 1 7ng 62 Tn 2 n 103 C2 7103 02 Tn 2 n n 103 202 Tn 3 n 263 C2 n n 163 262 Tn 3nn 1n 263362 Department of Computer Science University of San Francisco 32945 1228 for Quick Sort Worst case Tn Tn 1 7103 02 E 3 n 1n6362 Tn 2n 1C3C2TZC3C2 l I Tn 2nn 103202 Tn 3n 203Cgnn 103202 Tn 3nn 1n 263362 Tn 4nn 1n 2n 303402 Department of Computer Science University of San Francisco p304 1229 for Quick Sort Worst case Tn Tn 1 7103 02 Tn Tn 1n6362 Tn 2n 1C3C2TZC3C2 Tn 2nn 103202 Tn 3n 2C3C2 nn 163262 Tn 3nn 1n 263362 Tn 4nn 1n 2n 303402 ITn k Zf01n i03 1602 Department of Computer Science University of San Fran cisco p314 1230 for Quick Sort Worst case M Tm k EL 0101 neg m n k n iC3 keg n n 21723 i03 keg 0 Zigolm neg keg 0 20123903 1902 Cl ann 12 keg n2 T T T T Department of Computer Science University of San Francisc o p324 1231 for Quick Sort Department of Computer Science University of San Francisco 33345 cn TI1l TO 1232 for Quick Sort Department of Computer Science University of San Francisco p344 1233 for Quick Sort Department of Computer Science University of San Francisco p354 1234 for Quick Sort Department of Computer Science University of San Francisco p364 1235 for Quick Sort cm Cn l c2 Cn lc2 n leve Cn 2 c2 Cn 2c2 cn 52 Cn 3c2 cn kc2 Department of Computer Science University of San Francisco p3745 1236 for Quick Sort cn cn Cn lc2 leve n 2 c2 Cn 2C2 n Cn 3C2 cn kc2 7R dthne cnnl2 nc2 Department of Computer Science University of San Francisco 33845 1237 for Quick Sort Best case performance occurs when break list into size n 12j and size n 12i TO cl for some constant cl T1 02 for some constant 02 Tn 7203 2Tn2 for some constant 03 This is the same as Merge Sort n lg 71 Department of Computer Science University of San Francisco 33945 1238 Quick Sort If Quicksort is 012 on some lists why is it called quick o Most lists give running time of nlg n A Average case running time is n lg n o Constants are very small a Constants don t matter when complexity is different a Constants do matter when complexity is the same What lists will cause Quick Sort to have 9012 performance Department of Computer Science University of San Francisco p404f 1239 Quick Sort Worst Case e Quick Sort has worstcase performance when A The list is sorted or almost sorted A The list is inverse sorted or almost inverse sorted Many lists we want to sort are almost sorted 9 How can we fix Quick Sort Department of Computer Science University of San Francisco p414f 1240 Better Partitions e Pick the middle element as the pivot A Sorted and reverse sorted lists give good performance e Pick a random element as the pivot a No single list always gives bad performance 6 Pick the median of 3 elements A First Middle Last a 3 Random Elements Department of Computer Science University of San Francisco p424f 1241 Improving Quick Sort o Insertion Sort runs faster than Quick Sort on small lists A Why 6 We can combine Quick Sort amp Insertion Sort A When lists get small run Insertion Sort instead ofa recursive call to Quick Sort a When lists get small stop After call to Quick Sort list will be almost sorted finish the job with a single call to Insertion Sort Department of Computer Science University of San Francisco p434f 1242 Heap Sort e Build a heap out of the data 65 Repeat 13 Remove the largest element from the list place it at end of heap Until all elements have been removed from the heap The list is now sorted Example 31 7 2 5 4 Department of Computer Science University of San Francisco p444f ALA L 1 1 Data Structures and Algorithms Searching and Hashing Chris Brooks Department of Computer Science University of San Francisco Department of Computer Science 7 University of San Francisco 7 p 14 150 Searching and Hashing e We know how to arrange things sorting What about efficient ways of nding things 6 We ve seen a couple of ways to do this already A List A Binary Search Tree Department of Computer Science University of San Francisco p24i 151 Searching amp Selecting o Let s assume that we want to store records in some sort of database o Records have keys and values data 6 Our database should have the following operations A Add a key value pair to the database A Remove a key and associated value from the database A Find the value associated with a key Department of Computer Science University of San Francisco p34i 152 Sorted List Implementation If database is implemented as a sorted list 6 Add Remove Find Department of Computer Science University of San Francisco p44i 153 Sorted List Implementation If database is implemented as a sorted list 6 Add 0n Remove C71 Find 01g n Department of Computer Science University of San Francisco p54i 154 BST Implementation If database is implemented as a Binary Search Tree 6 Add Remove Find Department of Computer Science University of San Francisco p64i 155 BST Implementation If database is implemented as a Binary Search Tree 6 Add 01g n best 0n worst o Remove 01gn best 0n worst 6 Find 01g n best 0n worst Department of Computer Science University of San Francisco p74i 156 Unsorted List Maintain an unsorted noncontiguous array of elements 15 4 3 l3 8 6 o How long does a Find take 6 How long does a Remove take cc How long does an Add take Does this sound like a good idea Department of Computer Science University of San Francisco p84i 157 Hash Function G What if we had a magic function a Takes a key as input A Returns the index in the array where the key can be found if the key is in the array To add an element a Put the key through the magic function to get a loca on A Store element in that location a To find an element A Put the key through the magic function to get a loca on a See if the key is stored in that location Department of Computer Science University of San Francisco p94i 158 Hash Function The magic function is called a Hash function If hash key i we say that the key hashes to the value 1 We d like to ensure that different keys will always hash to different values Why is this not possible Department of Computer Science University of San Francisco p104i 159 Hash Function The magic function is called a Hash function If hash key i we say that the key hashes to the value 1 We d like to ensure that different keys will always hash to different values Why is this not possible A Too many possible keys A If keys are strings of up to 15 letters there are 1021 different keys Department of Computer Science University of San Francisco p1 141 1510 Integer Hash Function When two keys hash to the same value a collision occurs We cannot avoid collisions but we can minimize them by picking a hash function that distributes keys evenly through the array Example Keys are integers A Keys are in range 1m A Array indices are in range 1 n a n ltlt m Department of Computer Science University of San Francisco p124i 151 1 Integer Hash Function When two keys hash to the same value a collision occurs We cannot avoid collisions but we can minimize them by picking a hash function that distributes keys evenly through the array Example Keys are integers A Keys are in range 1m A Array indices are in range 1 n a n ltlt m hashk kmodn Department of Computer Science University of San Francisco p134i 1512 Integer Hash Function 63 What if table size 10 all keys end in 0 Department of Computer Science University of San Francisco p144i 1513 Integer Hash Function e What if table size 10 all keys end in 0 e What if table size is even all keys are even Department of Computer Science University of San Francisco p154i 1514 Integer Hash Function What if table size 10 all keys end in 0 What if table size is even all keys are even In general what if the table size and many of the keys share factors Department of Computer Science University of San Francisco p164i 1515 Integer Hash Function What if table size 10 all keys end in 0 What if table size is even all keys are even In general what if the table size and many of the keys share factors What can we do Department of Computer Science University of San Francisco p174i 1516 Integer Hash Function What if table size 10 all keys end in 0 What if table size is even all keys are even In general what if the table size and many of the keys share factors What can we do a Prevent keys and table size from sharing factors 0 Typically we don t get to pick the keys they re given externally a We can control the table size Department of Computer Science University of San Francisco p184i 1517 Integer Hash Function What if table size 10 all keys end in 0 What if table size is even all keys are even In general what if the table size and many of the keys share factors What can we do A Prevent keys and table size from sharing factors a No control over the keys A Make the table size prime Department of Computer Science University of San Francisco p194i 1518 String Hash Function Hash tables are usually used to store string values If we can convert a string into an integer we can use the integer hash function How can we convert a string into an integer Department of Computer Science University of San Francisco p204i 1519 String Hash Function e Hash tables are usually used to store string values If we can convert a string into an integer we can use the integer hash function o How can we convert a string into an integer a Add up ASCII values of the characters in the string int hashString key int tableSize int hashvalue O for int i0 iltkeylength i hashvalue 2 int keycharAti 0 return hashvalue 6 tableSize Department of Computer Science University of San Francisco p214i 1520 String Hash Function Hash tables are usually used to store string values If we can convert a string into an integer we can use the integer hash function How can we convert a string into an integer n Concatenate ASCII digits together keysize l Z k yk gtk 256k y8ize k1 160 Department of Computer Science University of San Francisco p224i 1521 String Hash Function o Concatenating digits does not work since numbers get big too fast Solutions A Overlap digits a little use base of 32 instead of 256 A Ignore early characters shift them off the left side of the string static long hashString key int tablesize long h 0 int i for i0 iltkeylength i h h ltlt 4 int keycharAti return h tablesize Department of Computer Science University of San Francisco p234i 1522 EIfHash For each new character the hash value is shifted to the left and the new character is added to the accumulated value If the string is long the early characters will fall off the end of the hash value when it is shifted 0 Early characters will not affect the hash value of large strings Instead of falling off the end of the string the most significant bits can be shifted to the middle of the string and XOR ed Every character will influence the value of the hash function Department of Computer Science University of San Francisco p244i 1523 EIfHash static long ELFhashString key int tablesize long h 0 long 9 int i r i0 iltkeylength i h h ltlt 4 int keycharAti g h amp OXFOOOOOOOL if g 1 O h g gtgtgt 24 h 2 M Q return h M Department of Computer Science University of San Francisco p254Z 1524 Collisions c When two keys hash to the same value a collision occurs 65 A collision strategy tells us what to do when a collision occurs 6 Two basic collision strategies A Open Hashing Closed Addressing Separate Chaining a Closed Hashing Open Addressing Department of Computer Science University of San Francisco p264i 1525 Open Hashing Array does not store elements but linkedlists of elements To Add an element to the hash table A Hash the key to get an indeXz39 A Store the keyvalue pair in the linked list at indexi To find an element in the hash table A Hash the key to get an indeXz39 a Search the linked list at index 2 for the key This should remind you of a sorting algorithm Department of Computer Science University of San Francisco p274i 1526 Open Hashing Under the following conditions Keys are evenly distributed through the hash table 6 Size of the hash table of keys inserted What is the running time for the following operations 6 Add 9 Remove 6 Find Department of Computer Science University of San Francisco p284i 1527 Open Hashing Under the following conditions Keys are evenly distributed through the hash table 6 Size of the hash table of keys inserted What is the running time for the following operations G Add 91 9 Remove 91 65 Find 91 Department of Computer Science University of San Francisco p294i 1528 Closed Hashing e Values are stored in the array itself no linked lists 65 The number of elements that can be stored in the hash table is limited to the table size hence Closed hashing Department of Computer Science University of San Francisco p304i 1529 Closed Hashing e To add element X to a closed hash table A Find the smallest i such that Arrayhashx fi is empty wrap around if necessary a Add X to Arrayhashx fi A If fi i linear probing Department of Computer Science University of San Francisco p314i 1530 Closed Hashing 6 Problems with linear probing a Primary Clustering Clumps large sequences of consecutively filled array elements tend to form Positive feedback system the larger the clumps the more likely an element will end up in a clump Department of Computer Science University of San Francisco p324i 1531 Closed Hashing 639 Quadradic probing a Find the smallest i such that Arrayhashx fi is empty A Add X to Arrayhashx fi A fiz 2 Department of Computer Science University of San Francisco p334i 1532 Closed Hashing 639 Quadradic probing a Find the smallest i such that Arrayhashx fi is empty A Add X to Arrayhashx fi A fiz 2 3 Problems a Can t reach all elements in the list Department of Computer Science University of San Francisco p344i 1533 Closed Hashing 639 Quadradic probing a Find the smallest i such that Arrayhashx fi is empty A Add X to Arrayhashx fi A fiz 2 3 Problems a Can t reach all elements in the list A if table is less than 12 full and table size is an integer guaranteed to be able to add an element Department of Computer Science University of San Francisco p354i 1534 Closed Hashing a PseudoRandom A Create a Permutation Array P A fi Pi Department of Computer Science University of San Francisco p364i 1535 Closed Hashing e Multiple keys hash to the same element A Secondary clustering 6 Double Hashing a Use a secondary hash function to determine how far ahead to look A fi i hash2key Department of Computer Science University of San Francisco p374i 1536 Deletion e Deletion from an open hash table is easy a Find the element 5 Delete it e Deletion from a closed hash table is harder A Why Department of Computer Science University of San Francisco p384i 1537 Deletion Deletion a closed hash table can cause problems a Three different kinds of entries A Empty cells B Cells that contain data A Cells that have been deleted tombstones Department of Computer Science University of San Francisco p394i 1538 Deletion e To insert an element A Find the smallest i such that hashx fi is either empty or deleted 6 To find an element A Try all values ofi starting with 0 until either Tablehashx fi x Tablehashx fi is empty not deleted Department of Computer Science University of San Francisco p404i 1539 Rehashing o What can we do when our closed hash table gets full 65 Or if the load of elements table size gets larger than 05 A Create a new larger table New hash table will have a different hash function since the table size is different A Add each element in the old table to the new table Department of Computer Science University of San Francisco p414i Data Structures and Algorithms Week 08 Lecture 1 1 1 BTrees De nition 0 De nition Suppose m is a positive integer Then a B tree of order m is a tree with the following properties H pow 7 Cf Each nonempty node other than the root has between and m Children If the tree is nonernpty7 the root has between 2 and m children If a node has 0 Children then it stores 0 7 1 keys in increasing order If the keys stored in a node are k1ltk2lt ltk57 then a b 0 all keys stored in leftmost or 0th subtree are less than k1 all keys stored in the 2th subtree7 1 S 239 lt 5 lie between kl and Isl1 and all keys stored in the last subtree are greater than than k5 All the leaves have the same depth Data Structures and Algorithms Week 08 Lecture 1 insert search current node for key if found print message return null else if current node is a leaf insert key into current node else recursively insert into appropriate child of current node possibly returning a new key and a new child if return is not null insert new key into current node set reference to new child if current node has too many children split the current node creating a new key and a new child return the key and child else return null ALA L 1 1 Data Structures and Algorithms Huffman Trees Chris Brooks Department of Computer Science University of San Francisco Department of Computer Science 7 University of San Francisco 7 p 12 100 Text Files All files are represented as binary digits including text files Each character is represented by an integer code a ASCII American Standard Code for Information Interchange Text file is a sequence of binary digits which represent the codes for each character Department of Computer Science University of San Francisco p221 101 ASCII o Each character can be represented as an 8bit number A ASCII for a 97 01100001 A ASCII for b 98 01100010 o Text file is a sequence of 1 s and 0 s which represent ASCII codes for characters in the file A File aba is 97 97 98 A 011000010110001001100001 Department of Computer Science University of San Francisco p321 102 ASCII o Each character in ASCII is represented as 8 bits a We need 7 bits to represent all possible character combinations 0 The 8th bit is used for error correction a Breaking up file into individual characters is easy A Finding the kth character in a file is easy Department of Computer Science University of San Francisco p421 103 ASCII o ASCII is not terribly efficient a All characters require 8 bits a Frequently used characters require the same number of bits as infrequently used characters A We could be more efficient if frequently used characters required fewer than 8 bits and less frequently used characters required more bits Department of Computer Science University of San Francisco p521 104 Representing Codes as Trees e Want to encode 4 only characters a b c d instead of 256 characters a How many bits are required for each code if each code has the same length Department of Computer Science University of San Francisco p621 105 Representing Codes as Trees e Want to encode 4 only characters a b c d instead of 256 characters a How many bits are required for each code if each code has the same length a 2 bits are required since there are 4 possible options to distinguish Department of Computer Science University of San Francisco p721 106 Representing Codes as Trees c Want to encode 4 only characters a b c d a Pick the following codes A a 00 A b 01 A c 10 A d 11 e We can represent these codes as a tree A Characters are stored at the leaves of the tree A Code is represented by path to leaf Department of Computer Science University of San Francisco p821 107 Representing Codes as Trees 639 a 00 b 01 c 10 d11 Department of Computer Science University of San Francisco p921 108 Representing Codes as Trees e a01b00c11d10 Department of Computer Science University of San Francisco p1021 109 Prefix Codes e If no code is a prefix of any other code then decoding the file is unambiguous a How do you know whether a string is one complete code or part of another 6 If all codes are the same length then no code will be a prefix of any other code trivially e We can create variable length codes where no code is a prefix of any other code Department of Computer Science University of San Francisco p1121 1010 Variable Length Codes e Variable length code example a a0b100c101d11 Decoding examples A 100 A 10011 A 01101010010011 Department of Computer Science University of San Francisco p1221 1011 Prefix Codes amp Trees e Any prefix code can be represented as a tree a0b100c101d11 Department of Computer Science University of San Francisco p1321 1012 File Length e If we use the code A 300 b01 c10 d11 How many bits are required to encode a file of 20 characters Department of Computer Science University of San Francisco p1421 1013 File Length o If we use the code A a00 b01 c10 d11 How many bits are required to encode a file of 20 characters 65 20 characters 2 bitscharacter 40 bits Department of Computer Science University of San Francisco p1521 1014 File Length e If we use the code A a0 b100 c101 d11 How many bits are required to encode a file of 20 characters Department of Computer Science University of San Francisco p1621 1015 File Length e If we use the code A a0 b100 c101 d11 How many bits are required to encode a file of 20 characters 65 It depends upon the number of a s b s c s and d s in the file Department of Computer Science University of San Francisco p1721 1016 File Length e If we use the code A a0 b100 c101 d11 How many bits are required to encode a file of A 11 a s 2 b s 2 c s and 5 d s Department of Computer Science University of San Francisco p1821 1017 File Length e If we use the code A a0 b100 c101 d11 How many bits are required to encode a file of A 11 a s 2 b s 2 c s and 5 d s 11123235233lt4O Department of Computer Science University of San Francisco p1921 1018 Decoding Files e We can use variable length keys to encode a text file 65 Given the encoded file and the tree representation of the codes it is easy to decode the file o 0111001010011 Department of Computer Science University of San Francisco p2021 1019 Decoding Files We can use variable length keys to encode a text file Given the encoded file and the tree representation of the codes it is easy to decode the file Finding the kth character in the file is more tricky Department of Computer Science University of San Francisco p2121 1020 Decoding Files We can use variable length keys to encode a text file Given the encoded file and the tree representation of the codes it is easy to decode the file Finding the kth character in the file is more tricky A Need to decode the first k1 characters in the file to determine where the kth character is in the file A Gain space lose random access Department of Computer Science University of San Francisco p2221 1021 File Compression e We can use variable length codes to compress files a Select an encoding such that frequently used characters have short codes less frequently used characters have longer codes A Write out the file using these codes a lfthe codes are dependent upon the contents of the file itself we will also need to write out the codes at the beginning of the file for decoding Department of Computer Science University of San Francisco p2321 1022 File Compression e We need a method for building codes such that a Frequently used characters are represented by leaves high in the code tree A Less Frequently used characters are represented by leaves low in the code tree A Characters of equal frequency have equal depths in the code tree Department of Computer Science University of San Francisco p2421 1023 Huffman Coding e For each code tree we keep track of the total number of times the characters in that tree appear in the input file 6 We start with one code tree for each character that appears in the input file 6 We combine the two trees with the lowest frequency until all trees have been combined into one tree Department of Computer Science University of San Francisco p2521 1024 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a 100 b 20 c15 d 30 e 1 aleO b 20 C 15 130 e1 Department of Computer Science University of San Francisco p2621 1025 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a100b20c15d30e1 16 aleO bz20 C15 ezl dz3O Department of Computer Science University of San Francisco p2721 1026 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a 100 b 20 c15 d 30 e 1 lc15 e1 Department of Computer Science University of San Francisco p2821 1027 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a 100 b 20 c15 d 30 e 1 Department of Computer Science University of San Francisco p2921 1028 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a 100 b 20 c15 d 30 e 1 Department of Computer Science University of San Francisco p3021 1029 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a 10 b 10 c10 d 10 e 10 a 10 b 10 C 10 1le 810 Department of Computer Science University of San Francisco p3121 1030 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a 10 b 10 c10 d 10 e 10 20 lO lO ile elOl Department of Computer Science University of San Francisco p3221 1031 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a 10 b 10 c10 d 10 e 10 20 20 lO lO lO Department of Computer Science University of San Francisco p3321 1032 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a 10 b 10 c10 d 10 e 10 lale I lblel lClO ldlel Department of Computer Science University of San Francisco p3421 1033 Huffman Coding 939 Example Ifthe letters ae have the frequencies a a 10 b 10 c10 d 10 e 10 Department of Computer Science University of San Francisco p3521 1034 Huffman Trees amp Tables o Once we have a Huffman tree decoding a file is straightforward but encoding a tree requires a bit more information o Given just the tree finding an encoding can be difficult o What would we like to have to help with encoding Department of Computer Science University of San Francisco p3621 1035 Encoding Tables 100 1010 11 CDQOO39QJ 1011 Department of Computer Science University of San Francisco p3721 1036 Creating Encoding Table e Traverse the tree A Keep track of the path during the traversal 6 When a leaf is reached store the path in the table Department of Computer Science University of San Francisco p3821 1037 Huffman Coding e To compress a file using huffman coding A Read in the file and count the occurrence of each character and built a frequency table Build the Huffman tree from the frequencies Build the Huffman codes from the tree Print the Huffman tree to the output file for use in decompression Print out the codes for each character Department of Computer Science University of San Francisco p3921 1038 Huffman Coding e To uncompress a file using huffman coding a Read in the Huffman tree from the input file a Read the input file bit by bit traversing the Huffman tree as you go A When a leaf is read write the appropriate file to an output file Department of Computer Science University of San Francisco p4021 public public public public public public public public public 1039 Binary Files BinaryFileString filename char readOrWrite boolean EndOfFile char readChar void writeCharchar c int readInt void writeIntint i boolean readBit void writeBitboolean bit void close Department of Computer Science University of San Francisco p4121 1040 Binary Files 3 readBit A Read a single bit readChar a Read a single character 8 bits e readlnt a Read a single int 9 bits in the range 255 255 Department of Computer Science University of San Francisco p4221 1041 Binary Files 3 writeBit A Writes out a single bit writeChar a Writes out a single 8 bit character a writelnt a Writes out a single 9 bit integer If the value passed in is greater than 255 or less than 255 value printed out is not guaranteed Department of Computer Science University of San Francisco p4321 1042 Binary Files is If we write to a binary file a bit bit char bit int And then read from the file a bit char bit int bit e What will we get out Department of Computer Science University of San Francisco p4421 6 If we write to a binary file a bit bit char bit int And then read from the file a bit char bit int bit What will we get out Garbage except for the first bit 1043 Binary Files Department of Computer Science University of San Francisco p4521 1044 Printing out Trees e To print out Huffman trees a Print out nodes in preorder traversal A Need a way of denoting which nodes are leaves and which nodes are interior nodes Huffman trees are full every node has 0 or 2 children A Print out 9 bits for each node positive values for leaves negative values for interior nodes Value printed for interior nodes doesn t matter as long as it is negative Department of Computer Science University of San Francisco p4621 1045 Command Line Arguments public static void mainString args 6 The args parameter holds the input parameters 6 java MyProgram arg1 argZ arg3 a argslength 3 A args0 arg1 a args1 ar92 A args2 arg3 Department of Computer Science University of San Francisco p4721 ALA L 1 1 Data Structures and Algorithms Discrete Math Review Chris Brooks Department of Computer Science University of San Francisco Department of Computer Science 7 University of San Francisco 7 p 13 20 Discrete Math Review Sets Logarithms Summations Recursion Proof Techniques Department of Computer Science University of San Francisco p231 21 Sets A set is a collection of distinguishable objects usually called members or elements A 1234 A redgreen blue A 123456 I is the set with no elements the empty set A denotes the cardinality size of set A a e A indicates that object a is in set A Department of Computer Science University of San Francisco p331

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