Data Structures Introduction

Question 1

Abstract Data Type (ADT)

Answer 1

special data type with defined values and operations, but the operations are hidden from the user
(isFull(). isEmpty(), insert())

Question 2

Data Structures

Answer 2

store data in an organized and efficient manner (arrays, stacks, queue, linked list, trees, hashing)

Question 3

Computational Complexity

Answer 3

Big O Notation. classifies algorithms based on time/space complexity.

O(1): constant. n is not iterated or recursed.

O(log n) logarithmic: cut time cost in half (from which floor does the crystal ball shatter? log n starts from the middle and works in halves at least)

O(n): Linear, simple for loop through size n

O(n log n): log linear, likely recursive and binary tree sorts (for every n, reduce loop time)

O(n^c): polynomial. entirety of n is looped through for every C

O(c^n): exponential time: function runs through entirety of n, multiple times, and multiple times for every c

Question 4

time vs space complexity trade-off

Answer 4

uncompressed data takes more space, but less time
look-up table: takes less time to process but costs more space to allocate table memory.

Question 5

Amortized Complexity

Answer 5

total expense per operation, over a sequence of operations in a worst-case scenario.

the standard assumption for O notation

Question 6

Efficiency vs Performance

Answer 6

But high efficiency will take less time and resources to run the program and achieve its goals.

Performance: how well a machine can handle the code. weaker systems might struggle and slow down with ‘highly efficient’ code, lacking the resources to give to the program to run efficiently.

Question 7

True or false:

2n = O(n)

2n = O( n ^ 2 )

n^2 = O(n)

n^2 = O( n * ( log n ) ^ 2)

Answer 7

True, (2n is linear time. less than or equal to n)

False, linear 2n is not quadratic

false

True

Question 8

LiLo

Answer 8

last in, last out. last entered element is processed first.

Question 9

FiFo

Answer 9

First in First out. first entered element is processed first.

Question 10

API

1 How can a user store stack elements by reference instead of by value?

2 which of the stack functions should assert? what should they assert on?

Answer 10

1 passing a pointer (value referring to the value’s location in memory)

2 destroy (check stack exists), create (element_size and num_of_elements are not 0, check stack exists) push (assert stack exists, element !< element_size, stack is not full.)