CPSC Assignment 3

Name: Elsie Onasanya Professor: Prof. Dr. Kamal Dahbur Course: CPSC 2100 Date: Nov 20, 2023

QUESTION # 1: Write an algorithm StackReplace that takes a stack and two items. If the first item is in the stack, replace it with the second item, leaving the rest of the stack unchanged. write an algorithm Replace that takes a stack and two items, use a temporary stack and pop everything from it and push into new stack until we encounter the first item, if we find the first item, push second item into the temporary stack. Now we need to push everything. back to the onginal stack, so again pop from temr stack and push into original stack. Pop(originalStack, item) While(item Not Equal firstltem) push(tempStack, item) pop(originalStack, item) If Not Empty(originalStack)) push(tempStack, secondltem) While(not Empty(tempStack)) Pop(tempStack, item) Push(originalStack, item) QUESTION # 2: Write an algorithm QueueReplace that takes a stack and two items. If the first item is in the stack, replace it with the second item, leaving the rest of the queue unchanged. To write an algorithm Replace that takes a queue and two items, use a temporary queue and dequeue everything from it and enqueue into new queue until we encounter the first item, if we find the first item, enqueue second item into the temporary queue. Now we need to dequeue everything back to the original queue, so again dequeue from temp queue and enqueue into original queue. Dequeue(originalQueue, item) While(item Not Equal firstitem) Enqueue(tempQueue, item) Dequeue(originalQueue, item) If(Not Empty(originalQueue)) Enqueue (tempQueue, secondltem) While(Not Empty(tempQueue)) Dequeue (tempQueue, item) Enqueue (originalQueue, item) QUESTION # 3: Using the EmployeeGraph shown below, answer the following parts of the question: a) Show the depth-first traversal from Jean to Sandler Jean, Lance, Fran, John, Susan, Sander (always taking the left-most are If there is more than one) b) Show the breadth-first traversal from Lance to Darlene Lance,Fran, John, Susan, Darlene c) Show the table that represents this graph (i.e., similar to Table 8.3 in the textbook) Brent F F F T F F T F F F Darlene F F F F F F F T F T Fran F F F F F T T F T F Fred T F F F F F F F F F Jean F F F F F F T F F T John F F F F F F F F F T Lance T F T F T F F F F F Mike F T T F F F F F F F Sander F F F F F F F F F T Susan F T T F T T F F T F Brent Darlene Fran Fred Jean John Lance Mike Sander Susan QUESTION # 4: Using the state of memory shown below, if the partitions are fixed and a new job arrives requiring 52 blocks of main memory, show memory after using each of the following partition selection approaches: a) First fit b) Best-fit c) Worst fit A. First Fit B. Best fit C. Worse fit Operating System Operating System Operating System Process 1 Process 1 Process 1 New process Empty 60 blocks Empty 60 blocks Process 2 Process 2 Process 2 Process 3 Process 3 Process 3 Empty 52 blocks New process Empty 52 blocks Empty 100 blocks Empty 100 blocks New process QUESTION # 5: Using the table of processes and service time shown below, draw a Gantt chart that shows the completion times for each process using the following CPU scheduling algorithms: