Data Structures and Algorithms I - C949 WGU With Correct Answers.

Algorithm efficiency typically measured by the algorithm's computational complexity Computational complexity the amount of resources used by the algorithm. The most common resources considered are the runtime an ...

Algorithm efficiency typically measured by the algorithm's computational complexity Computational complexity the amount of resources used by the algorithm. The most common resources considered are the runtime and memory usage. runtime complexity a function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N Space-complexity (of an algorithm) a function, S(N), that represents the number of fixed-size memory units used by the algorithm for an input of size N. Ex: an algorithm that duplicates a list of numbers is S(N) = N + k, where k is a constant representing memory used for things like the loop counter and list pointers. auxiliary space complexity The space complexity not including the input data. Ex: An algorithm to find the maximum number in a list will have a space complexity of S(N) = N + k, but an ______ of S(N) = k, where k is a constant. Lower bound A function f(N) that is ≤ the best case T(N), for all values of N ≥ 1 Upper bound A function f(N) that is ≥ the worst case T(N), for all values of N ≥ 1 Asymptotic Notation the classification of runtime complexity that uses functions that indicate only the growth rate of a bounding function O notation a growth rate for an algorithm's upper bound Ω notation a growth rate for an algorithm's lower bound Θ notation a growth rate that is both an upper and lower bound Big O notation A mathematical way of describing how a function (running time of an algorithm) generally behaves in relation to the input size. O(N^2) A selection sort has a _____ runtime complexity O(N) A linear search has a _____ runtime complexity Constant O(5) has a _____ runtime complexity Quadratic O(N + N^2) has a _____ runtime complexity. worst-case runtime The ______ of an algorithm is the runtime complexity for an input that results in the longest execution. recursive algorithm An algorithm that breaks the problem into smaller subproblems and applies the algorithm itself to solve the smaller subproblems base case Because a problem cannot be endlessly divided into smaller subproblems, a recursive algorithm must have a _________: where a recursive algorithm completes without applying itself to a smaller subproblem. The ______ is what ensures that a recursive algorithm eventually terminates recursive function A _____ is a function that calls itself. Commonly used to implement recursive algorithms. Fibonacci sequence A numerical sequence where each term is the sum of the previous 2 terms in the sequence, except the first 2 terms, which are 0 and 1. Binary search An algorithm that searches a sorted list for a key by first comparing the key to the middle element in the list and recursively searching half of the remaining list so long as the key is not found. recurrence relation A function f(N) that is defined in terms of the same function operating on a value < N. recursion tree A visual diagram of a operations done by a recursive function, that separates operations done directly by the function and operations done by recursive calls constant time operation an operation that, for a given processor, always operates in the same amount of time, regardless of input values algorithm A sequence of steps for accomplishing a task, methodical step-by-step procedure to perform a task. Linear search a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached Sorting the process of converting a list of elements into ascending (or descending) order Selection sort A sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part. It has the advantage of being easy to code, involving one loop nested within another loop. Algorithm runtime is O(N^2) Insertion sort A sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part. typical runtime is O(N^2) Shell sort A sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm. It uses gap values to determine the number of interleaved lists. A gap value is a positive integer representing the distance between elements in an interleaved list. For each interleaved list, if an element is at index i, the next element is at index i + gap value. 26 If shell_sort() is run with an input list of size 20 and a gap values list of [15, 7, 3, 1], how many times will insertion_sort_interleaved() will be called? Quicksort A sorting algorithm that repeatedly partitions the input into low and high parts (each part unsorted), and then recursively sorts each of those parts. To partition the input, it chooses a pivot to divide the data into low and high parts. The pivot can be any value within the array being sorted, commonly the value of the middle array element. is typically O(N log N), the worst case runtime is O(N^2). Fortunately, this worst case runtime rarely occurs. Merge sort A sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list. The recursive partitioning continues until a list of 1 element is reached, as list of 1 element is already sorted. Merge sort Sorting algorithm that uses merge() and merge_sort(). Bucket sort A numerical sorting algorithm that distributes numbers into buckets, sorts each bucket with an additional sorting algorithm, and then concatenates buckets together to build the sorted result. A bucket is a container for numerical values in a specific range. Ex: All numbers in the range 0 to 50 may be stored in a bucket representing this range. This sort is designed for arrays with non-negative numbers. Radix sort A sorting algorithm designed specifically for integers. The algorithm makes use of a concept called buckets and is a type of bucket sort. The algorithm processes one digit at a time starting with the least significant digit and ending with the most significant. Two steps are needed for each digit. First, all array elements are placed into buckets based on the current digit's value. Then, the array is rebuilt by removing all elements from buckets, in order from lowest bucket to highest. fast sorting algorithm A sorting algorithm that has an average runtime complexity of O(NlogN) or better. element comparison sorting algorithm A sorting algorithm that operates on an array of elements that can be compared to each other. Ex: An array of strings can be sorted with a comparison sorting algorithm, since two strings can be compared to determine if the one string is less than, equal to, or greater than another string. (Selection sort, insertion sort, shell sort, quicksort, merge sort, and heap sort). Radix sort, in contrast, is not as it requires array elements to be numbers. sorted() A built-in Python function that takes one list argument, sorts the list's elements in ascending order using the less than (<) operator, and returns a new list with the sorted elements. sort() Python list method to do an in-place sorting of list elements in ascending order, meaning the list is modified and another list is not returned. Bubble sort A sorting algorithm that iterates through a list, comparing and swapping adjacent elements if the second element is less than the first element. It uses nested loops and as such has a runtime of O(N^2). It is often considered impractical for real-world use because many faster sorting algorithms exist. Quickselect An algorithm that selects the k^th smallest element in a list. Ex: Running quickselect on the list (15, 73, 5, 88, 9) with k = 0, returns the smallest element in the list, or 5. The best case and average runtime complexity are both O(N). In the worst case, it may sort the entire list, resulting in a runtime of O(N^2). computer program Consists of instructions that a computer executes (or runs), like multiplying numbers or printing a number to a screen. Task decomposition To reduce a complex task into simpler basic steps, making the whole task easier to solve. A computer program is generally created by _____ into simpler basic steps, and then instructing a computer to perform those steps in a certain order. computational thinking The method of evaluating a problem's most basic parts and then creating an algorithm to solve that problem is commonly known as __________. Python interpreter An application that can be used on various operating systems, including Microsoft Windows, Linux, and MacOS. interactive interpreter A program that allows the user to execute one line of code at a time. syntax error To violate a programming language's rules on how symbols can be combined to create a program. An example is putting multiple prints on the same line. runtime error Wherein a program's syntax is correct but the program attempts an impossible operation, such as dividing by zero or multiplying strings together (like 'Hello' * 'ABC'). crash Abrupt and unintended termination of a program. Integrated Development Environment (IDE) Provides a developer with a way to create a program, run the program, and debug the program all within one application. IDLE is the official Python ______. Compiler Translates a high-level language program into low-level machine instructions. Application Another word for program. Machine instruction A series of 0s and 1s, stored in memory, that tells a processor to carry out a particular operation like a multiplication. Assembly language Human-readable processor instructions; an assembler translates to machine instructions (0s and 1s). Moore's Law The observation that computing power roughly doubles every two years. The doubling of IC capacity roughly every 18 months. Clock Rate at which a processor executes instructions. Cache Relatively-small volatile storage with fastest access located on processor chip. Random Access Memory (RAM) Volatile storage with faster access usually located off processor chip. Disk Non-volatile storage with slower access. Operating System Manages programs and interfaces with peripherals. Computational Problem Specifies an input, a question about the input that can be answered using a computer, and the desired output. NP-complete ____ are problems with no practical algorithmic solutions. a A set of problems for which no known efficient algorithm exists data structure A way of organizing, storing, and performing operations on data. Operations performed on a _____ include accessing or updating stored data, searching for specific data, inserting new data, and removing data. Record The data structure that stores subitems, with a name associated with each subitem. Array A data structure that stores an ordered list of items, with each item is directly accessible by a positional index. Linked list A data structure that stores ordered list of items in nodes, where each node stores data and has a pointer to the next node. Binary tree A data structure in which each node stores data and has up to two children, known as a left child and a right child. Hash table A data structure that stores unordered items by mapping (or hashing) each item to a location in an array. Heap A max-_____ is a tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys. A min-_____ is a tree that maintains the simple property that a node's key is less than or equal to the node's childrens' keys. Graph A data structure for representing connections among items, and consists of vertices connected by edges. A vertex represents an item in a _____. An edge represents a connection between two vertices in a _____. abstract data type (ADT) A data type described by predefined user operations, such as "insert data at rear," without indicating how each operation is implemented. ______ can be implemented using different underlying data structures. However, a programmer need not have knowledge of the underlying implementation to use ________. List An ADT for holding ordered data. Items are ordered based on how items are added. Duplicate items are allowed. The order is based on how the program insert or removes items. Common underlying data structures (Array, linked list) Stack An ADT in which items are only inserted on or removed from the top of a _____. Common underlying data structures (Linked list) Queue An ADT in which items are inserted at the end of the ____ and removed from the front of the ____. first-in first-out. Common underlying data structures (Linked list) Deque An ADT in which items can be inserted and removed at both the front and back. Common underlying data structures (Linked list) Bag Items are not ordered. Duplicate items are allowed. An ADT for storing items in which the order does not matter and duplicate items are allowed. Common underlying data structures (Array, linked list) Set Items are not ordered. Duplicate items are not allowed. A _______ is an ADT for a collection of distinct items, so duplicate items are not allowed. Common underlying data structures (Binary search tree, hash table) Priority queue Items are ordered based on items' priority. Duplicate items are allowed. A ______ is an ADT where each item has a priority. Items with higher priority are closer to the front of the queue than items with lower priority, so the item's priority determines the item's position in the queue. Both duplicate items and items with the same priority are allowed. A queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority. Common underlying data structures (Heap) Dictionary (Map) n ADT that associates (or maps) keys with values. Common underlying data structures (Hash table, binary search tree) Mutability Indicates whether the object's value is allowed to change reserved words Those words are part of the language and are called _____ and thus cannot be used as a programmer-defined name. Also known as keywords. Python int Numeric type: Used for variable-width integers. Python float Numeric type: Used for floating-point numbers. Python string Sequence type: Used for text. Python list Sequence type: A mutable container with ordered elements. Python tuple Sequence type: An immutable container with ordered elements. Python dict Mapping type: A container with key-values associated elements Branching Directs a program to execute either one group of statements or another, depending on the result of an expression. range() Generates a sequence of numbers, starting at zero and ending before a value given inside the parentheses. dynamic typing Used by Pythonto determine the type of objects as a program executes. For example, the consecutive statements num = 5 and num = '7' first assign num to an integer type, and then a string type. The type of num can change, depending on the value it references. The interpreter is responsible for checking that all operations are valid as the program executes. If the function call add(5, '100') is evaluated, an error is generated when adding the string to an integer. static typing Used by many other languages like C, C++, and Java. Requires the programmer to define the type of every variable and every function parameter in a program's source code, for example String Name = "John" to declare a string variable. When the source code is compiled, the compiler attempts to detect non type-safe operations, and halts the compilation process if such an operation is found. scope resolution he process of searching for a name in the available namespaces. Namespace maps names to objects, maps the visible names in a scope to objects. Scope The area of code where a name is visible. Namespaces are used to make ______ work. locals() Returns a dictionary of the names found in the local namespace. Attribute A name following a "." symbol. Self A method parameter that refers to the class instance. Instance An instantiation of a class. __init__ A constructor method that initializes a class instance. Class A group of related variables and functions. Class object A factory for creating new class instances. Instance object Represents a single instance of a class. Instance methods Functions that are also class attributes. Instance Attribute A variable that exists in a single instance. Class attribute A variable shared with all instances of a class. recursive function A function may call other functions, including calling itself. A function that calls itself is known as _____. base case The recursive function has an if-else statement, where the if branch is the end of the recursion, known as the ________. The else part has the recursive calls. Such an if-else pattern is quite common in recursive functions. hash table a data structure that stores unordered items by mapping (or hashing) each item to a location in an array (or vector). collision Occurs when an item being inserted into a hash table maps to the same bucket as an existing item in the hash table. Chaining A collision resolution technique where each bucket has a list of items. Handles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket. The insert operation first uses the item's key to determine the bucket, and then inserts the item in that bucket's list. Searching also first determines the bucket, and then searches the bucket's list. Likewise for removes. Open addressing A collision resolution technique where collisions are resolved by looking for an empty bucket elsewhere in the table. linear probing A hash table with ______ handles a collision by starting at the key's mapped bucket, and then linearly searches subsequent buckets until an empty bucket is found. quadratic probing A hash table with ______ handles a collision by starting at the key's mapped bucket, and then quadratically searches subsequent buckets until an empty bucket is found. Double hashing An open-addressing collision resolution technique that uses 2 different hash functions to compute bucket indices. perfect hash function Maps items to buckets with no collisions. A ____ can be created if the number of items and all possible item keys are known beforehand. The runtime for insert, search, and remove is O(1). Direct Hash Function Uses the item's key as the bucket index. A hash table with a _____ is called a direct access table. Given a key, a direct access table search algorithm returns the item at index key if the bucket is not empty, and returns null (indicating item not found) if empty. Binary Tree In a _______ , each node has up to two children, known as a left child and a right child. Full A binary tree is _____ if every node contains 0 or 2 children.