CS50 Week 4

Question 1

What is the O of merge sort?

Answer 1

nlog(n)

Question 2

What is the \Omega of merge sort?

Answer 2

nlog(n)

Question 3

When the O and \Omega of an algorithm are the same, how is that denoted?

Answer 3

The algorithm’s runtime can be described as Theta(n)

n is the appropriate runtime.

Question 4

What is the pseudocode implementation of merge sort?

Answer 4

On input of n elements:
If n < 2
Return;

Else:
    Sort left half of elements;
    Sort right half of elements;
    Merge sorted halves;

Question 5

What is the tradeoff when considering merge sort?

Answer 5

You trade efficiency for speed. Specifically, more memory is required of merge sort, because a second list is needed for intermediate storage.

Question 6

Why is merge sort Theta nlog(n)?

Answer 6

The log(n) portion is the breakdown of he list into halves.

the n constant reflects merging the lists together.

Question 7

What is the basic concept of recursion?

Answer 7

Using a function to call itself using modified arguments, until a base case is reached that returns without calling itself.

Question 8

When a variable is passed to a function, what is really passed?

Answer 8

A copy of that variable.

Question 9

What is the syntax for a pointer?

Answer 9

type*

Question 10

What is the syntax for dereferencing?

Answer 10

*type

Question 11

What does dereferencing mean?

Answer 11

Go to the address stored in the pointer.

Question 12

What is the syntax for passing a memory address to a function?

Answer 12

&x

where x is the variable.

Question 13

What is the string type, as contained in the CS50 library?

Answer 13

A char*

Question 14

How are strings compared to each other?

Answer 14

strcmp()

it is in string.h

It returns 0 if two strings are identical

Question 15

What function allocates memory, and how does it work?

Answer 15

malloc(n)

malloc will allocate memory of n bytes and return the address of the first byte in memory?

Question 16

How many bytes are needed to copy a string?

Answer 16

One more than the number of characters in the string. We must allocate space for the \0.

Question 17

What is a convenient way to store a number of a given data type

Answer 17

type* pointer = malloc(n * sizeof(type))

for example:

char* pointer = malloc(6 * sizeof(char))

Question 18

What happens to memory created by malloc when the function ends?

Answer 18

Nothing, it stays around in the heap. That’s why it needs to be freed.