Show:
C Basics
Algorithm
Data Structures
Memory Management
Wild Card
100
If global variables are accessible by all functions anyway, why not declare all variables as global rather than use local variables at all?
Using only global variables increases the risk that some functions might change their values unbeknownst to other functions. It’s particularly risky to reuse (popular) symbols (e.g., i). Using only global variables also tends to make code less readable if variables' declarations are no longer proximal to lines of code that utilize those variables.
100
How many times must you tear a 1,024- page phonebook in half in order to whittle it down to a single page?
10
100
True or False: A stack is a first-in, first-out data structure.
FALSE. Stack is FILO; Queue is FIFO.
100
What are 2 ways to trigger a segmentation fault?
You can trigger a segfault by indexing into an array far beyond its bounds, by dereferencing an invalid (e.g., garbage or NULL) pointer, and even by calling a function recursively too many times (the result of which is that the stack overruns the heap).
100
Convert the binary number below to decimal: 10100111001
1337
200
Consider the program below. #include int main(void) { printf("%.1f\n", 1 / 10); } When compiled and executed, this program outputs 0.0 even though 1 / 10 is surely 0.1! Why is this program outputting 0.0?
Because 1 and 10 are both of type int, the expression 1 / 10 evaluates to an int as well, in which case everything after the decimal is discarded, and so 0.1 becomes 0, which is then formatted by printf as 0.0.
200
Out of insertion sort, bubble sort, selection sort and merge sort, which algorithm gives the slowest running time in the best case and which algorithm gives the slowest running time in the worst case?
In the best case: Selection sort gives slowest running time; Worst case: all insertion sort, bubble sort, selection sort (n*(n-1)/2)
200
What is one property of a good hash function?
Uniformly distributing some (possibly non-uniform) domain over a range.
200
Consider the two lines of code below. // first line int grades[9]; // second line int *grades = malloc(sizeof(int) * 9); (a) Compare the two lines of code in a sentence: how are they similar? (b) Contrast the two lines of code in a sentence: how are they different?
(a) Both lines allocate an array of 9 `int`s (whose size totals, on a 32-bit machine, 36 bytes). (b) Whereas the first line allocates the array on the stack, the second line allocates the array on the heap; the second line additionally allocates 32 bits (on a 32-bit machine) for a pointer called grades. (In the first line, grades is just a "symbol" that consumes no space.)
200
Suppose that valgrind reports the error below when run on Cansu’s code. Explain in a sentence what David has probably done. Invalid write of size 4
David has likely written to a 4-byte location in memory that does not belong to his program, as by indexing beyond the boundary of an array of `int`s.
300
Suppose that Doug sees the warning below when he tries to compile his code. implicit declaration of function 'printf' Explain what the problem must be and how Doug can fix it.
Doug has forgotten #include atop his code. Inserting that line should resolve.
300
Consider the pseudocode for Bubble Sort below. [Repeat n times: For each element i: If element i and its neighbor are out of order: Swap them.] Why is this implementation of Bubble Sort in best case n^2? In a sentence or more, explain (in English or pseudocode) how you could alter this implementation so that it is instead best case n.
Even if its input is already sorted, this implementation iterates over n elements n times, for a total of n * n = n2 steps. If we instead check, at the end of each iteration of the outer loop, whether or not we actually swapped any neighbors, breaking out of that loop if not, we can keep our running time in best case n.
300
Suppose that a hash table for (entirely alphabetical) English words is implemented as an array with 26 separate chains. Even with an optimal hash function that uniformly distributes words over the 26 chains, searching a hash table is in O(n/26), which is equivalent to O(n) since 26 is a constant. And so a hash table’s efficiency seems no better than one big linked list. In a sentence or two, why bother using a hash table at all, then, for English words?
Even though searching a hash table and searching a linked list might be asymptotically equivalent, the fact remains that, in the real world, the former might very well take 1/26 as much time as the latter, a difference that humans might certainly notice and appreciate.
300
Consider the lines of code below, where string and GetString are defined as in CS50’s library. (Recall that string and char * are synonymous.) string s1 = GetString(); string s2 = s1; s2[0] = toupper(s2[0]); Why, in a sentence or more, does the last line above capitalize both s1 and s2, even though s2 is a copy of s1?
Because s2 equals s1, it, as a pointer to a char, merely points to the same char in memory as does s1. Accordingly, s1[0] and s2[0] represent the same char in memory. Capitalizing one thus capitalizes the other.
300
Consider the function below. int foobar(int n) { if (n < 2) return 1; else return (n * foobar(n-1)); } (a) Assuming it is called with some non-negative`n`, what mathematical function does foobar compute? (b) In a sentence or more, explain why, for sufficiently large non-negative n, foobar actually returns negative values. (c) In a sentence or more, why might foobar sometimes segfault?
(a) Factorial (b) For sufficiently large non-negative n, the function suffers from overflow, as n! exceeds INT_MAX. (c) For sufficiently large non-negative n, foobar is recursively called so many times that the calls' frames overrun the available stack space.
400
Suppose that you’re a TF and a student comes up to you at office hours. The student explains that GCC is spitting out the message below. control reaches end of non-void function In one or more sentences, explain to this student (well, us) what this warning means with respect to the student’s code.
In some (or all) cases, the student’s function doesn’t actually return a value (e.g., the student left out a return statement altogether), even though its return type is not void.
400
For each algorithm below, specify an upper (O) and lower (Ω) bound on its running time. Assume that the linked lists and arrays in question are all of length n. 1) insert in a sorted singly-linked list 2) search in a sorted singly-linked list 3) sort a sorted array with Selection Sort 4) sort an unsorted array with Merge Sort
1) n, 1 2) n, 1 3) n^2, n^2 4) nlogn, nlogn
400
Consider the remarks below, each of which sounds like an advantage but is not without an underlying disadvantage too. Complete each of the remarks, making clear the price paid (i.e., tradeoff) for the advantage. (a) Merge sort tends to be faster than bubble sort. Having said that…​ (b) A linked list can grow and shrink to fit as many elements as needed. Having said that…​ (c) Binary search tends to be faster than linear search. Having said that…​
(a) Having said that, merge sort requires twice as much space (to store values while merging). (b) Having said that, a linked list does not allow for binary search, even if sorted, since it doesn’t support direct access to nodes by index. (c) Having said that, binary search requires that its input be sorted, which might not be the case (and sorting it would require additional time).
400
With respect to memory management, how is the heap different from the stack?
Memory allocated on the heap (via malloc) persists (i.e., belongs to a program) until it is explicitly freed (via free), whereas memory allocated on the stack (in the form of functions' local variables) persists only until the function for which the memory was allocated returns.
400
Write a function to reverse a string and store the reverse in that string? Bonus: Tell us how you would do that in place? how you would reverse a string if you don't need to store it? *You can use strcpy*
What is int reverse(char* s) { int len = strlen(s) + 1; char* temp = malloc(sizeof(char) * len); if (temp == NULL) return 1; for (int i = 0; i < len; i++) { temp[i] = s[len - i]; } temp[len] = '\0'; strcpy(temp, s); free(temp); return 0; } int reverseinplace(char* s) { int len = strlen(s); int mid = (len - 1)/2; for (int i = 0; i < mid; i++) { int temp = s[i]; s[i] = s[n - i]; s[n - i] = temp; } return 0; }
500
Even though 232 is 4,294,967,296, the largest value that a 32-bit int can represent is only 2,147,483,647. Why?
Because an int is, by default, signed, it’s intended to represent negative and positive numbers alike. While half of its range is allocated toward non-negative numbers (0 through 231 - 1), the rest is reserved for negative numbers
500
(a) When some algorithm could be implemented in code either iteratively or recursively, why might you want to implement it recursively? (b) When some algorithm could be implemented in code either iteratively or recursively, why might you want to implement it iteratively?
(a) Some algorithms are, by their own definition, recursive (e.g, Merge Sort), in which case it’s straightforward (and thus convenient) to implement them in code recursively. An iterative implementation, by contrast, might take more time to write and might even prove less readable. (b) Recursive implementations of algorithms tend to consume more memory than necessary if recursive calls' frames pile up on the stack (without being optimized away by a compiler). They are also vulnerable to stack overflow if more recursive calls are made than can even fit on the stack. In such cases, an iterative implementation might prove more memory-efficient and more capable of handling large inputs.
500
Recall that a tree is a data structure in which each node has some value along with zero or more children. A binary tree, meanwhile, is a tree in which each node has at most two children. A binary search tree, finally, is a binary tree, the value of whose root is (1) greater than that of its left child, if any, and any descendants thereof and (2) less than that of its right child, if any, and any descendants thereof. Moreover, each child is itself the root of a binary search tree. To be clear, a binary search tree is necessarily a binary tree, but a binary tree is not necessarily a binary search tree. For simplicity, assume that trees' values are integers and that trees may not contain duplicate values. Suppose that a C function called find is supposed to return true if any node in a binary tree contains a particular value, else it is supposed to return false. Complete the below definition of find, based on your definition of node. Do not assume that tree is non-NULL or that tree is a binary search tree. bool find(node *tree, int n) {
bool find(node *tree, int n) { if (tree == NULL) return false; else if (tree->n == n) return true; else if (find(tree->left, n)) return true; else if (find(tree->right, n)) return true; else return false; }
500
Recall that, to use any of the C550 Library’s functions, you not only need to put #include atop your code, you also need to pass the -lcs5 flag to gcc when compiling, which might feel redundant. But this #include and this -lcs50 play different roles in the process of compilation. In two sentences, what role does each play?
Whereas the #include (a pre-processor directive) informs gcc that a program might call functions declared in cs50.h the -1cs50 (a linker flag) tells gcc to incorporate the bits that result from compiling cs50.c (wherever they are) into the program.
500
Generate the Huffman encoding free for the following text: "abbcccccccddeeeefghhhii"
(See white board)