exam

Question 1

what does a profiler do

Answer 1

helps identify how long code takes to run
- functions that are called the most
- functions that run the longest

Question 2

what are two reasons we may use way too much data

Answer 2

1. sparse data sets
   - lots of gaps/spaces
2. high volume of data
   - should be compressed

Question 3

what can we do to optimize space?

Answer 3

• compression
• bit manip
• choose better data structures

Question 4

what is compression

Answer 4

analyzing the data to find and remove redundant or useless info

Question 5

describe two types of compression

Answer 5

lossless - does not lose any info (zip, flac)

lossy - loses some info (jpeg, mp3)

Question 6

with compression, what are we sacrificing? what are we improving?

explain.

Answer 6

we are sacrificing time to improve how much space we use.

• it takes extra time to compress, and to get the original data back
• it takes less space because compression gets rid of redundant or useless info

Question 7

your program is taking too much space. what are your options to fix this problem and what should you try first?

Answer 7

1. change data structure to something that fits the problem better
2. bit manipulation if you need to squeeze out the last few bits
3. compression

Question 8

what type of variables should be used with bit manipulation? why?

Answer 8

unsigned variables

• unsigned variables can’t be negative
  
  • overflow will be to 0
  • bit manipulation is more reliable

Question 9

what are the 3 steps to running a profiler

Answer 9

1. compile code with flag
   - gprof flag: -pg
2. run code
3. run profiler
   - gprof myCode

Question 10

what are 4 key routes to optimize your code

Answer 10

1. change algorithms
2. restructure code
3. redesign data structures
4. refactor code

Question 11

when and why should you optimize your code? When shouldn’t you?

Answer 11

only optimize if there’s a big performance issue. otherwise, the code is likely “good enough”

optimizing often makes code harder to:
- maintain
- reuse
- understand

Question 12

optimizing code often makes the code harder to: (3)

Answer 12

• maintain
• reuse
• understand

Question 13

what is the 80-20 rule and what concept does it relate to?

Answer 13

relates to optimization

80% of the program’s execution is spent in 20% of the code

Question 14

optimizing is about making our code do ______(more/less) work, not making the current work __________(faster/slower)

Answer 14

less

faster

Question 15

explain and give examples of optimizing by pre-computation

Answer 15

• pre-compute and store frequently used info in a table or variable

examples:
- constants (like PI or a BUFFER)
- the length of a string or array

Question 16

explain optimizing by data structures

Answer 16

• select data structure that best applies to the problem. are insertions frequent? searches? sorted or not?

linked list
- fast insertions

array
- fast searches
- good for sequential processing

Question 17

optimization by caching trades ____ for _____

Answer 17

trades storage for speed

Question 18

malloc allocates a number of
____________ memory locations

the compiler ________ the type on the bits

Answer 18

contiguous
- an array

overlays

Question 18

void pointers are addresses that point at ________

Answer 18

memory

Question 19

garbage collection is a form of ____________ memory management.

it attempts to reclaim _____________ which is…

Answer 19

automatic

garbage. memory occupied by objects that are no longer in use

Question 20

what does the type of a pointer actually do?

Answer 20

tells us how to interpret the data we find at the place in memory it points to

Question 21

what are three methods of garbage collection?

Answer 21

1. tracing
   - mark and sweep. recursively determine which pointers are REACHABLE and then get rid of the ones that aren’t (NULL pointers can be reachable or unreachable)
2. reference counting
   - keep track of how many references to an object are currently in use
   - 0 refs = garbage
3. escape analysis
   - compiler optimization technique
   - objects that are not accessible outside of a function can get moved to the stack where they will automatically be claimed

Question 22

when should we collect garbage?

Answer 22

asap (proactive)

only when necessary (lazy)
- not enough space

somewhere in between

Question 23

what is fragmentation? how do we solve this?

Answer 23

when space in a program is used inefficiently
- there’s spaces between memory

defragmentation is used to reorganize and store data in contiguous memory

Question 24

what is a class? what does it include?

Answer 24

- a blueprint to create objects - includes data/info and behaviour

Question 25

what is inheritance?

Answer 25

the traits a subclass gets from its parent

Question 26

what is polymorphism? what's a tool we can use in C to simulate polymorphism? examples?

Answer 26

polymorphism is an object that can take on various forms we use "union" examples: - shapes (circle, square, triangle) - a man (father, husband, employee)

Question 27

the sizeof a union is the size of _____________

Answer 27

its widest type

Question 28

what is the main difference between a union and structs? explain

Answer 28

only one property within the union can be used at a time the members of a UNION are stored at the SAME address in memory. the members of a STRUCT are stored at DIFFERENT addresses

Question 29

what is a function pointer? show how you declare and initialize one

Answer 29

a function pointer contains the address of a function int func1(int x); // function int (*func1_ptr)(int x); // declare func1_ptr = func1; // initialize notes about initialization: - no parentheses - values are populated at linking stage

Question 30

unions can be used to save ________ in structures. explain how. examples?

Answer 30

space if all the info inside a struct doesn't apply to all uses of the struct, a union can be created within the struct to handle each specific case example from slides: catalog item struct - each item has a stock number, price, and item type BUT - books would have an author and a title variable - a shirt would have colour, and size variables - a mug would have colour, but may not have size

Question 31

Unions can be used to create data structures that contain a mixture of data of different types. What can we use to differentiate between the types?

Answer 31

- a tag field example from slides: #define INT_KIND 0 #define DOUBLE_KIND 1 typedef struct { int kind; /* tag field */ union { int i; double d; } u; } Number; // assigning n.kind = INT_KIND; n.u.i = 82;

Question 32

c supports 3 forms of pointer arithmetic. what are they?

Answer 32

adding an integer to a pointer - if p points to a[i], then p + k points to a[i+k] subtracting an integer from a pointer - same thing but subtracting subtracting one pointer from another: gives distance between the two elements - if p points to a[i] and q points to a[k], then p - q is equal to i-k

Question 33

you don't have to cache Everything, what should you cache? (2)

Answer 33

- you can cache the things that are used most - cache the things that have been used recently (?)