Answered step by step
Verified Expert Solution
Question
1 Approved Answer
.(and so on) c) Show the array after each iteration of the inner loop P7. Show the array, A, at the end of each iteration
.(and so on) c) Show the array after each iteration of the inner loop P7. Show the array, A, at the end of each iteration of the outer loop of selection sort. Index: 0 1 1 4 Original Array: 0 P8. Give a piece of code with nested loops that has time complexity NIgN P9. 5N3N(N) True or False? Justify your answer. P10.5NN'(N) True or False? Justify your answer. P11. Given summation: 1 + 26 + 36+ + N6 Can you solve this in terms of , or 0 ? P12. Below is the code for selection sort. There was a suggestion in class for making it stable. Based on that suggestion or your own ideas, modify this algorithm to become stable. (The modified algorithm can behave somewhat different than selection sort, but it should still place the j-th smallest element its final position, j, after the j-th iteration of the outer loop.) int i, j, temp; for -0N-1: j) int min_idxj if (A [ ] 6>3->2>the two nodes following p have data 6 and 3 and since 6 >3 the nodes will be swapped (keep in mind that you must readjust the links, not just swap the values 3 and 6). If p >32. the function will not swap: p>32. typedef struct node link; Assume the class providedstruct n representation of nodes and inks: int item; link next: a) The function does not crash (for pointer errors or otherwise). These points are only given if the program is also correct. b) Draw a picture of what happens with the links when you swap the nodes. Use line numbers (or code segments) to indicate on the picture what line of your code produces those changes. c) Write the function (Do not use anything that would bypass working with the links.) P19. Write a function int triples (int* A, int N) that takes as argument an array, A, with N integers, and returns 1 if all the numbers in A appear a multiple of three times. (That is the same number could appear 3 times or 6 times or 21 times, etc.) Otherwise it will return 0 You can assume that all the numbers in A are positive (greater or equal to 0) E.g.: both triples ([5,3,5, 3,3,5,6) and triples ([5,3,5,3,3,5,5, 5,5], 9) return 1. But triples ([3,7,3,3,7, 5) returns 0 (7 appears only twice) a) Give both the time and space complexity of your program. Justify it by referring back to specific program lines or putting comments in the program b) Give a brief but clear explanation of how your function works c) Write the code. Do all the data manipulation that is needed (if you want to use a specific algorithm, you need to write the code for it) P20. Write a function that takes the first nodes of two lists (A and B) and checks if each BAt + +Ai, where A , and B, denote the first nodes from the lists. If yes, it returns 1, else it returns 0. For A: 3->6-> 2> 5 -> 13 -1 B:3-> 9-> 11-> 16-> 29-> 30 It returns l because. Bi-Ai-3, B,-Aj+ A2 (9-3+6), , B,-Art Ayt +Ag (30-3+6+2+5+1 3+1 ) For A: 3-6-> 2 -> 5 - 13 ->1 B:3-> 9-> 15-> 16-> 29-> 30 It returns 0 because one or more nodes fail the property. In particular. Art A2+ A3 (15+3+9+2), a) Write the function. (you do not need to handle special cases). You should solve it using lists, not by copying the data in arrays and continuing to work with arrays. If you work with arrays, you lose 6 points. Assume the class provided representation of nodes typedef struct node link; struct node int item; link next; b) If your function fails or crashes for certain inputs, give those inputs and clearly indicate the line with the problem (use line numbers or write the test cases as a comment on that line of code) c) What is the complexity of your function? Justify your answer P21. Graded on correctness, little or no partial credit a) Write a function, int check(link first_node), that takes as argument the first node of a single linked list. It should return 1 0 if all the items in the list are unique and 01 otherwise (if there are repetitions). For example For 7-> 4->9->6->4->3 it returns 1 (4 is repeated) For 5-> 2->9->6->3 it returns 0 (no repetitions) For a list with only one node it returns 1 0 (no repetitions) Assume that links are implemented using the type and struct given below typedef struct node * link; struct node int item; link next; b) Give the time complexity of your function in terms of O P22. Write a function, int my_count(list L), that takes as argument a list L of integers (the item is an integer). It should count the number of consecutive repetitions of each item and print both the item and the count. A single occurrence is counted as 0. The function should also return the total number of repetitions. For example, for the list 7->2->9->9->9->9-7->7->9->3->3 it will print 7, 0 2, 0 9, 3 7, 1 9, 0 3, 1 And it will return 5. Your code should not crash Assume that list are implemented using the types and structs defined below. You should do the pointer manipulation (do not assume for example that there is a function that removes a node or one that inserts at a specific position). typedef struct node link; typedef struct struct_list list: struct node int item; link next; struct struct_list link first; int length; P23. Assume that you have an implementation of a stack object and you need to simulate a FIFO (First-In-First-Out) queue, using the stack. For simplicity, we will not declare a queue_struct. We will use as the queue a stack object. Provide the implementation of the put_in_FIFO and get_from_FIFo functions (they must have the signature shown here) using the stack's put and get functions. void put_in FIFO (stack my_queue, int data); int get_from_FIFO (stack my_queue) From the stack implementation, you only have access to the header file. In particular, you do not know the stack implementation and you do not have access to the stack_struct. You must access the stack only through the provided functions: typedef struct stack struct stack; stack newStack(int mx_sz); void push (stack s, int data) int pushpop (stack s) destroyStack (stack s) int isEmpty (stack s) int getLength (Stack s) The description and the code below are provided to help you understand the problem If a stack is accessed through the put_in_FIFO and get from_FIFO only it should behave like a FIFO queue. For example the client code below would print: 4, 1, 9, 15, 7 int main) f stack my-queue newStack (100); put_in FIFO (my_queue, 4); put_in FIFO (my_queue, 1); put-in-FIFO (my-queue, 9); int data-get_from_FIFO (my_queue)1/ data will be 4 printf("%d, ", data); put_in FIFO (my_queue, 15); put_in_FIFO (my queue, 7); // prints 4 data = get-from-FIFO (my-queue); printf("d, , data); data -get_from_FIFO (my_queue) printf("%d, ", data); data = get-from-FIFO (my-queue) ; printf("%d, ", data); dataget from FIFO (my queue); printf ("%d ", data); // prints 1 // prints 9 // prints 15 // prints 7 (5 points) Give the complexity of your functions in terms of e
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started