Jaegool_'s log

NP Problems What is an "undecidable" problem in computer science? - a problem that can't be solved no matter how much time and memory is provided In computer science in terms like NP-complete or NP-hard, "NP" stands for: - non-deterministic polynomial(비결정성 다항식) True or false: Any problem that can be solved by a deterministic computer in polynomial time can also be solved by a non-deterministic c..

HeapSort Step1: Heapify O(n) Step2: n-1 deleteMax operations O(log n) = (n-1) * O(log n) total: O(n log n) advantages: Guaranteed O(n log n) Space cost of n + 1 disadvantages: Higher overhead than other n log n sorts Not a stable sort ShellSort avg: O(n(logn)^2) worst: O(n^2) inspection gap is reduced at each stage MergeSort We have two sorted lists of equal length. The length is n. What is the ..

Recursion Review what is the output of this program? #include using namespace std; int mysteryFunc(int num1,int num2) { if (num1 == 0) return num2; else return mysteryFunc(num1 / 10,num2*10+num1%10); } int main() { cout 2^2 away, nth collision -> n^2 away - Offset from the current location: currentLocation

Contents Sorting Insertion Sort Selection Sort Merge Sort Quick Sort Heap Sort Shell Sort Disjoint Set - A data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets Term: Forest Union Find Union by Size + Path Compression Union by Rank/Height Graph Topological Sort: ordering the nodes in a directed acyclic graph Shortest path: Dijkstra's..

Priority Queues could be implemented as a list, but that has efficiency issues. At least one of insertion and deletion will be O(n). Binary heaps are an alternative that offers better performance Min Binary Heap: Min binary tree + a complete tree(insert from the left child) percolate up: when inserting a smaller value in a min binary heap Constant to insert the value at the end. Must swap with a..

Progress Check 11 on Hash Tables 1. Insertion and searching in a search tree dictionary has a best case of O(log(n)) and we sometimes aren't even that lucky. What is the best search time that we can reasonably achieve in a hash table? O(1), constant time search 2. Which of the following hash functions is correct for an integer key being stored in a dictionary of size tableSize? hash(key) = key %..

Progress Check on AVL Search Trees 1. Which of the following is NOT true of Abstract Data Types (ADTs)? C a. An ADT can be implemented using a class in C++. b. ADTs describe both data and the operations on the data. c. An ADT is always specific to a particular programming language. d. Dynamic arrays and linked lists are two different ways to implement the LinearList ADT. 2. Which of the followin..

1. What are the height and depth of the J node in the tree above? height = 1, Depth: 2 2. Which of the following is NOT a leaf node? D 3. Which of the following terms best describes the relationship of G to M? Aunt HW 4. More Linked List Practice void doUnion(const list& list1, const list& list2, list& result) { list::const_iterator iter1; list::const_iterator iter2; // your code here -- make su..