CIS 120 Midterm II Algorithms and Their Limitations Complete Exam (Complete And Verified Study material) (14pages) LEARNEXAMS

1. Program Design - Queues Recall the definition of queues in OCaml as presented in class. For reference, the queue operations appear in the Appendix. type ’a qnode = { v : ’a; mutable next : ’a qnode option; } type ’a queue = { mutable head : ’a qnode option; mutable tail : ’a qnode option } Use the design process to implement a function, called join, that takes two queues and modifies them so that all of the qnodes of the second queue are moved to the end the first queue while retaining their order. For example, suppose queue q1 contains the values 1,2 and queue q2 contains the values 3,4. Then after an execution of join q1 q2, the queue q1 should contain 1,2,3,4, and q2 should be empty. The join function may assume that q1 and q2 are valid queues, generated by the standard queue operations. If q1 and q2 are aliases to the same queue, then join should have no effect. As the purpose of this function is to mutate its arguments, it should always return (). a. (0 points) The first step is to understand the problem. There is nothing to write here—your answers to the other parts will show how well you have accomplished this step. b. (3 points) The next step is to define the interface. Write the type of the operation as you might see it in a .mli file. Use a generic type. val join :