WGU C949 Essentials

WGU C949 Essentials Leave the first rating Students also studied Terms in this set (60) Science Computer Science Algorithms Save D385 Software Security and Testing...69 terms sdelbonPreview C949 Study guide into FlashCards 438 terms johnnyjordan23 Preview WGU C949 Exam Review 160 terms taniagreen03Preview

C949 O

70 terms Ma What are the 6 Characteristics of an Algorithm? Unambiguity Finiteness -finite number of steps, defined endpoint or output Well-defined inputs Effectiveness & Feasibility - doable and practicable.Language independence Well-defined outputs what are the 8 Factors of an Algorithm?Modularity Correctness Maintainability Functionality Robustness User-friendly Simplicity Extensibility What is a straightforward type of algorithm that exhaustively tries all possible solutions?Brute Force Algorithm What algorithm method breaks a problem into smaller, similar subproblems and applies itself recursively?Recursive Algorithm Which type of algorithm is used to transform data into a secure, unreadable form using cryptographic techniques?Encryption Algorithm Which type of algorithm explores potential solutions by undoing choices when they lead to an incorrect outcome?Backtracking Algorithm

Which type of algorithm is designed to find a specific target within a dataset?Searching Algorithm Which type of algorithm aims to arrange elements in a specific order?Sorting Algorithm Which type of algorithm converts data into a fixed-size hash value for rapid access in hash tables?Hashing Algorithm Which algorithm breaks a complex problem into smaller subproblems and combines their solutions?Divide and Conquer Algorithm Which type of algorithm makes locally optimal choices at each step in the hope of finding a global optimum?Greedy Algorithm Which type of algorithm stores and reuses intermediate results to enhance efficiency in solving complex problems?Dynamic Programming Algorithm Which type of algorithm utilizes randomness in its steps to achieve a solution?Randomized Algorithm What uses asymptotic notation to determine the algorithm's time and space complexity before its run?Priori analysis What is an analysis that measures the speed of an algorithm by running and timing it?Posteriori analysis What are the three main asymptotic notations in asymptotic analysis, and what do they calculate?Big O Notation - worst case Omega Notation - best case Theta Notation - average case What is merge sort's method and time complexity? Recursively divides the list into halves down to one element, then sorts as it merges them.O(n log⁡ n) for all cases.What is quick sort's method and time complexity? Partitions a section of the unsorted list into a left part and a right part, based on a chosen element within the list called the pivot.O(n log n) average, O(n^2) worst How do you determine the midpoint for quicksort? middle value - round down if list is even What is a heap sort's method and time complexity? Uses a heap data structure to repeatedly extract the maximum (or minimum) element and rebuilds the heap O(n log n) all cases What is a radix sort's method and time complexity? Places integers into buckets based on the least significant digit's value then repeating O(n) in all cases

What is a selection sort's method and time complexity? The selection sort algorithm searches the unsorted part of the array for the smallest element and swaps it to the sorted part.O(n^2) in all cases What is a insertion sort's method and time complexity? Takes an element from the unsorted part and repeatedly swaps with the element next to it until it is in the sorted part.O(n^2) in all cases apart from O(n) if already sorted What is a bubble sort's method and time complexity? Iterates through a list, comparing and swapping adjacent elements O(n^2) in all cases What is a bucket sort's method and time complexity? Distributes elements into buckets for numerical values in a specific range and sorts each bucket individually, then concatenates buckets together O(n^2) worst case, O(n) average case What is a shell sort's method and time complexity? Uses gap values to determine number of interleaved lists then sorts each list individually with a variant of the insertion sort. It finishes by performing a standard insertion sort on the entire array.O(n^2) worst case, O(n^1.5) average case, O(n log n) best case What are the main 7 Big O notations?1. O(1) - Constant Time

• O(log n) - Logarithmic Time
• O(n) - Linear Time
• O(n log n) - Log-Linear Time
• O(n^2) - Quadratic Time
• O(2^n) - Exponential Time
• O(n!) - Factorial Time

What is a data structure that stores subitems, often called fields, with a name associated with each subitem?Record What is a data structure that stores an ordered list of items, where each item is directly accessible by a positional index.Array What is a data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node?Linked List What is a data structure in which each node stores data and has up to two children, known as a left child and a right child?Binary Tree What is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array?Hash Table What is a tree data structure that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys?Max-heap

What is a tree data structure that maintains the simple property that a node's key is less than or equal to the node's childrens' keys?Min-heap What is a data structure for representing connections among items?Graph What are a set of problems for which no known efficient algorithm exists?NP-complete problems What are 3 characteristics of NP-complete problems? No efficient algorithm has been found to solve one No one has proven that an efficient algorithm to solve one is impossible.If an efficient algorithm exists for one, then all can be solved efficiently.What is the underlying structure of a tuple?dynamic array What is the underlying structure of a list?array or linked list What is the underlying structure of a dynamic array? array What is the underlying structure of a stack?linked list What is the underlying structure of a queue?linked list What is the underlying structure of a deque?linked list What is the underlying structure of a bag?hash table, array or linked list (add & remove easily) What is the underlying structure of a set?hash table or binary search tree (checks if distinct) what is the underlying structure of a priority queue? heap what is the underlying structure of a dictionary? hash table, binary search tree ADT for holding ordered data.list ADT for holding ordered data and allowing indexed access dynamic array ADT in which items are only inserted on or removed from the top stack ADT in which items are inserted at the end and removed from the front queue ADT in which items can be inserted and removed at both the front and back deque