Exam 1 ReviewSoftware DevelopmentSoftware Development PhasesRealistic Waterfall ModelTask AnalysisTesting, Execution, and DebuggingThe "V" Life Cycle ModelTwo major types of testingSlide 9LIST ADTStatic Array basedSlide 12Slide 13Slide 14Slide 15Slide 16Linked ListTraverseSlide 19InsertionSlide 21DeletionSlide 23Big O NotationBinary SearchBinary Search 3-ways comparisonsThe Max. Contiguous SubsequenceO(n3) Algorithm AnalysisO(N2) Algorithm cont.Designing and Building a Stack classImplementation of the OperationsSlide 32Slide 33Linked StacksImplementing Linked Stack OperationsSlide 36Consider the following program segmentUse of Run-time StackIntroduction to QueuesCircular QueueQueue Full SituationAlgorithm for Enqueue(value)Algorithm for Dequeue()Linked QueuesFunctions related to StackEnqueue and FrontDequeueQueue + StackExam 1 ReviewDr. Bernard Chen Ph.D.University of Central ArkansasFall 2008Software DevelopmentSoftware development is a complex process that is both an art and a scienceIt is an art in that it requires a good deal of imagination, creativity, and ingenuityIt is also a science that it uses certain standard techniques and methodologiesSoftware Development PhasesProblem Analysis and SpecificationDesignCodingTesting, Execution, and DebuggingMaintenanceRealistic Waterfall ModelTask AnalysisPurposePre-condition (input): describe the state of processing before the program is executedPost-condition (output): describe the state of processing after the program is executedTesting, Execution, and DebuggingErrors happen all the time!!!There are three different points at which errors can be introduced:1. Syntax errors2. Run-time errors3. Logic errorsThe "V" Life Cycle ModelTwo major types of testingBlack box testing:Outputs produced for various inputsChecked for correctness Do not consider structure of program component itself.(so basically, it just test a lot of different inputs and match with the expected outputs )Two major types of testingWhite box testing:examine code’s internal structure(Test for every loop, if statement, functions…)Test data is carefully selectedLIST ADTCollection of data elementsA sequence with a finite number of data items, all of the same typeBasic operationsConstruction---create a empty list Empty---check if the list is emptyInsert---insert an itemDelete---remove a itemTraverse---go through the list or part of itStatic Array basedNormally sequential orderings of list elements match with array elementsOf course, the array must be large enough to hold all of the list elementsIt means we need to chose carefullyStatic Array basedInsert: we need to doCheck the capacityNeed to move array elements to make room for the new elementStatic Array basedAlgorithm for insert:If size is equal to capacity: display error due to limit spaceIf pos < 0 or pos > size: display error due to error positionElse: for i in rangeing from size to pos+1:array[i]=array[i-1] //C++ starts index from 0array[pos]=itemsize++Static Array basedThe efficiency of this insert algorithm obviously depends on the number of array elements that must be shifted to make room for the new itemIn worst case, the new item must be inserted at the beginning of the list O(n)The best case occurs when the new item is inserted at the end of it O(1)Two important special kinds of lists for which are stacks and queuesStatic Array basedDelete: also requires shifting array elementsFor example, to delete the second item in:23, 25, 34, 48, 56, 61, 79, 82, 89, 91, 99Static Array basedAlgorithm for delete:If size is zero:issue a error messageIf pos <0 or pos >=size:issue an error message Otherwise:for index i ranging from pos to size-2:array[i]=array[i+1]size--Linked ListLinked list nodes containData part – stores an element of the listNext part – stores link/pointer to next element (when no next element, null value)TraverseWe begin by initializing an auxiliary variable ptr to point to the first node:Initialize a variable ptr to point to first nodeProcess data where ptr pointsTraverseTraverse (ctd)set ptr = ptr->next, process ptr->dataContinue until ptr == nullInsertionTo insert a new data value into a linked list, we must first obtain a new node and store the value in its data partThe second step is to connect this new node to existing listTwo cases in this situation: (1) insertion after some element in the list and (2) insertion at the beginning of the listInsertionInsertion To insert 20 after 17Need address of item before point of insertionpredptr points to the node containing 17Get a new node pointed to by newptr and store 20 in itSet the next pointer of this new node equal to the next pointer in its predecessor, thus making it point to its successor. Reset the next pointer of its predecessor to point to this new node20newptrpredptrDeletion For deletion, there are also two cases to consider:Deleting an element that has a predecessorDelete the first element in the listDeletionDelete node containing 22 from list.Suppose ptr points to the node to be deletedpredptr points to its predecessor (the 17)Do a bypass operation: Set the next pointer in the predecessor to point to the successor of the node to be deletedDeallocate the node being deleted. predptrptrTo free spaceBig O NotationBig O notation is used to capture the most dominant term in a function, and to represent the growth rate.Also called asymptotic upper bound. Ex: 100n3 + 30000n =>O(n3) 100n3 + 2n5+ 30000n =>O(n5)Binary SearchIf the array has been sorted, we can use binary search, which is performed from the middle of the array rather than the end.We keep track of low_end and high_end, which delimit the portion of the array in which an item, if present, must reside.If low_end is larger than high_end, we know the item is not present.Binary Search 3-ways comparisonstemplate < class Comparable>int binarySearch(int a[], int x){int low = 0;int high = a.size() – 1; int mid;while(low < high) {mid = (low + high) / 2;if(a[mid] < x)low = mid + 1;else if( a[mid] > x)high = mid - 1;else return mid;}return NOT_FOUND; // NOT_FOUND = -1}//binary search using three-ways comparisonsThe Max. Contiguous SubsequenceGiven (possibly negative) integers A1, A2, .., An, find (and identify the sequence corresponding to) the max. value of
View Full Document