Archives

sorted = true; for (auto i = 1; i < vec.size(); i++) { if (vec[i-1]> vec[i]) { swap(vec[i],vec[i-1]); sorted = false; } } } } { // bubble sort descending bool sorted = false; while (!sorted) { sorted = true; […]

deadline. If no such spot exists, discard it. Sorting takes O(N lg N). If we check the placement for each job by checking all the open spots less than the deadline, the algorithm is O(N2). Using the disjoint sets to […]

system is charging these particular operations as 2 for the insertion and 3 log N − 2 for the deleteMin. The total time is still the same; this is an accounting gimmick. If the number of insertions and deleteMins are […]

at most 2B leaves. Consequently, the number of black nodes on a path is at most log N. Since there can’t be two consecutive red nodes, the height is bounded by 2 log N. red black trees are AVL trees […]

CHAPTER 2 Algorithm Analysis (b) False. A counterexample is T1(N) = 2N, T2(N) = N, and f (N) = N. (c) False. A counterexample is T1(N) = N2, T2(N) = N, and f (N) = N2. (d) False. The same […]

{ Node *p , *afterp; p = before–>next; afterp = p–>next; // both p and afterp assumed not NULL p->next = afterp–> next; beforep –>next = afterp; afterp–>next = p; beforep–>next = afterp; afterp–>next = p; p->next–>prev = p; p->prev […]

CHAPTER 4 Trees 4.2 For node B: (a) A. (b) D and E. (c) C. (d) 1. (e) 3. 4.3 4. 4.4 There are N nodes. Each node has two links, so there are 2N links. Each node but the […]

was observed in the example in the text after inserting 1–8 in order followed by 16, 15, and 14. The insertions of 15 and 14 cause imbalances necessitating a double rotation. 4.25 (a) O(log log N). (b) The minimum AVL […]

(b) The caption on figure 5.56 should read Dictionary skeleton for Exercise 5.21 CHAPTER 5 Hashing 5.1 (a) On the assumption that we add collisions to the end of the list (which is the easier way if a hash table […]

(b) O(N2) (c) O(N4.1) (d) O(2N) CHAPTER 6 Priority Queues (Heaps) 6.2 6.3 The result of three deleteMins, starting with both of the heaps in Exercise 6.2, is as follows: 6.4 (a) 4N 6.5 /** * Insert item x, allowing […]

For each of the k − 1 elements a[i + 1], a[i + 2], . . . , a[i + k − 1], at most two inversions can be removed by the exchange. This gives a maximum of 2(k − […]

No Compress Union by Size 4.044 No Compress Union by Rank 3.904 Compression Random Union 7.113 Compression Union by Size 3.663 Compression Union by Rank 3.629 using namespace std; const int MAXSET= 500; const int NUM_ITERS= 1000; const int NUM_UNIONS […]

s, G, H, D, A, E, I, F, B, C, t Because a topological sort processes vertices in the same manner as a breadth-first search, it tends to produce a more natural ordering. we use a vector of indegrees Assumes […]