Part (a) Write an algorithm for sorting with consideration that n data is stored in linked list. Don't make any assumption just stick to the following instructions: Each node contains an INFO field and a NEXT pointer. Start contains the address of the header node. Don't change any values in the INFO. Part (b) – Consider the given algorithm for insertion of a data at after the given location in linked list. INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM) 1. [OVERFLOW?] If AVAIL = NULL, then Write: OVERFLOW, and Exit // [Remove first node from AVAIL list] 2. Set NEW := AVAIL and 3. AVAIL := LINK[AVAIL] 4. Set INFO[NEW] := ITEM. [Copies new data into node] 5. If LOC = NULL, then: [Insert as first node] 6. Set LINK[NEW]:= START and 7. START : = NEW 8. else: [Insert after node with location LOC] Set LINK[NEW]:= LINK[LOC] and LINK[LOC] := NEW 9. 10. [End of If structure] 11. Exit Answer the following questions: (i) Draw the diagram for the simulation of the above algorithm such that your diagram reflects the updated link with different colors. Also, show the correspondence in the diagram between updated links and line number of algorithms (ii) Calculate the running time of given algorithm.

Part (a) Write an algorithm for sorting with consideration that n data is stored in linked list. Don't make any assumption just stick to the following instructions: Each node contains an INFO field and a NEXT pointer. Start contains the address of the header node. Don't change any values in the INFO. Part (b) – Consider the given algorithm for insertion of a data at after the given location in linked list. INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM) 1. [OVERFLOW?] If AVAIL = NULL, then Write: OVERFLOW, and Exit // [Remove first node from AVAIL list] 2. Set NEW := AVAIL and 3. AVAIL := LINK[AVAIL] 4. Set INFO[NEW] := ITEM. [Copies new data into node] 5. If LOC = NULL, then: [Insert as first node] 6. Set LINK[NEW]:= START and 7. START : = NEW 8. else: [Insert after node with location LOC] Set LINK[NEW]:= LINK[LOC] and LINK[LOC] := NEW 9. 10. [End of If structure] 11. Exit Answer the following questions: (i) Draw the diagram for the simulation of the above algorithm such that your diagram reflects the updated link with different colors. Also, show the correspondence in the diagram between updated links and line number of algorithms (ii) Calculate the running time of given algorithm.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Implement the algorithms in C++ program. Algorithm 1: (Traversing a Linked List) Let LIST be a linked list in memory. This algorithm traverses LIST, applying an operation PROCESS to each Node/element of the LIST. HEAD points to the first node of the LIST. Pointer variable CURR points to the node currently being processed. Step 1. Set CURR = HEAD. [Initializes pointer CURR.] Step 2. Repeat Steps 3 and 4 while CURR ≠ NULL. Step 3. Apply PROCESS to CURR -> INFO. Step 4. Set CURR = CURR -> NEXT [CURR now points to the next node.] [End of Step-2 loop.] Step 5. End Algorithm2: INSERT( ITEM) NOTE: Here it is needed that all the time, LIST should remains in the sorted order using Info part of the Node. To Insert / Enqueue a new node in the LIST, first LIST will be searched (using Info of Nodes) to find its LOCATION ( where to insert new Node). This exercise makes it possible that every new node has the probability to insert at the beginning, in the middle or at the end of LIST. CURR is…
A. A single linked list provides pointers to the next node in the sequence. Consider the below structure of the linked list and answer the questions that follow: list_head- list_tail- Assuming the front is the 1st node and the back is the Nth node, state and explain the running times for the below: i. Find a node from the front. ii. Find a node from the back. iii. Insert a node at the front. iv. Insert a node at the back. V. Erase a node from the front. vi. Erase a node from the back.
Consider a Single Linked List (SLL) of nodes, where 'node' is a type with two fields: integer data and the node type reference 'next' that refers to the next node in the list. For each part given below consider the SLL and the code given in the second column. Following the execution of the code, show the resulting list (in the answer box, for each part, use the arrow key to draw the list as: head-----> ? -------> ? -------> ?). List and Java Code | head →1-2-3→4→ null node ptr=head; node newnode = new node(0); // data=0 head = newnode; newnode.next=ptr; b head 1→2→3→4→ null node ptr=head; node newnode = new node(6); // data=6 while(ptr.next!=null) { ptr=ptr.next; } ptr.next=newode; head -1-2- 3→ 4→ mull node ptr=head; ptr=ptr.next; head=ptr;
data structure
a. Write a code for every function (e.g. insert, delete, update, create) of link list collection b. Write type of procedures and also write the difference between them
Please fast...... avoid plagiarism Explain in your own words the steps necessary to add a value to the tail of a single-ended, singly-linked list. The list should have a reference (pointer) to its head and should terminate in nullptr/NULL/none. Make sure you deal with all possible cases.
Is it possible to implement a sorted linked list using a DLL? What is the advantage of using a DLL versus a single linked list? Back up your point with a real example or application.
You are implementing two queues for the same data set, one by using array and one by using linked list. Compare the operations of insertion and deletion of the elements for time and space complexity separately.
With a single linked list START as a starting point, add the data element ITEM to the list to the right of node NODE (ITEM is to be added as the data element NODE represents' successor), Write the actions to be done and provide an illustration of the insert operation's logical representation.
Answer the given question with a proper explanation and step-by-step solution. Part 1: Implement the quickselect median algorithm Implement the median algorithm from test 1, which is called the "quickselect" algorithm (due to it's relationship to quicksort). Note, it can be used to find the i-th smallest element for any value of i, but we'll just use it to find the median (i = length/2) The algorithm uses the partition helper method (provided) to find the median. The partition method moves small elements, to the left side, and big elements to the right side. Finding the median requires moving all elements smaller than the median to the left half, and all elements greater to the right half. We can call repeatedly partition in a binary-search-like manner to quickly put the median in the right place. Implement the driver method public static int median(int[] arr) which returns the median value, and modifies the input array so all small elements are in the left half, and all big elements…
Given a singly linked list L, where x and y are two data elements that occupy the nodes NODEX and NODEY with PREVIOUSX as the node, which is the previous node of NODEX, write a pseudo-code to swap the date x and y in list L by manipulating the links only (data swapping is not allowed). Assume that x and y are available in the list and are neither neighbors nor the end nodes of list L. For example, given the list L shown in Figure P6.10(a), with L, NODEX, NODEY and PREVIOUSX marked on it, the swapping should yield the list shown in Figure P6.10(b). NODEX and NODEY are neither immediate neighbors nor the end nodes of list L. PREVIOUS X NODE X PREVIOUS X எக்க்கக்கா எத்த்தக்க (a) Before swapping g and x NODE Y NODE Y (b) After swapping g and x Linked Lists 193 NODE X Figure P6.10. Swapping of elements in a singly linked list by manipulating links
Develop a sort implementation that counts the number of different key values,then uses a symbol table to apply key-indexed counting to sort the array. (This methodis not for use when the number of different key values is large.)