data structures 1

Question 1

what is a data structure?

Answer 1

Efficient mechanism to store data and provide access operations

Question 2

pros of in memory vs on disk

Answer 2

memory - faster

on disk - larger storage, non volatile

Question 3

empirical vs asymptotic analysis

Answer 3

emp - measuring resource usage of algorithm experimentally

asymp - determining bounds on resources needed as size of data increases

Question 4

best worst average case meaning?

Answer 4

best - lowest possible time
worst - highest possible time
ave - average of time cross all values for n

Question 5

what is a dominant term ?

Answer 5

term that increases the fasted in a function eg in x^2+x+3…X^2 is the dominant term

Question 6

Asymptotic function definition - what does big O notation entail/mean

Answer 6

f(x) = O(g(x))

• fx is order gx
• big O notation
• fx is bounded by multiple of gx for large x values
• |f(x)| <= M|g(x)| for all x>x0

Question 7

explain time-space trade-off

Answer 7

using additional space to make operations faster - e.g precomputing data
using slower operations to reduce space requirements

Question 8

explain time-time tradeoff

Answer 8

insertion time vs search time - extra time will be spent on one operation…which one is more valuable to the current person/role player?

Question 9

things to relearn at the end of this chapter

Answer 9

the definition of asymptotic analysis - what does M stand for?