WGU C949 - Data Structures And Algorithms Questions with 100% correct answers (scored 99.9%)

Algorithm

Describes a sequence of steps to solve a computational problem or perform a calculation.

Computational Problem

Specifies an input, a question about the input that can be answered using a computer, and the desired output.

Longest Common Substring

An algorithm that determines the longest common substring that exists in two inputs strings.

Binary Search

An efficient algorithm for searching a list. The list's elements must be sorted and directly accessible (such as an array).

Dijkstra's Shortest Path

An algorithm that determines the shortest path from a start vertex to each vertex in a graph.

NP-Complete

A set of problems for which no known efficient algorithm exists.

Polynomial time algorithm

An algorithm whose execution time grows as a polynomial of input size. An efficient algorithm is one whose runtime increases no more than polynomially with respect to the input size.

Data structure

A way of organizing, storing, and performing operations on data. Operations include accessing or updating stored data, searching for specific data, inserting new data, and removing data.

Record

A data structure that stores subitems, with a name associated with each subitem.

Array

A data structure that stores subitems, with a name associated with each subitem. May only store homogeneous data elements.

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.

Tree

A non-linear data structure that organizes data in a hierarchical way.

Heap

A complete binary tree-based data structure.

Max-heap

A tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys.

Min-heap

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.

Vertex

Represents an item in a graph.

Edge

Represents a connection between two vertices in a graph.

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.

List

An ADT for holding ordered data. Duplicate items are allowed.

Stack

An ADT in which items are only inserted on or removed from the top.

Queue

An ADT in which items are inserted at the end and removed from the front. referred to as a first-in first-out ADT.

Deque

An ADT in which items can be inserted and removed at both the front and back.

Bag

An ADT for storing items in which the order does not matter and duplicate items are allowed.

Set

An ADT for a collection of distinct items.

Priority Queue

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. Duplicates items are allowed.

Dictionary

An ADT that associates (or maps) keys with values. Can be used to describe associative relationships in Python.

Queue push

Inserts an item at the end of the queue.

Queue pop

Removes and returns the item at the front of the queue.

Queue peek

Returns but does not remove item at the front of the queue

Assignment statement

Assigns the name on the left side to reference the value on the right side.

Mutability

Indicates whether the object's value is allowed to change.

type()

A Python function that returns the class type of the argument (object) passed as parameter.

id()

A Python function that returns identity (unique integer) of an object.

name/identifier

A sequence of letters (a-z, A-Z, _) and digits (0-9), and must start with a letter. Note that "_", called an underscore, is considered to be a letter.

Reserved words

Words that have special meaning and therefore cannot be used as identifiers.

PEP 8

The Python style guide that outlines the basics of how to write Python code neatly and consistently.

floating-point literal

A number with a fractional part, even if that fraction is 0, as in 1.0, 0.0, or 99.573

Scientific notation

A floating-point literal written using an e preceding the power-of-10 exponent, as in 6.02e23 to represent 6.02x10^23. The e stands for exponent. Likewise, 0.001 is 1x10-^3 so can be written as 1.0e-3.

Overflow

Occurs when a value is too large to be stored in the memory allocated by the interpreter.

Expression

A combination of items such as variables, literals, and operators that evaluates to a value. Can be just a literal, just a variable, or some combination of variables, literals, and operators.

Literal

A specific value in code like 2 or "abc".

Operator

A symbol for a built-in language calculation like + for addition.

Modulo operator

Written as %, evaluates to the remainder of the division of the two integer operands.

String literal

A string value specified in the source code of a program.

Sequence type

A type that specifies a collection of objects ordered from left to right. A string's characters are ordered from the first letter of the string to the last.

Character index

The position of a character in a string.

len()

A Python function to find the length of a string (and any other sequence type).

any()

A Python function that returns True if any key of the dictionary is true.

Containers

Objects that contain references to other objects instead of data.

Element

An item of a list

Sequence-type functions

Built-in functions that operate on sequences like lists and strings.

Tuple

A data type behaves similar to a list but is immutable - once created the elements cannot be changed.

Numeric type

This type includes int and float which represent the most common types used to store data. These types all support the normal mathematical operations such as addition, subtraction, multiplication, and division, among others.

Mapping type

A mapping type is a data type comprised of a collection of keys and associated values. Python's only built-in mapping type is the dictionary. Dictionaries implement the associative array abstract data type.

membership operators

These operators include the in and not in operators and yield True or False if the left operand matches the value of some element in the right operand, which is always a container.

Function

A named series of statements

Block

A series of indented statements following the function definition.

duck typing

A form of dynamic typing based on the maxim "If a bird walks, swims, and quacks like a duck, then call it a duck".

local variables

Variables declared within a function or procedure and so can be accessed only by the code within that function or procedure

global variables

Variables declared in the main body of the program and so can be accessed anywhere in the code

global statement

A statement that must be used to change the value of a global variable inside of a function.

Scope

the area of code where a name is visible.

Scope resolution

The process of searching for a name in the available namespaces.

pass-by-assignment

Arguments to functions are passed by object reference

Class object

A factory that creates instance objects.

instance object

When created by the class object, this is initialized via the __init__ method.

class attribute

Defined within the scope of a class, this attribute is shared amongst all of the instances of that class

Instance attribute

This attribute is unique to each class instance and is created within a method, or from outside of the class' scope.

Clas interface

Consists of the methods that a programmer calls to create, modify, or access a class instance.

Class customization

The process of defining how a class should behave for some common operations. Such operations might include printing, accessing attributes, or how instances of that class are compared to each other.

operator overloading

This technique of Class customization can redefine the functionality of built-in operators like <, >=, +, -, and * when used with class instances.

rich comparison methods

Methods like __lt__ that can be altered using operator overloading

memory allocation

The process of an application requesting and being granted memory.

reference count

An integer counter that represents how many variables reference an object.

list object type

One of the most important and often used types in a Python program. It is a container, which is an object that groups related objects together. It is also a sequence; thus, the contained objects maintain a left-to-right positional ordering.

in-place modification

The capability of a list to grow and shrink without the program having to replace the entire list with an updated copy.

stride

An optional component of slice notation which indicates how many elements are skipped between extracted items in the source list.

list comprehension

a convenient construct that iterates over a list, modifies each element, and returns a new list consisting of the modified elements.

recursive function

A function that calls itself, either directly or indirectly.

base case

Every recursive function must have a case that returns a value without performing a recursive call.

constant time operation

An operation that, for a given processor, always operates in the same amount of time, regardless of input values.

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

A function, S(N), that represents the number of fixed-size memory units used by the algorithm for an input of size N.

Auxiliary space complexity

The space complexity not including the input data.

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. Three notations are commonly used in complexity analysis:

O - Growth rate for an algorithm's upper bound.

Ω - Growth rate for an algorithm's lower bound.

Θ - Growth rate that is both an upper and lower bound.

worst-case runtime

The runtime complexity for an input that results in the longest execution.

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.

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.

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.

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.

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.

nearly sorted

When a list only contains a few elements not in sorted order.