Computer Science II
Computer Science II COP 3503
University of Central Florida
Popular in Course
Popular in Computer Programming
This 19 page Class Notes was uploaded by Luisa Beer on Thursday October 22, 2015. The Class Notes belongs to COP 3503 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 24 views. For similar materials see /class/227465/cop-3503-university-of-central-florida in Computer Programming at University of Central Florida.
Reviews for Computer Science II
Report this Material
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/22/15
Mathematical Preliminaries Logs The log function is the inverse of an exponent Thus if we have a b then it follows by definition that log b c a Since a positive number to any exponent can never be negative and only logs with positive bases except for 1 are computed it follows that you can never take the log of 0 or any negative value Take a look in your book on page 103 to review several rules that apply to logarithms and exponents logba logbc logbac logba logbc logbac logbac clogba logba logca logcb bquotlogca aquot logcb bah bac babc ba c bac bac Summations By definition of a summation we have the following general form 2 fz39fafa1fa2fb Here are a couple standard summations formulas we will use often n1 1l a Ea 1 61 and nnl El 2 Also here is an example of a technique that works with some sums Find 12quot 205 322 n2quot391 Let s 12quot 221 322 n2quot391 Then zs 121 222 323 n2quot Now subtract the bottom equation from the top s 12quot 21 22 2 391 n2quot s n2quot 20 05 22 0 s n2quot 21 s n2quot 2n 12 1 n12 1 Proof Technique By Example If you have a statement of the form quotThere exists a value of x which satisfies property Pquot then all you need to do to prove it is nd a single value of x for which the property P is satisfied Consider this example There exists input such that Insertion Sort runs in On time for that particular input Consider the input 123n for an input array of size n Tracing through the code for insertion sort shows that the inner for loop in each instance runs only once Thus the algorithm runs in On for the input listed above Similarly if you ever have a statement of the form quotFor all values of x the property P is satis edquot then all you would need to do to DISPROVE the statement is nd a single value of x for which the statement is false Consider the following example For all possible inputs Merge Sort runs faster than Insertion Sort This statement is false Once again consider already sorted input Merge Sort runs in 6nlgn regardless of the input but as we mentioned above Insertion Sort on the already sorted input is faster On Proof Technique Proof by Contradiction If you are asked to prove an if then statement one method is to prove the contrapositive of this statement The method in which to do this is simply assume the opposite of the conclusion Under this assuption make logical deductions Eventually one of these logical deductions should contradict some type of wellknown information or one of the premises Since this is impossible the conclusion is that an incorrect step must have been taken in the proof The only possible incorrect step was making the initial assumption Thus this assumption is faulty so the opposite of it is true and that proves the assertion Here39s an example Prove the correctness of the binary search algorithm shown in class last time Clearly the algorithm never reports a false positive It can ONLY say val is found if a particular array element equals val Thus we must show that it is impossible for the algorithm to NOT find a value that is actually in the sorted array Assume to the contrary that there exists an sorted array input A and a value val such that the algorithm does not find val in the array when it really does exist in the array Let val be in array location x in the array In order for the algorithm to not find val the value of mid must never equal x during the running of the algorithm In order for this to occur at some point in the algorithm low would have to be set to x1 or more OR high would have to be set to x1 or less In order for either of these things to occur the appropriate if statement choices must be met If low is set to x1 or more that means that a comparison was made with val and Ax1 or some higher index and val was greater than that value But since we know that AX val this contradicts the fact that the array was sorted Similarly if high is ever set to Xl or less we once again get a contradiction to the fact that the array is sorted Proof Technique Induction Based on past experience with this class I39ve found that I don39t have enough time to teach induction effectively and still cover all the algorithm and data structure material necessary for this course But in order for me to illustrate my example for loop invariants I need induction Plus the concept of induction is a very important one So I will give you a very short synopsis of induction so you can see the main idea and understand my loop invariant example Mathematical induction can be used to prove a particular statement about all positive integers The basic idea of the proof method is as follows Consider trying to prove some statement to be true for all positive integers 11 To do this you must do the following three steps 1 Show that the statement is true for n1 2 Assume the statement is true for an arbitrary value of nk 3 Prove the statement is true for nk1 The idea is that if you can always show that if a statement is true for one integer it is always true for the next one and the statement is true for 1 then it must be true for 2 But if it39s true for 2 it must also be true for 3 then 4 etc Repeating the application of the rule if the statement is true for k it is true for k1 as many times as necessary proves the statement for any positive integer desired Proof Technique Loop Invariant If you want to prove some statement S about a loop sometimes you can do so through proving that a loop invariant is true Consider the following code int max numbers0 for int i1 iltnumberslength i if numbers i gt max max numbersi Supposed we wanted to prove that max stored the largest value in the array numbers after this code segment was executed We can prove this through the use of a loop invariant A loop invariant is a statement that is ALWAYS true about a loop at a particular point in its execution for EACH iteration Consider the following loop invariant for the code above At end of a loop iteration right before i is executed max stores the largest value from the set numbers0 numbersl numbersi Now let39s prove this loop invariant through induction on i Base case i0 Before the loop begins max stores numbers0 which is the maximum value from the set numbers0 Assume for an arbitrary value k of i lt numberslength that after the k th loop iteration max stores the largest value from the set numbers0 numbersl numbersk Now we must prove for ik1 that after the k1 loop iteration max stores the largest value from the set numbers0 numbersl numbersk1 Consider running the k1 loop iteration First i gets incremented Thus now ik1 Next numbersk1 is compared to max If max is larger we know that there is a value in the set numbers0 numbersk that is larger than numbersk1 based on the inductive hypothesis If this is the case it necessarily follows that maxnumbers0 numbersk maxnumbers0numbersk1 Thus when the if statement does not execute max does correctly store the maximum value from the set numbers0 numbersk1 The other possibility is that numbersk1gtmax By the inductive hypothesis it follows that numbersk1 is greater than each value in the set numbers0 numbersk Thus it follows that maxnumbers0numbersk1 numbersk1 This is EXACTLY what max will get set to in the if statement Thus we can conclude in all cases that max will store the maximum value in the set numbers0 numbersk1 after the k1 loop iteration A Sample Algorithm Sorted List Matching Problem given two sorted lists of names output the names common to both lists Perhaps the standard way to attack this problem is the following For each name on list 1 do the following a Search for the current name in list 2 b If the name is found output it If a list is unsorted steps a and b may take On time Can you tell me why BUT we know that both lists are already sorted Thus we can use a binary search in step a From 81 we learned that this takes Olog n time where n is the total number of names in the list For the moment if we assume that both lists are of equal size then we can safely say that the size of list 2 is about 12 the total input size so technically our search would take Olog n2 time where n is the TOTAL SIZE of our input to the problem Using our log rules however we find that log n log n2 1 Thus it s fairly safe to assume for large n that our running time is simply Olog2 11 Now that is simply the running time for 1 loop iteration But how many loop iterations are there Assume that there are n2 names on each list again where n is the TOTAL SIZE of the input Under our assumption there will be n2 loop iterations so our total running time would be On log 11 Why did I not divide the expression in the BigO by 2 A natural question becomes Can we do better The answer is yes What is one piece of information we have that our first algorithm does NOT assume That list 1 is sorted You ll notice that our previous algorithm will work regardless of the order of the names in list 1 But we KNOW that this list is sorted also Can we exploit this fact so that we don t have to do a full binary search for each name Consider how you d probably do this task in real life List 1 List 2 Adams Boston Bell Davis Davis Duncan Harding Francis Jenkins Gamble Lincoln Harding Simpson Mason Zoeller Simpson You d read that Adams and Boston are the first names on the list Immediately you d know that Adams wasn t a match and neither would any name on the list 1 alphabetically before Boston So you d read Bell and go on to Davis At this point you d deduce that Boston wasn t on the list either so you d read the next name on list 2 voila A match You d out put this name and simply repeat the same idea In particular what we see here is that you ONLY go forward on your list of names And for every step so to speak you will read a new name off one of the two lists Here is a more formalized version of the algorithm 1 Start two markers one for each list at the beginning of both lists 2 Repeat the following steps until one marker has reached the end of its list a Compare the two names that the markers are pointing at b If they are equal output the name and advance BOTH markers one spot If they are NOT equal simply advance the marker pointing to the name that comes earlier alphabetically one spot There are some slight mistakes in this algorithm but the overall idea is here and you will fix the mistakes when you write a program to implement this algorithm for your homework Now before we finish the lecture the last thing we must do is analyze the running time of this algorithm Here is what we see For each loop iteration we advance at least one marker The maximum number of iterations then would be the total number of names on both lists which is 11 using our previous interpretation For each iteration we are doing a constant amount of work Essentially a comparison and sometimes outputting a single name Thus our algorithm runs in On time an improvement over our previous algorithm A final question one must ask is can we solve this question in even less time If yes what is such an algorithm if no how can we prove it Our proof goes along these lines In order to have an accurate list we must read every name on one of the two lists If we skip names on BOTH lists we can NOT deduce whether we would have matches between those names or not In order to simply read all the names on one list we would take On2 time But in order notation this is still On the running time of our second algorithm Thus we know we can not do better in terms of time within a constant factor of our second algorithm Binary Trees You have covered these in C81 but we39ll look at them in greater detail in this class also noting implementation differences between C and Java We will declare a Binary Tree Node class BinTreeNode to store a single node Here are the instance variables of the class public int data public BinTreeNode left public BinTreeNode right Also just as we did with linked lists we will have a second class that maintains a Binary Tree which will be called BinTree It will only have a single BinTreeNode instance variable private BinTreeNode root We will actually do most of our work through the BinTreeNode class The only cases that we will pay attention to in the BinTree class are the ones that deal with the empty binary tree An empty binary tree will be represented by the instance variable root being null But for the most part all the methods in the BinTree class will call on their counterparts in the BinTreeNode class Review Tree Traversals Visiting each node in a binary tree is not as straight forward as in a linked list In particular you can39t necessarily go in a quotstraight linequot But recursion helps solve the problem Notice that each BinTreeNode is made of three components 1 A value 2 A left subtree 3 A right subtree One can visit each node in the structure by simply visiting these three components in any order Notice that components 2 and 3 are trees as well thus necessitating recursion Our convention is that we will visit the left subtree before the right This leaves us three different orders to visit the three components above Each of these orders corresponds to a tree traversal as follows Preorder Tree Traversal 1 Visit the root 2 Visit the left subtree 3 Visit the right subtree Inorder Tree Traversal 1 Visit the root 2 Visit the left subtree 3 Visit the right subtree Postorder Tree Traversal 1 Visit the root 2 Visit the left subtree 3 Visit the right subtree Code for traversals The code for each of the three tree traversals is quite similar Here is the code for the Inorder traversal In the BinTree class public void Inorder if root z null rootInorder In the BinTreeNode class public void Inorder if left null leftInorder Systemoutprintdataquot quot if right null rightInorder Before we move on let39s trace through an example of each of the traversals Inserting a Node Into a Binary Tree If we are doing an insert into a BinTreeNode object which must have at least one node here39s a basic outline of the steps necessary 1 Compare the value to insert to the root value 2 If the value to insert is less insert the node into the left subtree This can be done using a temporary pointer Also if this subtree is null make room for the node and insert it 3 If the value is greater than or equal to the root value do exactly as listed above in step 2 except to the right side Now the only case not considered is inserting into an empty Binary Tree object Here we can just create a single BinTreeNode storing the value to insert The code corresponding to this is in the BinTree class Consider the following illustrations Code to do an Insert BinTreeNode class Inserts a new node storing the value X into the binary search tree with the root as the current object public void insertint X Create new node to insert BinTreeNode temp new BinTreeNodeX BinTreeNode cur this temp node to traverse tree boolean done false while Idone Decide if node should be inserted in R or L subtree if curdata gt X Only traverse down tree if left pointer isn39t null if curleft null cur curleft Or insert temp node in the correct location else curleft temp done true else Only traverse down tree if right pointer isn39t null if curright null cur curright Or insert temp node in the correct location else curright temp done true The necessary changes to the BinTree class are minimal Inserts a node containing X into the binary tree public void insertint x if root null root new BinTreeNodeX else r00tinsertx Deleting from a Binary Tree When deleting a node from a binary tree here are the three cases to consider 1 Node to delete is a leaf node 2 Node to delete has one child 3 Node to delete has two children The first case is the easiest Just find the parent and set either it39s left or right which ever is appropriate to null For the second case we see that we can just quotpatchquot the appropriate parent link to the child of the node to be deleted Finally for the third case we can find a value in the tree to replace the value at the node to be deleted In particular the minimum value in the right subtree of the node can be stored in the node to be deleted Then we can delete the old node that value was stored in because it had at most 1 child Consider each of these examples
Are you sure you want to buy this material for
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'