CS50: Weeks 0-5 Flashcards
What does “BIT” stand for?
BInary digiT
What does “ASCII” stand for?
American Standard Code for Information Interchange
What is an algorithm?
A set of instructions for the computer to follow.
What is pseudocode?
English “code” to represent algorithm steps.
What does CS, or the science of computation, consist of?
Inputs, algorithms, and outputs.
What is binary?
A number scale in base-2 (0,1) - 2^0 [1], 2^1 [2], 2^2 [4], 2^3 [8] …
What is an API?
Application Programming Interface
Who created ALTAIR Basic, and when?
Bill Gates, Paul Allen in 1975.
When was the BASIC language created and where?
1964 at Darmouth College
Who created the C language, and where/when?
Dennis Ritchie at AT&T Bell Labs between 1969-1973
What is a “library”?
Pre-written source code that can be “included” into other source files to use its functions.
What is a “function”?
A subroutine that performs one or many actions.
What is the standard output function in C?
printf()
What is the condition function in C?
if() {}
What are the loop functions in C?
while() {}, for() {}, and do {} while()
What is the “new line” character in C?
“\n”
How do you declare a variable in C?
= ; e.g., “string firstName = “Bryan”;
Who approved ASCII and when?
ANSI (American National Standards Institute) in 1963.
What are the first 128 characters of the ASCII set?
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)
Explain the binary search algorithm and how it is calculated.
Binary search is a log base 2 (log2) sequence.
· e.g., log n calculation: 2^7 = 128, so log2(128) = 7
What are 3 reasons to use functions?
Organization, Simplification, Reusability
What is “argv[]”?
argv[] is a dynamically created char* (string) array holding command line arguments.
What are some examples of simple but inefficient sorting algorithms?
Bubble, Selection, Insertion sorts.
What is the “core” file that sometimes exist in a program’s running directory?
A core (file) is the snapshot of the program’s memory when a error causes a “core dump”.
How does a Bubble sort work?
Start at beginning; compare two numbers at a time and swap to be in order.
How does a Selection sort work?
Find smallest element in entire set and move it to the beginning, swapping with that existing position. Then next lowest value, etc.
How does an Insertion sort work?
Start at beginning, make one pass and insert the element behind in the set where it needs to go.
What is Big O notation?
Big O (asymptotic) notation (“on the Order of…”) denotes the upper bound (worst case) running operation count.
What is Ω notation?
Ω notation denotes the lower bound (best case) measurement.
What is O(n)?
Linear.
What is O(1)?
Constant
What is O(log n)?
Logarithmic (halving something repeatedly); relies on pre-sorted set.
What is Θ (notation)?
When O() and Ω() are the same (“a program has Θ (theta)”).
What is the O scale of Bubble, Selection, and Insertion sorts?
O(n^2) - not efficient
What is the O scale of Merge Sort?
O(n log n)
What is measuring the asymptotic complexity of an algorithm?
How does the time of your algorithm increase as the size of your input grows.
What is O(n)?
O(n) = linear, operations are directly proportional to input n.
What is O(1)?
O(1) example: reading an array ceiling variable to get size of array. 1 step to do so, regardless of array size.
How is a Binary search tree used?
Used to keep a list sorted, while simultaneously allowing items to be added to the list.
What is “in order traversal”?
Print everything out on the left subtree, then the node, then the right subtree
What is a “leaf node”?
An element with no branches beneath it
What is the premise of a Selection sort?
Do a linear search to find minimum unsorted element; then swap positions between MUS and first position in list
How does a Vigenère Cipher key work?
Uses a word as a key, producing multiple Ceasar cipher keys
What are 2 major drawbacks to Ceasar Cipher?
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)
How does Bubble sort work?
Adjacent values are swapped until the array is completely sorted.
How does Selection sort work?
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.
How does Insertion sort work?
Data is divided into sorted and unsorted portions. One by one, the unsorted values are inserted into their appropriate positions in the sorted subarray.
How does Merge sort work?
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.
What is T(n)?
“the total running time of an algorithm, given an input of size n”
What is recursion?
the act of a function calling itself
What happens if a recursive function doesn’t have a base case?
it will try to run indefinitely (keep calling itself) until is uses up all stack memory.
What is GDB?
The GNU Project Debugger is a command-line tool for debugging C programs.
What does sscanf() do?
Reads an existing string and parses it (for conversions, etc.)
What are the sections of a computer’s memory, and what do they contain?
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).
What is the “return address” in a parent programs stack memory?
A return address in stack memory is the address of calling program so that the called f() will know where to return.
What is a “shell code attack”?
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.
How are linked lists implemented?
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.
What are the O and Ω search times for a linked list?
O(n) and Ω(1).
What functions are used to open/close a file?
fopen(), fclose()
What functions are used to read from a file?
fgetc(), fgets(), fread(), fseek()
What functions are used to write to a file?
fputc(), fputs(), fprintf(), fwrite()
What is Valgrind?
A command-line tool to find heap memory leaks.
What is a function?
A self-contained code segment that can be reused; used to perform repeatable actions.
What is a libary?
Pre-written source code that can be “included” into other source files to use its functions.
What are the stages of compiling source code?
1) Preprocessing (# directives), 2) Compiling (c->assembly), 3) Assembling (assembly->object code), 4) Linking (including all linked libraries to make 1 exe file).
What is the syntax for a ternary operator?
(bool expression) ? :
