WGU C949 Data Structures And Algorithms QUESTIONS AND CORRECT ANSWERS

WGU C949 Data Structures And Algorithms QUESTIONS AND CORRECT ANSWERSRecord Data structure that stores subitems, w/ names associated w/ each subitem Array Data structure that stores an ordered list of items, w/ each item directly accessible by a positional index. 00:49 01:45 Linked List Data structure that stores an ordered list as nodes, each node stores data and has a pointer to the next node. Binary Tree Data structure where each node stores data and has up to two children, left child and right child. Hash Table Data structure that stores unordered items by mapping each item to a location in an array. Max Heap Tree that maintains the simple property that a node's key is greater than or equal to a node's children key. Min Heap A tree that maintains simple property that node's key is less than or equal to the node's children key. Graph Represents connections among items. Consists of vertices and edges. Vertex represents an item on a graph. Edges represent a connection between two vertices. Abstract Data Type (ADT) Data type described by predefined user operations. Does not say anything about the implementation. List Common ADT for holding ordered data.Like an array. Can store ints, strings. Ex. nums = [5, 25, 30] Queue ADT where items are inserted at the end of the queue and removed at the front of the queue. First in first out ADT. push - inserts items at the end of the queue pop - removes and returns the item at the front of the queue. Dictionary Maps keys to values. Uses {}. The value can be number,string, or tuple. Can be any type. ex. players = { 'Lionel Messi': 10, 'Christiano Ronaldo': 7 } 00:02 01:45 If else statement Branching directs programs to execute either one group of statements or another. ex. if expression: # Statements to execute when expression is true else: # Statements to execute when expression is false # Statements here execute after the if-else. Multiple if else statements elif used when two or more branches. if age <= 15: print('Too young for car insurance.') price = 0 elif age <= 24: price = age_16_to_24 elif age <= 39: price = age_25_to_39 else: price = age_40_up Boolean Operators In python must True / False must be capitalized. Has 3 operators: and / or / not (age > 16) and (age < 25) (age > 16) or (days > 10) not (days > 10) Membership Operators not , in Cannot check for values but can check for keys. ex. my_dict = {'A': 1, 'B': 2, 'C': 3} if 'B' in my_dict: print("Found 'B'") else: print("'B' not found") # Membership operator does not check values if 3 in my_dict: print('Found 3') else: print('3 not found') reversed() Iterates over a for loop backwards. ex. print('nPrinting in reverse:') for name in reversed(names): print(name, '|', end=' ') Function Named series of statements. Invoking a function is called a function call, which causes a function to execute. Ex. def compute_square(num_to_square): return num_to_square * num_to_square Polymorphism Behavior of function depends on argument type. ex. 'x' * 5 = 'xxxxx' Global Used to change value of a global variable inside of a function. ex. employee_name = 'N/A' def get_name(): global employee_name name = input('Enter employee name:') employee_name = name get_name() print('Employee name:', employee_name) Class An instantiation operation is performed by "calling" the class, using parentheses like a function call as in my_time = Time(). An instantiation operation creates an instance, which is an individual object of the given class. An instantiation operation automatically calls the __init__ method defined in the class definition. A method is a function defined within a class. The __init__ method, commonly known as a constructor, is responsible for setting up the initial state of the new instance. In the example above, the __init__ method creates two new attributes, hours and minutes, and assigns default values of 0. ex. class Time(object): def __init__(self): = 0 es = 0 time1 = Time() = 7 es = 15 Recursive Function A function can call itself or other functions. Ex. def count_down(count): if count == 0: print('Go!') else: print(count) count_down(count-1) count_down(2) Loop over dictionaries for key in dictionary: # Loop expression # Statements to execute in the loop #Statements to execute after the loop Conditional List new_list = [expression for name in iterable if condition] Algorithm Efficiency measures algorithm complexity Computational Complexity amount of resources used by algorithm. ex runtime / memory usage. Runtime Complexity T(N) represents number of constant time operations performed by algorithm where N is input size. Has a lower bound and upper bound Space Complexity S(N) represents number of fixed-size memory units used by an algorithm for an input size N. Ex. S(N) = N + k where k is constant representing memory used for things like loop counters Auxilary Space Complexity Space complexity not included in data. ex. k Lower bound f(N) that is <= the best case of T(N), for all values N>=1 Upper bound f(N) that is >= worst case of T(N), for all values N>=1 O notation notation that provides a growth rate for an algorithm's upper bound. Ω notation notation that provides a growth rate for an algorithm's lower bound. Θ notation notation that provides a growth rate that is both an upper and lower bound Big O Notation A way of expressing the worst-case run-time of an algorithm, useful for comparing the speed of two algorithms. Binary Search Efficiency log2N + 1 ex. log2(32) + 1 = 6 Selection Sort A sort algorithm that repeatedly scans for the smallest item in the list and swaps it with the element at the current index. The index is then incremented, and the process repeats until the last two elements are sorted. Run time : O(N^2) Insertion Sort A simple sorting algorithm that builds the final sorted array (or list) one item at time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Run time : O(N^2) Difference between Selection and Insertion Sort The difference is in what the inner loop does: In selection sort, the inner loop is over the unsorted elements. Each pass selects one element, and moves it to its final location (at the current end of the sorted region). In insertion sort, each pass of the inner loop iterates over the sorted elements. Shell Sort Starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Worst Case: O(N^(3/2)) Quick Sort Unstable, O(n log n) for a good pivot,O(n^2) for a bad pivot Ω(n log n) : Uses partitioning O(n), Pick a median of 1st, middle, and last element for pivot. Random selection is also good, but expensive. Algorithm can be slow because of many function calls. Midpoint: i + (k-i)/2 def quicksort (numbers, start_index, end_index): Merge Sort Sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list. Runtime : O(N log N) i=left index i - j k = right index j+1 - k j = middle index Bucket Sort Best: O(n+k) Avg: O(n+k) Worst: O(n^2) Space: O(nk) Bucket index = floor ( number * (n-1/M) Radix Sort an O(n*k) search algorithm where K = keylength. Stable. Sorts input into bins based on the lowest digit; then combines bins in order and sorts on the next highest digit & so forth. O(d(n+b)) Bubble Sort Moving through a list repeatedly, swapping elements that are in the wrong order. O(N^2) Quick Select A selection algorithm to find the kth smallest element in an unordered list. Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side - the side with the element it is searching for. This reduces the average complexity from O(n log n) to O(n). Worst case run time O(n^2) Partition algorithm: singly linked list a data structure in which each list element