.121 10-15 Flashcards by Ellie Chapps

What is indexed retrieval?

using an identifier to store + retrieve each object/record

How well did you know this?

Not at all

Perfectly

What can be used as the identifier/key in indexed retrieval?

an unique attribute of each object (e.g. alphabetically ordering by name)

How well did you know this?

Not at all

Perfectly

Why is indexed retrieval via keys helpful?

allows us to perform binary search (objects will be sorted by the given key)

How well did you know this?

Not at all

Perfectly

How does indexed retrieval effect search efficiency?

linear search can be 26x faster if ordered alphabetically and all sections are equal
binary can be 26x faster (same as above)

worst case for both - if all objects are in 1 section (will be the usual time complexity for both algorithms)

How well did you know this?

Not at all

Perfectly

What is a problem with storing objects?

collisions

How well did you know this?

Not at all

Perfectly

Solutions to avoid collisions

indexed retrieval + chains

How well did you know this?

Not at all

Perfectly

How does indexed retrieval reduce collisions?

when inserting extra data the index array is recomputed by shifting other records to make sure there’s room for the object

How well did you know this?

Not at all

Perfectly

How does using chains reduce collisions?

if alphabetical - store all objects beginning w/ the letter in an array for that letter where each element points to the appropriate chain
chains are dynamic (use pointers) so easy to insert extra objects w/o any recomputation of indexes!!

How well did you know this?

Not at all

Perfectly

Efficiency of chains:

much faster (where objects distributed across many chains)
- same improvement as w/ using arrays

worst case - every object is in the same chain so O(N)

How well did you know this?

Not at all

Perfectly

Explain hash tables:

data struct. that converts a key to an int which becomes the index for storing the key-value pair

How well did you know this?

Not at all

Perfectly

What is the key of an element in a hash table?

the unique part/identifer

How well did you know this?

Not at all

Perfectly

How is a key turned to an index for a hash table?

hash function takes the key to generate a hash code
same deterministic function to store + retrieve
ℎ:𝑈 →{0,1,2,…,𝑚 −1} - h = hash function, U = universe of keys, m = array size

How well did you know this?

Not at all

Perfectly

What makes a hash function good?

produces a wide range of index values (helps minimise collisions)
unform hashing - each key is equally likely to map to an array location

How well did you know this?

Not at all

Perfectly

What operations are helpful for hashing?

multiplication/division = helps create a wider range of indexes
MOD - can % by array size to ensure index is within array bounds (helpful after multiplication)
logical shifts + OR operations - can replace multiplication/division for better speeds

How well did you know this?

Not at all

Perfectly

What is a key-value pair?

each element of data is associated with a unique identifier
must store both to distinguish between pairs with the same hash

How well did you know this?

Not at all

Perfectly

hash table as an ADT:

stores <k,v> pairs (where keys are unique + a handle to the associated value
put (t, <k,v>) - to store <k, v> in table t
get (t, k) - returns <k,v> if k is in t
delete (t, k)

How well did you know this?

Not at all

Perfectly

Explain rehashing:

used to make the table efficient again once chains get too long

create a new hash table at least double the current size
move all the key-value pairs over

though invisible to the ADT user, it can be an expensive operation

How well did you know this?

Not at all

Perfectly

Why are hash tables useful?

designed to be fast to work w/
- when few collisions (collisions are resolved by chaining) = O(1)

How well did you know this?

Not at all

Perfectly

Define an algorithm:

set of computational steps that transform the input → the output

How well did you know this?

Not at all

Perfectly

How can algorithms be represented?

code, flow charts, sentences, punch cards + pseudocode

How well did you know this?

Not at all

Perfectly

What is a greedy algorithm?

one that optimises for the current situation/moment without care for the best option for the future

How well did you know this?

Not at all

Perfectly

What are the complexities?

Study These Flashcards

time complexity - no. of steps relative to input size
may also be measured as actual running time (not as accurate)

space complexity - amount of memory required to run an algorithm to completion

space + time = bounded resources

What features are important when designing an algorithm?

Study These Flashcards

correct, robust, simple, and space/time complexity

What is space complexity separated into?

Study These Flashcards

fixed part - memory required to store certain data independent of the size of the problem
e.g. constants

variable part - space needed by variables so dependent on problem size
e.g. user inputted variables

What does runtime depend on (time complexity)?

input size + input organisation we look at this theoretically to avoid influence of optimal operating temp. + no. of processor cores

What is the experimental approach?

writing a program to implement the algorithm and run w/ inputs of varying size/composition + plot the results

What are the limitations of the experimental approach?

- implementing algorithm may take a long time and be very difficult - results may not be indicative for runtime on other inputs - to compare 2 algorithms must use same software + hardware

What is the better alternative to the experimental approach?

estimating actual runtime theoretically by analysing algorithms

What is a benefit of operation counting?

allows analysis of algorithm itself, independent of language (only when you ignore minor details + assume each elementary operation takes a fixed time to execute)

What are some things you'd count as an operation?

assignment, comparison, incrementing, etc. therefore 1 for = 3 operations REMEMBER iteration means some operations run n times

List the different time complexities?

constant linear logarithmic quadratic

Define constant time complexity:

time taken by the program is independent of the size of the input e.g. T(N) = 20

Define linear time complexity:

time taken by the program is directly proportional to the size of the input e.g. T(N) = 3N + 1

Define logarithmic time complexity:

time taken by the program is logarithmically proportional to the size of the input e.g. T(N) = 3log2N + 3

What is a logarithm?

opposite of to the power of what power (c) do you have to raise b by to get a ex.) 2^3 = 8, log2(8) = 3

How does a sentinel search improve a linear search?

checks if searched value is at end of array and if not places searched value there eliminates need to check if within bounds of array as value with technically always be "found"

Time complexity of sentinel vs linear search (worst case):

T(N) = 2N + 3 - sentinel T(N) = 3N + 3 - linear (both still linear time complexities!)

Time complexity of a binary search:

worst case - T(N) = C1 + C2log2N - logarithmic best case - T(N) = C1 - constant

How is growth of functions relevant to time complexity?

to be considered better an algorithm has to be scalable not just a better T(N) for one input

What time complexities are best and worst for function growth?

best = constant, logarithmic, n^fractional num, linear, n log n + quadratic worst = factorial, exponential, polynomial, cubic + n^2 log n

What is the difference between polynomial and exponential growth?

exponential = int^n polynomial = n^int (anything higher than quadratic or cubic)

What is big-O notation?

the upper boundary for the growth of a function T(n) where f(n) specifies the boundary

What does O(f(n) mean?

O = the big-O notation f(n) = function of input size n so show that T(n) is O(f(n)) means T(n) = O(n)

What do you need to find to prove T(n) = O(n)?

find ONE example where T(n) <= M*f(n) for all n >= n0 so make up numbers for M and n0

What tells us the big-O notation w/o all the maths?

picking out the dominant term from the T(N) e.g. T(N) = C1 * N + C0 dominant term = N = linear O(N)

Why if T(n) = O(n^2) does it also equal O(n^3)?

in practice we take the smallest simple function but technically is equally to anything that grows faster

What are the main time complexities in big-O notation?

constant = O(1) logarithmic = O(log N) - drop the base linear = O(N) quadratic = O(N^2)

How do you find the time complexity of nested loops?

multiply the loop's complexities together

How do you find the time complexity of non-independent loops?

can plug in values (dry run) then sum up the values + evaluate OR use the general summation rule for for loops

What is a non-independent loop?

inner loop relies on counter of outer loop e.g. for (i = 0; i < N; i++){ for (j = N; j < i; j++){ }}

What does the summation of i = 1 to N with the rule i actually equal?

(N(N+1) / 2

What does the summation of i =1 to N with the rule 1 equal?

N (incremets 1 N times so N)

What is the summation rule for for loops?

summation of i = a to b with the rule 1 b - a + 1 (increments from a to b then one additional time as much be a <= format)

.121 10-15 Flashcards

(53 cards)