Computer Science I
Computer Science I COP 3502
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 3502 at University of Central Florida taught by Arup Guha in Fall. Since its upload, it has received 33 views. For similar materials see /class/227461/cop-3502-university-of-central-florida in Computer Programming at University of Central Florida.
Reviews for Computer Science I
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
QUEUES A queue is simply a waiting line that grows by adding elements to its end and shrinks by removing elements from the front Compared to stack it re ects the more commonly used maxim in realworld namely first come first served Waiting lines in supermarkets banks food counters are common examples of queues A formal definition of queue as a data structure It is a list from which items may be deleted at one end front and into which items may be inserted at the other end rear It is also referred to as a firstinfirstout FIFO data structure l l front rear Queues have many applications in computer systems Handling jobs in a single processor computer print spooling transmitting information packets in computer networks 0 Primitive ueue 0 erations enqueue q x inserts item X at the rear of the queue q x dequeue q removes the front element from q and returns its value isEmpty q Check to see if the queue is empty isFull q checks to see if there is space to insert more items in the queue Example Consider the following sequence of operations being performed on a queue q which stores single characters enqueueq W enqueueq B enqueueq 039 x dequeueq enqueueq D39 enqueueq E x dequeueq enqueueq H x dequeueq enqueueq J39 The contents of the queue q after these operations would be T T front Fear Array Implementation The array to implement the queue would need two variables indices called from and rear to point to the first and the last elements of the queue f ant reLr Initially q gtrear l q gtfront 1 For each enqueue operation rear is incremented by one and for each dequeue operation from is incremented by one While the enqueue and dequeue operations are easy to implement there is a big disadvantage in this set up The size of the array needs to be huge as the number of slots would go on increasing as long as there are items to be added to the list irrespective of how many items are deleted as these two are independent operations Problems with this representation Although there is space in the following queue we may not be able to add a new item An attempt will cause an over ow 0 1 2 3 4 front rear It is possible to have an empty queue yet no new item can be inserted when from moves to the point of rear and the last item is deleted rear front A solution Circular Array Let us now imagine that the above array is wrapped around a cylinder such that the first and last elements of the array are next to each other When the queue gets apparently full it can continue to store elements in the empty spaces in the beginning of the array This makes efficient use of the array slots It is also referred to as a circular array This enables us to utilize the unavailable slots provided the indices front and rear are handled carefully Here again from refers to the index of the element to be next removed from the queue and rear refers to the index of the last element added to the queue rear front equivalently front rear The queue is implemented on a circular array With each enqueue the rear index is incremented and with each dequeue the from index is incremented The wrap around is achieved by taking the mod function with the capacity of the array The queue is initialized with from rear 0 When the rst element is enqueued the rear index becomes 1 while the from index remains 0 When the second element is enqueued the rear index becomes 2 while the front index remains 0 If we now dequeue the from index becomes 1 and at the next dequeue operation the front index becomes 2 The queue is now empty as two elements were stored and these two were retrieved The index values are front rear 2 In fact at any stage the condition from rear indicates that the queue is empty Consider a queue with 71 slots Suppose the from index is zero and we go on lling up the queue When the last but one slot is lled up the rear index will have value 71 Now if we want to insert another element in the queue the rear index will be 71 But since we do not have the slot 71 it would point to the slot 0 Thus while the queue is actually full we have from rear 0 which is not possible because that is a condition for the queue to be empty Here we are faced with a contradiction To overcome this problem the last element is never lled up in a circular queue and when only a single slot is empty we declare the queue to be full Queue Size The front and rear indices can be used to nd out the current size of the queue that is the number of elements currently in the queue The value rear 7 from gives us the size and when this value is negative we simply add the capacity to this to give us the size Thus in general we have size rear 7 front capacity capacity Engueue and Degueue algorithms Here are the enqueue and the dequeue algorithms It is assumed here that the variables rear front and capacity are globally Visible initially rear 0 front 0 void enqueueint Q int d rearplusl rear1 capacity if rearplusl front print Q fullquot else Qrear d rear rearplusl void dequeue int Q dd iffront rear dd 9999 print Q emptyquot else dd Qfront fron front 1capacity Deletion from a Binary Tree Last time we outlined how to delete a node from a binary tree We broke up our work into three cases 1 Deleting a leaf node 2 Deleting a node with one child 3 Deleting a node with two children Keep these three in mind as well as how we determined the delete would work in these cases when looking at this code For a leaf node our job isn39t too hard The key will be identifying the parent of the node to delete Actually we39ll do this in the other cases as well Once we do this then we just have to set the appropriate node to NULL parert gtleft NULL or parent gtright NULL For the second task we39ll need to nd the parent node of the node to be deleted along with the sole child node of the node to be deleted and quotconnect themquot Here are the four possibilities 10 10 5 15 gt 1 15 delete 5 5 15 gt 7 15 delete 7 7 10 10 5 15 gt 7 12 delete 12 12 10 10 5 15 gt 7 15 delete 23 23 In each of these two main cases I am still glossing over a couple details 1 What happens if the node to delete IS the root node of the tree and has no parent 2 How do we free memory for the deleted node We39ll deal with both of these issues when we see the code Finally we have to deal with the case where a node to be deleted has two children The nice thing here is that we will not physically do the delete of the chosen node If we did deciding what gets to be the root node and what takes its place etc could be unusually complicated Could there be another node we physically delete so that we could essentially maintain the structure of the tree Consider the following example 30 15 45 5 23 39 50 18 36 If I were deleting 30 what two nodes could I replace the 30 with and still essentially maintain the binary tree property Since all the terms to the left of the 30 must be less than it and all to the right must be greater than it the only values we can put at the root wo serious repercussions are 1 The maximum value in the left subtree in this case 23 OR 2 The minimum value in the right subtree in this case 36 Once we pick one of these two to replace with the root node we must simply delete the node corresponding to the value we pick We are guaranteed that this node has at most one child Why is that Now let39s look at the picture of us deleting 30 from this node when we replace 30 with 18 15 45 5 23 39 50 36 Some Auxiliary Functions In aiding the delete function I have written several auxiliary functions 1 parent finds the parent of a given node in a given binary tree 2 minVal finds the minimum value in a given binary tree 3 maxVal finds the maximum value in a given binary tree 4 isLeaf determines if a node is a leaf node or not 5 hasOnlyLeftChild determines if a node ONLY has a left child or not 6 hasOnlyRightChild determines if a node ONLY has a right child or not 7 findNode returns a pointer to a node in a given tree that stores a particular value Time Complexity using Recurrence relations Some complexity analysis problems can be decomposed into subproblems having a mathematical pattern which can make use of recurrence relations A recurrence relation also known as a difference equation is an equation which describes the number of operations Tn required by an algorithm in terms of a recursive sequence each term of the sequence is defined as a function of the preceding terms Here is an example of a recurrence relation Tn Tn1 1 Tl 1 This can be interpreted as follows 1 The total number of operations needed for 11 data items can be obtained by adding one operation to total number of operations needed for n 7 1 data items 2 For a single data item the algorithm requires one operation It follows that Tnl can also be represented in terms of Tn2 in similar manner Tnl Tn2 1 Tn Tn2 2 The right hand side can be reduced in similar manner till we reach Tl as shown in the lecture class When we substitute for Tl we get the solution for Tn Let us see how the number of operations for the following code can be expressed in terms of a recurrence relation 3 N sum 0 while j gt 1 sumsum j more2 sum jj 2 It is noted that the time to solve the problem number of operations for the case jN is reduced to that of solving the problem for jN2 after 3 operations are carried out This can be expressed mathematically as TN T N2 3 It is easy to see the problem for N2 can be reduced to that of solving the problem for N 4 by using a similar argument TN43 3 T N8 3 3 which can be rewritten as TN23 33 TN24 43 The pattern is very clear now and one can write the general form as TNTN2k k3 Our aim is to reduce the rst term on the right hand side to Tl Let 2k N then k log N and we can express TN as TNT13logN So the complexity turns out to be Olog N Linear Search In C Programming we looked at the problem of finding a specified value in an array The basic strategy was Look at each value in the array and compare it to what we39re looking for If we see the value at any time return that we39ve found it Otherwise if after we39re done at looking through each item in the array if we still haven39t found it then return that the value isn39t in the array In code we have something like this int searchint array int len int value int i for i0 iltlen i if arrayi value return 1 return 0 Clearly for an unsorted array this algorithm is optimal There39s no way you can definitively say that a value isn39t in the array unless you look at every single spot Similarly there39s no way you can say that you DON39T have some piece of paper or form unless you look through ALL of your pieces of paper But we might ask the question could we find an item in an array faster if it were already sorted Binary Search Consider the following game you most likely played when you were a child I have a secret number in between 1 and 100 Make a guess and I39ll tell you whether your guess is too high or too low Then you guess again The process continues until you guess the correct number and your job is to minimize the number of guesses you make Typically most people39s first guess is 50 Here39s why No matter whether the response is quottoo highquot or quottoo lowquot the most number of possible values for your remaining search either from 149 or 51100 is 50 Any other first guess and there39s a possibility that the number of possible remaining values is greater than 50 For example if you guessed 75 and the response was quottoo highquot then your number could be any number from 174 or one of 74 possibilities So the basic idea behind the game is Always guess the number that is halfway between the lowest possible value in your search range and the highest possible value in your search range Now how can we adapt this idea to work for searching for a given value in an array If I am given the array Iindex0 I1 I2 I3 I4 I5 I6 I7 I8 I lvalue2 I6 I19 I27 I33 I37 I38 I41 I118 and am searching for 19 we might ask ourselves where is quothalfway in between One guess would be to look at 2 and 118 and take their average 60 But 60 isn39t in the list and if we look at the number closest to 60 we find that it39s almost at the end of the array Very quickly we realize that if we are to adapt the guessing game strategy to searching in an array that we want to search in the middle INDEX of the array In this case the lowest index is 0 the highest index is 8 so the middle index must be 4 Thus we would ask the question quotIs the number I am searching for 19 greater than or less than the number stored in index 4 33 The answer is quotless thanquot so we can modify our search range to in between index 0 and index 3 Note that index 4 is no longer in the search space From there we39d continue in this process the second index we39d look at is index 1 since 032 1 Then we39d finally get to index 2 since 232 2 and find 19 in the array Now let39s put this idea together and code it up int binsearchint a int len int value int low 0 high len 1 while low lt high int mid lowhigh2 if value lt amid high mid 1 else if value gt amid low mid1 else return 1 return 0 At the end of each array iteration all we do is update either low or high Doing so modifies our search region to be smaller than it previously was based on the last comparison we made Efficiency of Binary Search Now let39s analyze how many comparisons guesses are necessary when running this algorithm on an array of 11 items First let39s try n 100 After 1 guess we have 50 items left After 2 guesses we have 25 items left After 3 guesses we have 12 items left After 4 guesses we have 6 items left After 5 guesses we have 3 items left After 6 guesses we have 1 item left After 7 guesses we have 0 items left The reason we have to list that last iteration is because the number of items left represent the number of other possible values to search We need to reduce this to 0 Also note that when n is odd such as when n25 when we search the middle element element 13 there are 12 elements smaller than it and 12 elements larger than it so that39s why the number of items is slightly less than 12 in those cases In the general case we get something like After 1 guess we have n2 items left After 2 guesses we have n4 items left After 3 guesses we have n8 items left After k guesses we have n2k items left If we can find the value that makes this fraction 1 then we know that in one more guess we39ll narrow down the item 72 2721 n2quot 1610an This means that a binary search roughly takes log2n comparisons when searching for a value in a sorted array of 11 items This is much much faster than searching linearly Consider the following chart n log n 8 3 1024 10 65536 16 1048576 20 33554432 25 1073741824 30 Basically any algorithm that takes log2n steps is super fast