C949 WGU Terminology

record

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

homogeneous data elements

linked list

data structure that stores ordered list of items in nodes, where each node stores data and has a pointer to the next node; can have multiple subitems

binary tree

A data structure that consists of nodes, with one root node at the base of the tree, and two nodes (left child and right child) extending from the root, and from each child node

can have no children, single left or right, or both right and left

hash table

data structure that stores unordered items by mapping (or hashing) each item to a location in an array

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

data structure for representing connections among items, and consists of vertices connected by edges

vertice

part of a graph the represents an item in a graph

edge

part of a graph that represents a connection between to vertices in a graph

what is an advantage of a linked list over an array?

when inserting a new item at the beginning it causes no shift to the data

ADT (Abstract data Type)

data type described by predefined user operations, such as "insert data at rear", without indication how each operation is implemented

list

ADT for holding ordered data

stack

ADT which items are only inserted on or removed from the top of a stack

LIFO

Queue

ADT in which items are inserted at the end of the queue and removed from the front of the queue

FIFO

deque ("deck")

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

Bag

ADT for stroing items in which the order does not matter and duplicate items are allowed

Set

ADT for collection of distinct items

common underlying DS: Binary search tree, hash table

Priority Queue

a queue in which the highest-priority elements are removed first; within a priority value, the earliest arrival is removed first.

common underlying DS: heap

Dictionary (map)

ADT that associates (or maps) keys with values

common underlying DS: has table, binary search tree

List, Bag

ADTs with array, linked list as common underlying DS

Stack, Queue, Deque

ADTs with linked list as their only common underlying DS

Peek

ADT operation for a queue that returns but does not remove item at the front of the queue

identity

unique identifier that describes the object

//

symbol for floored division

tuple

behaves similar to a list but is immutable -- once created the els can not be chagned

const array/list

for i in range(0)

sets i to 0 during the first iteration of the for loop, i to 1 during the second iteration, and finally i to 2 on the third iteration. The value within the parentheses is not included in the generated sequence.

range(5, -6, -1)

code for every int form 5 down to -5

range(10, 21, 2)

code for every 2nd int from 10 to 20

polymorphism

functional behavior depends on the argument types

dynamic typing

used to determine the type of objects as a program executes; Python

Static Typing

requires the programmer to define the type of every variable and every function parameter in a program's source code; C, C++

class

keyword that can be used to create a user-defined type of object containing groups of related vars and fxns

creates a new type of object

__init__

instantiation of a class automatically calls this method defined in the class def

this is also known as the constructor

memory allocation

the process of an app req and being granted memory

garbage collection

reference count is an integer count that reps how many vars ref an obj;

when an obj ref count = 0 the obj is no longer referenced and is sent here

ternary

type of operation condition ? (T)Block1: (F)Block2

assignment

type of operation for setting a var

comparison

type of operation for comparing data <, > ...

equality

type of operation == !==

short

data type

long

data type

linked allocation

A data structured contains the name, size, and starting block/cluster address of a file. A table is used to identify the address of each piece of the file.

Storage is allocated using pointers to new locations as needed.

mid-values

deque

A ______ is a "doubled-ended queue"

List

ADT that has elements of the same type so that the elements can be retrieved based on index or position

(high + low)/2

mid-values calculation for binary search. toCeil()

It is automatically available for garbage collection

What is the effect on the object regarding garbage collection?

Computing obj = new Computing(); obj = null

mutable

open to or capable of change, fickle

immutable

(adj.) not subject to change, constant

unique and immutable

Characteristics of keys in associative dictionary data type

DictName[key].remove(value)

method used to take a value out of a dictionary

Java.io.FileInputStream

Java method used to read bytes from standard file

Add(int index, Object x)

command that inserts object x at position index in a list

quick sort

recursively breaks down a problem into two or more subproblems of the same or related type

O(n^2)

Bubble sort && Insertion sort time complexity

bucket sort

Best: O(n+k)

Avg: O(n+k)

Worst: O(n^2)

Space: O(nk)

for uniformly distributed nums across a range to be sorted

bubble sort

for i from 0 to N -1

if a[i] > a[i+1]

swap(a[i], a[i +1]

end for

Bubble Sort Algorithm

def shortSort(alist):

exchanges = True

passnum = len(alist)-1

while passnum > 0 and exchanges:

exchanges = False

for i in range(passnum):

if alist[i]>alist[i+1]:

exchanges = True

temp = alist[i]

alist[i] = alist[i+1]

alist[i+1] = temp

passnum = passnum-1

Quick Sort Algorithm

int partition( void *a, int low, int high )

{

int left, right;

void *pivot_item;

pivot_item = a[low];

pivot = left = low;

right = high;

while ( left < right ) {

/ Move left while item < pivot /

while( a[left] <= pivot_item ) left++;

/ Move right while item > pivot /

while( a[right] > pivot_item ) right--;

if ( left < right ) SWAP(a,left,right);

}

/ right is final position for the pivot /

a[low] = a[right];

a[right] = pivot_item;

return right;

}

O(1)

Big-O

FindMin(x, y) {

if (x < y) {

return x

}

else {

return y

}

}

O(logn)

Big-O

BinarySearch(numbers, N, key) {

mid = 0

low = 0

high = N - 1

while (high >= low) {

mid = (high + low) / 2

if (numbers[mid] < key) {

low = mid + 1

}

else if (numbers[mid] > key) {

high = mid - 1

}

else {

return mid

}

}

return -1 // not found

}

Constant

O(5) has a _____ runtime complexity.

log-linear

o(N log N) has a ________ runtime complexity.

quadratic

O(N + N^2)

linear serach

O(N)

selection sort

O(n^2)

log_2(key)

BinarySearch number of times to find num

X is on both sides of equation

What makes a function recursive?

sorted

a list passed to binary_search needs to be...

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.

gap value

Z+ representing the distance between elements in an interleaved list; specifies the number of interleaved lists