C949

record

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

array

DS that stores an ordered list of items, where each item is directly accessible by a positional index

linked list

DS that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node

binary tree

DS in which each node stores data and has up to 2 children, known as a left and right child

hash table

DS that store unordered items by mapping each to a location in array

heap

max-heap maintains node’s key >= children’s keys.
min-heap maintains node’s key<= children’s keys.

graph

DS for repr. connections among items, and consists of vertices connected by edgesver

vertex

item in a graph

edge

connection between two vertices in a graph

must be imported for python
duplicates okay
mutable
homogeous

array

head and pointer
not indexed

linked list

linear 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. sorted or unsorted

binary search

starts in middle and uses “divide and conquer“ approach

bubble sort

iterates through a list, comparing and swapping

selection sort

nested loops
runtime: O(n²)
looks for smallest number

insertion sort

add number to sorted and sort as you go
FOR and WHILE loops
runtime: O(n²)

quick sort

everything on left side has to be less than pivot card
runtime: O(n log n)

merge

split in half, take the smallest of the four and switch
runtime: O(n log n)

radix sort

numbers go into 0-9 buckets accoridng to tens digit
runtime: O(n)

records
array
hash table
binary tree
linked list
graph
heap

Basic data structures: RAHBLGH

ADT

data type with predefined user operations (behaviour of data)

list

which ADT holds ordered data and uses arrays or linked lists

dynamic arrary

which ADT holds ordered data and allows indexed access, and uses array

stack

which ADT items are removed and inserted only from top, and uses linked list

queue

which ADT items inserted at end and removed from front, uses linked list

deque

which ADT uses insertion and removal from front and back? linked list

bag

which ADT stores unordered items and duplicates, uses array and linked list

set

which ADT is a collection of distinct items, unordered, and uses BST & hash table

priority queue

which ADT puts high priority at front, uses heap

dictionary

which ADT maps keys with values, uses BST & hash table

abstraction

user interacts high-level with items, low-level things hidden

python

which language uses list, set, dict, deque

C++

which language uses vector, list, set, deque, queue, stack, map

Java

which language uses collection, list, set, map, queue, deque

compression

encodes frequently used items into bits

Huffman coding

Assigns less bits using binary tree

Heuristic

A technique that willingly accepts less accuracy to improve speed

heuristic algorithm

Quickly determines near optimal solution, speed over accuarcy

Self adjusting heuristic

Modifies DS based on how the DS is used

red-black tree and AVL tree

what are 2 self-adjusting data structures

dynamic programming

what splits problems into subproblems, then uses stored solutions larger problems

Greedy algorithm

Which algorithm solves by assuming optimal choice currently will be optimal choice over all

LIST

what gets last item popped and returns it

SET

what gets random item popped

in, not in

what tests membership

tuple

which DS is immutable (can’t add/change) and faster than list

list

which DS is most common, grows and shrinks as needed, and sortable

set

which DS is non-duplicate, faster access than list, and unordered

clear & unambiguous,
well-def inputs,
outputs,
finite-ness,
feasible,
language independent

what are 6 characteristics of an algorithm

clear and unambigous

which characteristic? algorithm should be unique in every way and lead to single conlusion

well-defined inputs

which characteristic? algorithm must indicate what output will be produced

well-defined outputs

which characteristic? algorithm must indicate what output will be produced

finit-ness

which characteristic? algorithm must be finite and not result in endless loops

feasability

which characteristic? algorithm must be simple, generic, and practical. Must be executed with only available resources, has practical hardware requirements

language independent

which characteristic? algorithm must be simple instructions in simple manner and can be implemented by any future language

priori analysis

theoretical analysis of algorithm before implementation

post analysis

practical analysis of algorithm utilizing any language to build. purpose is to determine how much time and space it takes to operate

time complexity

amount of time required to finish an algorithm’s execution known as?

space complexity

quantity of space required to solve a problem and produce an output?

time complexity

what does big O notation express?

number of steps required to complete task

what is time complexity determined by?

the asymptotic notation used to depict the temporal complexity

what is big O notation?

auxiliary space + input size

what is space complexity?

algorithm is like concept to solve problem,
programmer executes one or more task by computer

difference between algorithm and programmer

linear and binary search

2 examples of searching algorithms

recursive algorithm

which algorithm breaks a problem into minor, then calls function repeatedly

merge and quick sort

2 examples of divide and conquer algorithms

greedy algortihms

which algorithm looks for best possible solution and continues with that to final

insertion sort

which sort? from left to right, sorts and adds to the left sorted pile

O(n²)

what notation does insertion sort have?

key

value used to map to an index

hash table

which is faster for searching? Hash table or list?

bucket

name of each hash table element

hash function

what computes a bucket index from item’s key

stack

does queue or stack have LIFO?

queue

does queue or stack have FIFO?

insert on top

what does push do?

removes and returns on top

what does pop do?

inserts at END of queue

what does enque do?

removes from the front and returns number

what does dequeue do?

deque, double ended

what ADT gets items inserted and removed from both front and back

key

what is a value used to map to an index

bucket

what’s the name of each hash table array element

hash function

what computes a bucket index from item’s key

chaining

what is a collision resolution where each bucket has a list of items

open addressing

which collision resolution technique where looks for an empty bucket elsewhere in the table

linear probing

what handles collisions starting at key’s amped bucket, then finding linearly

double hashing

what uses open-addressing as a collision technique and uses 2 diff. number functions to compute bucket indicies

cryptography

name for transmitting data securely

encryption

name for alteration of data to hide og meaning

not full, complete, not perfect

full

in binary tree, what means every node has 0 or 2 children

complete

in binary tree, what means all levels, except poss. last level, contain all poss. nodes and all nodes in the last level are as far left as possible

perfect

in binary tree, what means all internal nodes have 2 children and all leaf nodes are at the same level

not full, not complete, not perfect

full, not complete, not perfect

a name that holds a value

What is a variable in a computer program?

an expression

What can be on the right side of an assignment statement?

a style guide for writing python code

What is PEP 8 in Python programming?

value, type, and identity

What are three defining properties of a Python object?