CS50 Week 4 Flashcards Preview

Programming > CS50 Week 4 > Flashcards

Flashcards in CS50 Week 4 Deck (18):
1

What is the O of merge sort?

nlog(n)

2

What is the \Omega of merge sort?

nlog(n)

3

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

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

n is the appropriate runtime.

4

What is the pseudocode implementation of merge sort?

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

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

5

What is the tradeoff when considering merge sort?

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

6

Why is merge sort Theta nlog(n)?

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

the n constant reflects merging the lists together.

7

What is the basic concept of recursion?

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

8

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

A copy of that variable.

9

What is the syntax for a pointer?

type*

10

What is the syntax for dereferencing?

*type

11

What does dereferencing mean?

Go to the address stored in the pointer.

12

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

&x

where x is the variable.

13

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

A char*

14

How are strings compared to each other?

strcmp()

it is in string.h

It returns 0 if two strings are identical

15

What function allocates memory, and how does it work?

malloc(n)

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

16

How many bytes are needed to copy a string?

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

17

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

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

for example:

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

18

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

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