Jeopardy Study Night

101/151/183

100

What's the difference between a for-loop, a while-loop, and do-while loop?

What is Loop a set number of times, loop while true, loop at least once.

200

What's the difference between pass-by-value and pass-by-reference? Give examples.

What is Pass-by-value creates a copy of the variable, pass-by-reference uses the actual variable.

300

Can a while-loop and a for-loop be used interchangeably?

What is Yes.

400

What can access private member variable within a class?

What is Only the class member functions.

500

Say you have an ifstream named fin. How would you open a file, close a file, and check if the file is good?

What is fin.open("filename"); fin.close("filename"); if (!fin) { //do something } -or- while(fin.good());

203

100

Outline the steps for a proof by induction.

What is Base Case: prove the statement is true for some value n. Inductive Hypothesis: assume that the statement holds for some value k. Inductive Step: Prove that the statement holds for k + 1 using the inductive hypothesis.

200

How do you determine whether a directed graph is strongly or weakly connected?

What is A directed graph is strongly connected if there is a path from vertex a to b and vertex b to a for all verticies. A directed graph is weakly connected if its underlying undirected graph is connected (you could reach any vertex from a given vertex.)

300

What are the differences between strong and weak induction?

What is The difference appears in induction hypothesis. In weak induction, we only assume that particular statement holds at k-th step, while in strong induction, we assume that the particular statment holds at all the steps from the base case to k-th step.

400

For each scenario, decide whether a permutation or combination is appropriate: a) Solving a combination lock, b) How many different colors of marbles are in a bag, c) How many different ways you can knock in 3 pool balls (out of 16), d) What ingredients you use to make yourself a sandwich

What is a) permutation, b) combination, c) permutation, d) combination

500

For the following relations, drawn the correct graph represenation and determine whether they are reflexive, symmetric, antisymmertric, and/or transitive. 1.) For the set T = { {a,b}, {a}, {b}, {a,b,c} } R is the relation xRy if X ⊆ Y where X and Y are elements of T. 2.) For the set S = {5, 6, 7, 8, 9, 10} let R be the relation defined on S by the condition such that for all x, y ∈ S, xRy if (x + y) is a multiple of 3.

What is First Graph: Reflexive, Transitive, and Antisymmetric Second Graph: Symmetric

280

100

Where are local variables stored in memory?

What is Stack

200

What component does a node of a doubly-linked list contain that a singly-linked list doesn't?

What is A pointer to the previous node.

300

What is the importance of separating interface from implementation? Give an example.

What is Separating interface from implementation is what allows programmers to write code that does the same thing in different ways without worrying about the interface. An example is an abstract class.

400

What are the differences between deep copy and shallow copy?

What is A deep copy copies all fields, and makes copies of dynamically allocated memory pointed to by the fields. Changing the values of the deep copy will not affect the original values. A shallow copy references the original data, so if the value of the shallow copy changes, so will the original data.

500

What is the difference between overloading and overriding?

What is Overloading is when you re-write a function in a derrived class with additional function argumnents. Overriding is when you re-write a function with the same number of arguments, but change what the function does.

281

100

Rate the complexities of O(n^2), O(nlogn), O(logn), O(1), O(n!), O(n).

What is Least -> Most: O(1), O(logn), O(n), O(nlogn), O(n^2), O(n!).

200

What is merge sort and its complexities?

What is Divide and conquer! Split a list into the smallest unit and compare adjacent groups, merging them back together in sorted order. Avg. and worst case O(nlogn).

300

What is quick sort and its complexities?

What is Divide and conquer! Pick a pivot in the list. All elements less than pivot go before the pivot and same for elements greater. Recursively do that to the sub-lists.

400

When is Prim's alg. better and when is Kruskal's alg. better?

What is Prim's is better for a dense graph with lots of edges, else Kruskal's is better.

500

When can you not use the master theorem?

What is T(n) not monotonic, f(n) not polynomial, b not constant.

Advanced Classes

100

What goes in a stack and what goes in a heap?

What is Stack is used for static memory allocation and heap for dynamic memory allocation.

200

What are the types of cache misses and what do they mean?

What is Compulsory (first reference), Conflict (several blocks mapped to same spot), Capacity (cache ran out of room)

300

What are the differences between NP, NP-Hard, and NP-Complete?

What is NP is the set of all decision problems that can be solved to yes can be verified in poly time. NP-Complete is the set of all problems X in NP for which it is possible to reduce other NP problem Y to X in poly time (if know how to solve Y, can solve X) (ie. 3SAT). A problem is NP-Complete if it is NP and NP-Hard. NP-Hard problems are at least as hard as NP-Complete problems, but do not have to be in NP nor decision problems. Problem X is NP-Hard if there is an NP-Complete problem Y such that Y can be reduced to X in poly time (ie. halting problem).

400

What is the importance of separating interface from implementation? Give an example.

What is Separating interface from implementation is what allows programmers to write code that does the same thing in different ways without worrying about the interface. An example is an abstract class.

500

Design a 3-level hierarchical page table. Physical memory is with 8KB (byte-addressable); virtual memory addresses are 17-bits long. A page is 32 bytes and each page table entry is 2 bytes. The superpage table and each of the 2nd level page tables require precisely one page of storage. Determine the bit positions for a virtual address and a physical address.

What is VIRTUAL: super-page table (16-13), 2nd level page table (12-9), 3rd level page table (8-5), page offset (4-0). PHYSICAL: physical page number (12-5), page offset (4-0)