FTCE Computer Science K12 Exam Prep Questions and Correct Solutions

Asymptotic Analysis - How the run time of a program depends on the size of the problem Exact Analysis - Provides a more specific measure of algorithm efficiency than asymptotic analysis. Divide and Conquer Algorithm - An algorithm that solves a problem recursively by splitting it into a fixed number of smaller non-overlapping subproblems of the same type Greedy Algorithm - An algorithm that follows problem solving heuristic of making optimal choices at each stage. Disadvantages of Greedy Algorithms - 1. Short sighted 2. Non-Recoverable Backtracking Algorithm - A general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate as soon as it determines that the candidate cannot possibly be completed to a valid solution. Branch and Bound Algorithm - Eliminates groups of trees from consideration upon discovering that all their members are worse than the best tree found so far Sorting Algorithms - arrange items in a list in a particular order Multiplication Algorithm - Performs the basic operations of single-digit arithmetic. Graph Searching Algorithm - Searches for the number of graph edges and number of graph nodes. Big Theta Notation - A method of classifying the time complexity of algorithms according to realistic sets of bounding criteria that can be used to provide the best and worst case scenarios. Quick Sort Algorithm - This uses a divide and conquer algorithm. First the pivot value which is the first item in the list is selected. Then the remainder of the list is divided into two partitions, the elements less than the pivot is in the first partition and the greater elements in the second. Advantages of quick sort - 1. Extremely Fast 2. No need for Additional Memory Disadvantages of quick sort - 1. If the split point is nearer to the start or end of the list, the division will be very uneven. 2. If the list is very large, and recursion continues too long, it may cause stack overflow and the program will crash. Merge Sort - A list is split into individual lists, these are then combined (2 lists at a time). Candidate Set - Contains the data used to devise a solution. Selection function - Chooses the best candidate and adds it to the solution. Feasibility Function - Examines the candidate in order to determine whether or not it can be used to solve the problem. Objective Function - Gives a value to the solution. Solutions function - Determines if the complete solution has been found yet (returns a Boolean) Greedy Choice Property - A solution can be constructed incrementally without reference to future decisions, past decisions, or the set of possible solutions to the problem. Optimal Substructure Property - Present only if the optimal solution in any current stage always eventually leads to the optimal global solution. Variations of a Greedy Algorithm - 1. Pure Greedy Algorithm 2. Orthogonal Greedy Algorithm 3. Relaxed Greedy Algorithm Examples of Greedy Algorithms - 1. Kruskal's Algorithm 2. Prim's Algorithm 3. Dijkstra's Algorithm Dynamic Programming Design Paradigm - Programs solve problems by using recursive processes designed to divide the problem into smaller steps. Required Properties for Dynamic Programming Design Paradigm - 1. Optimal Substructure 2. Overlapping Sub-Problems 3. Sub-Problems that are only slightly smaller than the problem. Top-Down Approach - Most direct method using recursive procedures. Divides problems, adds solutions to table, then checks if existing solution occurs before creating new solution.