Conference, Team, Player, ScholarshipPlayerPlay Game, TransferConferences have Teams, Teams have Players,NoneScholarshipPlayers are PlayersAmount of resources required by algorithm with respect to problem sizeMeasures performance for a particular hardwareMinimum, maximum, and typical number of steps required by algorithmUpper bound on the number of steps required by algorithmThe number of steps required by each algorithm grows at a different rate with respect to the problem sizeSingle successor vs. multiple successorsSmaller values in left subtree, larger values in right subtreeO(log(n))find( n )Maps have keys to their elementsOperations take more stepsBase case and recursive stepSingle predecessor vs. multiple predecessorsEdges are one-way or bi-directionalCycle returns to its starting nodeEdge list & adjacency matrixSpace usage depends on Edge/Node ratio of graphMay encounter cyclesBreadth-first visits closer neighbors first, depth-first finishes exploring all reachable nodes from current node firstMaintain set of nodes with known shortest path from start (and their costs & predecessors), repeatedly add node closest to set (updating table of costs & predecessors) until all nodes in set.Table BestKnownDistancesFS, A, B, F, D, C, E, H, GS, cost = 0S->A, cost = 10S->B, cost = 14S->B->F, cost = 18S->A->D or S->B->D, cost = 22S->A->C, cost = 26S->A->D->E or S->B->D->E, cost = 28S->B->F->H, cost = 29S->A->D->E->G or S->B->D->E->G, cost = 33Classes defined in the scope of another classStatic inner classesTo define classes that need to access private members of enclosing classWhen name of inner class is not needed because it is used only onceRun-time errors detected during program executionTo represent run-time errors found by JavaSerious run-time errors (should be made unchecked exceptions) and common errors the program can handle (should be made checked exceptions)Try surrounds code that may cause exception, catch specifies exceptions caught and action performed, finally specifies action performed after try block exits (whether an exception is thrown or not)The Java compiler attempts to require all checked exceptions to be caught at some point in the Java program.Capture logical structure of problem, better utilize hardware resourcesNew, Runnable, Running, Blocked, DeadTells JVM thread is now RunnableTells JVM to wait until thread is Dead before continuing executionDeciding which thread(s) to run, and for how longPremptive scheduling can stop threads, non-preemptive scheduling has to wait for threads to stopConcurrent accesses to shared variable, where at least one access is a writeResults may differ based on scheduling, causing intermittent errors that are hard to debugCoordinating events with respect to timeTo eliminate data races in multithreaded codeEntity associated with each Object that can be held by one thread at a timeJava locks may be used to enforce mutual exclusion (by having multiple threads attempt to hold the same lock before executing) for a region of codeThreads are blocked waiting for locks with no possibility of making progress, program is unable to continue executionProgram will not complete executionData race on shared variable myElementsAdd synchronized keyword to both methodsModel is the data, View is what is displayed, Controller is used by user to interact with the model & viewReduce complexity of softwareExternal events that occur outside the control of the program that must be handled by the programTo represent user actionsEvents are generated by individual components (e.g., JButton) and handled using ActionListeners registered for the componentSorting algorithm using only pairwise key comparisonsDepends on qualities beyond pairwise key comparisons (e.g., alls keys have values between X and Y)Sorting algorithm leaves relative order of keys with equal value unchangedSorting algorithm only needs small constant amount of additional spaceSorting algorithm is designed for efficiency when keys do not all fit in memory (i.e., very large number of keys)Type of algorithm that divides problem into smaller problems of the same type and recursively solves them, combining their solutions for overall solutionType of algorithm that divides problem into smaller overlapping problems of the same type and recursively solves them, remembering previous solutions to subproblems.Dynamic programming remembers solutions to subproblems, divide-and-conquer resolves subproblemsBacktracking algorithms may use recursion to implement backtrackingGreedy algorithms achieve optimal solutions by selecting best (local) choice at each step. Heuristics use rules of thumb (such as greedy) to make a choice at each step, but are not guaranteed to achieve the best solutionBranch-and-bound algorithms attempt to reduce searching by eliminating partial solutions that are already worse than the best current solution foundImprove efficiency by avoiding repeating workSimple approach to searching for all possible solutionsNeed optimal solution but more efficient algorithms not knownGreedyDescriptions of reusable solutions to common software design problemsProgrammers found certain problems were solved repeatedlyWhen common software design problems are encountered that have been previously solvedIterator, Decorator, Marker, Observerpublic class BoatDecorator implements Boat {Boat b;BoatDecorator (Boat b) { this.b = b; }int topSpeed( ) { return b.topSpeed( ); }}public class withBarnacle( ) extends BoatDecorator {int topSpeed( ) { return b.topSpeed( ) - 1; }}public class withTurboEngine( ) extends BoatDecorator {int topSpeed( ) { return b.topSpeed( ) + 10; }}Boat myBoat = new withBarnacle( new withBarnacle(new withTurboEngine( new SpeedBoat( ) ) ) );CMSC132 Partial Solutions to Final Exam Practice QuestionsProblem 1 Software Engineering & Object Oriented Design A. Software Development and Testinga. Software is difficult because programmers are slow T or Fb. Software life cycle refers to how software is used T or Fc. Problem specification is a component of software development T or Fd. Problem specification is less important than program testing T or Fe. Iterative development is a software development methodology T or Ff. Black box testing is usually easier than clear box testing T or Fg. Integration tests are usually more important than unit tests T or Fh. Test coverage includes consideration of lines of code tested T or Fi. Test drivers are only found on NASCAR training tracks T or FB. Object-oriented
View Full Document
Unlocking...