Unformatted text preview:

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 DevelopmentSoftware development is a complex process that is both an art and a scienceIt is an art in that it requires a good deal of imagination, creativity, and ingenuityIt is also a science that it uses certain standard techniques and methodologiesSoftware Development PhasesProblem Analysis and SpecificationDesignCodingTesting, Execution, and DebuggingMaintenanceRealistic Waterfall ModelTask AnalysisPurposePre-condition (input): describe the state of processing before the program is executedPost-condition (output): describe the state of processing after the program is executedTesting, Execution, and DebuggingErrors 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 testingBlack box testing:Outputs produced for various inputsChecked 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 testingWhite box testing:examine code’s internal structure(Test for every loop, if statement, functions…)Test data is carefully selectedLIST ADTCollection of data elementsA sequence with a finite number of data items, all of the same typeBasic operationsConstruction---create a empty list Empty---check if the list is emptyInsert---insert an itemDelete---remove a itemTraverse---go through the list or part of itStatic Array basedNormally sequential orderings of list elements match with array elementsOf course, the array must be large enough to hold all of the list elementsIt means we need to chose carefullyStatic Array basedInsert: we need to doCheck the capacityNeed to move array elements to make room for the new elementStatic Array basedAlgorithm 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 basedThe efficiency of this insert algorithm obviously depends on the number of array elements that must be shifted to make room for the new itemIn 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 basedDelete: also requires shifting array elementsFor example, to delete the second item in:23, 25, 34, 48, 56, 61, 79, 82, 89, 91, 99Static Array basedAlgorithm 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 ListLinked list nodes containData part – stores an element of the listNext part – stores link/pointer to next element (when no next element, null value)TraverseWe begin by initializing an auxiliary variable ptr to point to the first node:Initialize a variable ptr to point to first nodeProcess data where ptr pointsTraverseTraverse (ctd)set ptr = ptr->next, process ptr->dataContinue until ptr == nullInsertionTo insert a new data value into a linked list, we must first obtain a new node and store the value in its data partThe second step is to connect this new node to existing listTwo cases in this situation: (1) insertion after some element in the list and (2) insertion at the beginning of the listInsertionInsertion To insert 20 after 17Need address of item before point of insertionpredptr points to the node containing 17Get a new node pointed to by newptr and store 20 in itSet 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 predecessorDelete the first element in the listDeletionDelete node containing 22 from list.Suppose ptr points to the node to be deletedpredptr 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 deletedDeallocate the node being deleted. predptrptrTo free spaceBig O NotationBig 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 SearchIf 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 SubsequenceGiven (possibly negative) integers A1, A2, .., An, find (and identify the sequence corresponding to) the max. value of


View Full Document

GSU CSC 2320 - exam1 review

Download exam1 review
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view exam1 review and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view exam1 review 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?