CS50: Weeks 0-5 Flashcards

1
Q

What does “BIT” stand for?

A

BInary digiT

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does “ASCII” stand for?

A

American Standard Code for Information Interchange

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is an algorithm?

A

A set of instructions for the computer to follow.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is pseudocode?

A

English “code” to represent algorithm steps.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What does CS, or the science of computation, consist of?

A

Inputs, algorithms, and outputs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is binary?

A

A number scale in base-2 (0,1) - 2^0 [1], 2^1 [2], 2^2 [4], 2^3 [8] …

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is an API?

A

Application Programming Interface

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Who created ALTAIR Basic, and when?

A

Bill Gates, Paul Allen in 1975.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

When was the BASIC language created and where?

A

1964 at Darmouth College

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Who created the C language, and where/when?

A

Dennis Ritchie at AT&T Bell Labs between 1969-1973

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a “library”?

A

Pre-written source code that can be “included” into other source files to use its functions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a “function”?

A

A subroutine that performs one or many actions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the standard output function in C?

A

printf()

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the condition function in C?

A

if() {}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are the loop functions in C?

A

while() {}, for() {}, and do {} while()

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the “new line” character in C?

A

“\n”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How do you declare a variable in C?

A

= ; e.g., “string firstName = “Bryan”;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Who approved ASCII and when?

A

ANSI (American National Standards Institute) in 1963.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the first 128 characters of the ASCII set?

A

0-31 = control characters (0=NULL or “\0”, termination character)
32-126 = printable characters (letters, numbers, punctuation, special)
Digits 0-9 are represented by ASCII 48-57, which when translated to binary include the binary equivalent of 0-9 prefixed by 011.
127 = DEL(ETE)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Explain the binary search algorithm and how it is calculated.

A

Binary search is a log base 2 (log2) sequence.

· e.g., log n calculation: 2^7 = 128, so log2(128) = 7

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What are 3 reasons to use functions?

A

Organization, Simplification, Reusability

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is “argv[]”?

A

argv[] is a dynamically created char* (string) array holding command line arguments.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What are some examples of simple but inefficient sorting algorithms?

A

Bubble, Selection, Insertion sorts.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the “core” file that sometimes exist in a program’s running directory?

A

A core (file) is the snapshot of the program’s memory when a error causes a “core dump”.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

How does a Bubble sort work?

A

Start at beginning; compare two numbers at a time and swap to be in order.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

How does a Selection sort work?

A

Find smallest element in entire set and move it to the beginning, swapping with that existing position. Then next lowest value, etc.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

How does an Insertion sort work?

A

Start at beginning, make one pass and insert the element behind in the set where it needs to go.

28
Q

What is Big O notation?

A

Big O (asymptotic) notation (“on the Order of…”) denotes the upper bound (worst case) running operation count.

29
Q

What is Ω notation?

A

Ω notation denotes the lower bound (best case) measurement.

30
Q

What is O(n)?

A

Linear.

31
Q

What is O(1)?

A

Constant

32
Q

What is O(log n)?

A

Logarithmic (halving something repeatedly); relies on pre-sorted set.

33
Q

What is Θ (notation)?

A

When O() and Ω() are the same (“a program has Θ (theta)”).

34
Q

What is the O scale of Bubble, Selection, and Insertion sorts?

A

O(n^2) - not efficient

35
Q

What is the O scale of Merge Sort?

A

O(n log n)

36
Q

What is measuring the asymptotic complexity of an algorithm?

A

How does the time of your algorithm increase as the size of your input grows.

37
Q

What is O(n)?

A

O(n) = linear, operations are directly proportional to input n.

38
Q

What is O(1)?

A

O(1) example: reading an array ceiling variable to get size of array. 1 step to do so, regardless of array size.

39
Q

How is a Binary search tree used?

A

Used to keep a list sorted, while simultaneously allowing items to be added to the list.

40
Q

What is “in order traversal”?

A

Print everything out on the left subtree, then the node, then the right subtree

41
Q

What is a “leaf node”?

A

An element with no branches beneath it

42
Q

What is the premise of a Selection sort?

A

Do a linear search to find minimum unsorted element; then swap positions between MUS and first position in list

43
Q

How does a Vigenère Cipher key work?

A

Uses a word as a key, producing multiple Ceasar cipher keys

44
Q

What are 2 major drawbacks to Ceasar Cipher?

A

1) Subject to frequency analysis (guessing key by seeing most repeated letter and assuming it’s a common letter, like “e”), and 2) Subject to brute force, since there are only 25 possible keys to use (not 26, since using 26 will just cycle around to result in the original unencrypted message)

45
Q

How does Bubble sort work?

A

Adjacent values are swapped until the array is completely sorted.

46
Q

How does Selection sort work?

A

Data is divided into sorted and unsorted portions. One by one, the smallest values remaining in the unsorted portion are selected and swapped over to the sorted portion of the array.

47
Q

How does Insertion sort work?

A

Data is divided into sorted and unsorted portions. One by one, the unsorted values are inserted into their appropriate positions in the sorted subarray.

48
Q

How does Merge sort work?

A

Divide an unsorted array in two and then sort the two halves of that array recursively (keep halving until each subarray is size 1). Compare first 2 items in each list; determine smaller of the two and place that element in the “final” list; repeat. Merge 2 sorted lists into a final sorted list.

49
Q

What is T(n)?

A

“the total running time of an algorithm, given an input of size n”

50
Q

What is recursion?

A

the act of a function calling itself

51
Q

What happens if a recursive function doesn’t have a base case?

A

it will try to run indefinitely (keep calling itself) until is uses up all stack memory.

52
Q

What is GDB?

A

The GNU Project Debugger is a command-line tool for debugging C programs.

53
Q

What does sscanf() do?

A

Reads an existing string and parses it (for conversions, etc.)

54
Q

What are the sections of a computer’s memory, and what do they contain?

A

A typical map of computer memory includes the text area (actual compiled program code), initialized & uninitialized data (global variables, #define constants), heap memory (variables, malloc() allocated memory), stack memory (function arguments, local variables), and environment variables (global settings of program/computer).

55
Q

What is the “return address” in a parent programs stack memory?

A

A return address in stack memory is the address of calling program so that the called f() will know where to return.

56
Q

What is a “shell code attack”?

A

A “shell code attack” is one where a buffer is overflowed intentionally to attempt to overwrite the return address in the stack so that malicious code can be run in its place.

57
Q

How are linked lists implemented?

A

Linked lists are data structures that represent a list, whereby each “node” contains 2 parts: the element value, and a pointer to the next node in the list. This is required because the list may not be allocated in contiguous blocks of memory. They are not random-accessible like an array.

58
Q

What are the O and Ω search times for a linked list?

A

O(n) and Ω(1).

59
Q

What functions are used to open/close a file?

A

fopen(), fclose()

60
Q

What functions are used to read from a file?

A

fgetc(), fgets(), fread(), fseek()

61
Q

What functions are used to write to a file?

A

fputc(), fputs(), fprintf(), fwrite()

62
Q

What is Valgrind?

A

A command-line tool to find heap memory leaks.

63
Q

What is a function?

A

A self-contained code segment that can be reused; used to perform repeatable actions.

64
Q

What is a libary?

A

Pre-written source code that can be “included” into other source files to use its functions.

65
Q

What are the stages of compiling source code?

A

1) Preprocessing (# directives), 2) Compiling (c->assembly), 3) Assembling (assembly->object code), 4) Linking (including all linked libraries to make 1 exe file).

66
Q

What is the syntax for a ternary operator?

A

(bool expression) ? :