ASSIGNMENT 1 --- Fall 1997 SPECIFICATION AND IMPLEMENTATION OF AN ADT FOR A RESERVATION SYSTEM Implement the following abstract datatype reservation system (RS) that provides the following 7 operations. create: --> RS Sem.: starts the reservation system create-new-event: RSxEVNRxNAT -> RS Sem.: creates a new event with NAT seats with a given event-number cancel-event: RSxEVNR -> RS Sem.: cancels the event with the given number reserve-seat: RSxEVNRxSSN -> RS Sem.: reserves a seat for a person with a given ssn for a given event remove-per-res: RSxSSN -> RS Sem.: removes the all reservation of a given person get-ev-res: RSxEVNR -> set-of(SSN) Sem.: gives the set reservations for a given event, get-pers-res: RSxSSN -> set-of(EVNR) Sem.: gives the set of events, a person has reservations for. get-events: RS -> set-of(EVNR) Sem.: returns the set of the currently defined events In the above, the following types have the following meaning: EVNR are numbers between 1 and 999999999 used to identify events; eventnumbers are not necessarily consecutive. NAT represents a positive integer between 1 and 1000 that is used to specify the number of available seats for the event. SSN represents social security numbers, which are used to identify persons that made reservations for a particular event; ssn have to be numbers between 100000000 and 999999999. Moreover, your implementation should take the following additional knowledge into consideration: * No overbooking is allowed in the reservation system; reservations for full events are rejected. * A person cannot reserve more than one seat for a given event. * reservations for events that have not be defined before-hand (by using create-new-event) are rejected. * Your program has to be capable of handling at most 30 events with an average of 100 seats. * Only one instance of the abstract data type RS has to be implemented. * We recommend to use arrays to store the state of the reservation system; some ideas can be stolen from sub-section 2.3 of the textbook. Follow the following steps and guidelines when implementing the reservation system: a) Specify the semantics of all operations in natural language. b) Specify integer error-codes for exceptional situations that might occur when calling your functions (e.g. reservations for an event that has not been defined before, or reservation for an event that is full, or double reservations for a particular event). c) Implement the reservation abstract type in C. Implement all operations as integer functions that return 0 in the case the the operation worked correctly, and an integer (>0) in exceptional cases using the error-codes you designed in step B. d) Test and verify your program. e) Run your program for the benchmark program that you will obtain 5 days prior to the due date. f) Document your program. ASSIGNMENT 2 --- Fall 1997 (LINKED DATA STRUCTURES) 2) IMPLEMENTING SPARSE MATRICES WITH LISTS (last updated: Oct. 21, 2:33p) Do the problem specified at the end of chapter 4 that asks for the designing of a menu-driven implementation of sparse matices that requests using linked data structures (page 185, last problem). Additionally you can assume that all the matrices manipulated by your system are quadratic. You can use a linked data structure of your own choice to implement your sparse matrix, including those suggested by the testbook. Simple implementations will obtain at most 85% of the available points. More sophisticated implementations that implement transpose, and multiplication more efficiently will obtain the full percentage of points. Provide additional documentation for your program that specifies which data structures you used by your implementation; moreover, take 2 examples matrices and depict how they are stored using the data structures you described in the first part of your documentation. If you claim your implementation is more efficent, additionally explain why your implementation is more efficient (for multiplication and/or transpose) than a simple single linked list implementation; also briefly discuss the storage overhead of your implementation, as well as the runtime overhead of your implementation with respect to other operations. You can make following assumptions: 1. The dimensions of matrices are fixed(nxn; n<=5) during every run-time session, and is inquired at the beginning of each program run. 2. Matrices are identified by names. Matrix's name could be alphabet, digit, or combination, and the length is less than 5. 3. There are at most 5 matrices defined during the session; if somebody tries to define a sixth matrix an error message is given. 4. Matrices can be erased to make space to define new matrices; in this case, the heap storage that is occupied by the matrix has to be released. 5. Matrices generated as results of addition, subtraction, multiplication, and transpose are printed out, but are not saved permanently. Your implementation should create a result matrix, print it out, and delete the result matrix using the erase-function (alternatively, you could have a special variable out that permanently stores the result of a computation; in this case the old contents of out has to be erased prior to generated the new matrix). Programs that just print out the result of operations without creating a result matrix will be penalized by subtracting 7% of the available points. Here is an example of possible program execution scenarios: > Enter the size of spares matrix (cannot be changed): 3 > (a) reads in a sparse matrix > (b) writes out a sparse matrix > (c) erases a sparse matrix > (d) adds two sparse matrices > (e) substracts two sparse matrices > (f) multiplies two sparse matrices > (g) transposes a sparse matrix > (h) quit > Make your choice: a > What's the name of the (3x3) matrix: m1 > row(1): 0 2 0 > row(2): 1 0 0 > row(3): 0 0 3 > (a) reads in a sparse matrix > (b) writes out a sparse matrix > (c) erases a sparse matrix > (d) adds two sparse matrices > (e) substracts two sparse matrices > (f) multiplees two sparse matrices > (g) transposes a sparse matrix > (h) quit > Make your choice: b > What's the name of the (3x3) matrix: m1 matrix(m1) = 0 2 0 1 0 0 0 0 3 > (a) reads in a sparse matrix > (b) writes out a sparse matrix > (c) erases a sparse matrix > (d) adds two sparse matrices > (e) substracts two sparse matrices > (f) multiples two sparse matrices > (g) transposes a sparse matrix > (h) quit > Make your choice: a > What's the name of the (3x3) matrix: m2 > row(1): 0 0 12 > row(2): 13 0 0 > row(3): 0 11 0 > (a) reads in a sparse matrix > (b) writes out a sparse matrix > (c) erases a sparse matrix > (d) adds two sparse matrices > (e) substracts two sparse matrices > (f) multiples two sparse matrices > (g) transposes a sparse matrix > (h) quit > Make your choice: d > What are the two matrices: m1 m2 matrix(m1+m2) = 0 2 12 14 0 0 0 11 3 > (a) reads in a sparse matrix > (b) writes out a sparse matrix > (c) erases a sparse matrix > (d) adds two sparse matrices > (e) substracts two sparse matrices > (f) multiples two sparse matrices > (g) transposes a sparse matrix > (h) quit > Make your choice: g > What's the name of the (3x3) matrix: m2 matrix(T(m2)) = 0 13 0 0 0 11 12 0 0 > (a) reads in a sparse matrix > (b) writes out a sparse matrix > (c) erases a sparse matrix > (d) adds two sparse matrices > (e) substracts two sparse matrices > (f) multiples two sparse matrices > (g) transposes a sparse matrix > (h) quit > Make your choice: c > What's the name of the (3x3) matrix: m1 > (a) reads in a sparse matrix > (b) writes out a sparse matrix > (c) erases a sparse matrix > (d) adds two sparse matrices > (e) substracts two sparse matrices > (f) multiples two sparse matrices > (g) transposes a sparse matrix > (h) quit > Make your choice: b > What's the name of the (3x3) matrix: m1 Error: matrix(m1) doesn't exist! > (a) reads in a sparse matrix > (b) writes out a sparse matrix > (c) erases a sparse matrix > (d) adds two sparse matrices > (e) substracts two sparse matrices > (f) multiples two sparse matrices > (g) transposes a sparse matrix > (h) quit > Make your choice: h ASSIGNMENT 3 FALL 1997 (last updated: Oct. 30, 11a) 3) TREE SWAPPING Write a C-function swap-tree that takes a binary search tree and swaps the left and right children of every node (see Fig. 5.20 in the textbook) of the tree. 4) REMOVAL OF RECURSION Transform the copy-function on page 207 of the textbook into an iterative function (Hint: use a stack to simulate recursion!) that does not have any recursion. 4a) (tougher problem, can be done in place of problem 4) -- 25\% extra credit. Write an iterative version of postorder traversal. 5) AVERAGE NUMBER OF ACCESSES Write a C-function avg\_acc that computes the average number of nodes that have to be accessed for finding a key in a given binary search tree. Interpret the results you obtained for the 3 sample trees given below, by comparing the results of calling your program for the tree with the theoretical predictions given in class. If your "practical" results are different from the "theoretical" predictions try to explain why they differ! Testing: Test you programs for three binary search trees that have been created by inserting the keys, listed below, in the indicated order: a) 5 1 2 3 4 91 98 97 96 41 40 39 36 34 35 66 9 8 7 6 b) 5 21 92 13 64 91 98 97 96 41 40 39 36 34 35 66 9 8 7 6 c) 96 97 41 40 39 36 34 35 66 9 8 7 6 5 1 2 3 4 91 98 In the case of problems 3 and 4, first print the keys of the original tree in preorder, and then print the keys of the copied and swapped tree in preorder. ASSIGNMENT 4 FALL 1997 (updated: Nov. 24, 2p) 6) COMPLEXITY ANALYSIS a) Give the run-time complexity of the following C program segment (with n being the complexity parameter of the program). i=1; while (i