UNC-CH COMP 410

Class Assignments


Assignment 1: Proofs and Runtimes (due Thurs. Sep. 6, by 11:00am, classtime)
        Do problems 1.1 and 1.7 in your text.
        Note that the "selection problem" in exercise 1.1 is given in section 1.1, p.1 of the text.

        Bring the theorem proofs to class on paper to hand in for grading. Send an email to the class account for the program. Make sure the message title contains ASSN 1 so I can sort them easily... you may send a URL to the Java source files, or you may attach them to the message. I want the source, not the .class files. Your TA will be compiling and running the code.

Assignment 2: Axiomatic Semantics (due Tues. Sep. 18, by 11:00am, classtime)
        1) Write an axiomatic semantic definition for a Bounded Queue of E (BQUE). A BQUE is created with some finite size (>0) and when an enq operation is done, if the BQUE is full then nothing changes... the item is not added to the BQUE and no items in the BQUE are removed.
        You can use the axioms we developed in class for a Bounded Stack (BST) as a model; obviously there will be some changes in the axioms, since a BQUE behaves differently from a BST. Use these signatures:
     BQUE of E

     new: pos       --> BQUE    (here, pos is int > 0)
     enq: BQUE x E  --> BQUE 
     deq: BQUE      --> BQUE
     front: BQUE    --> E
     back: BQUE     --> E
     size: BQUE     --> nat   (naturals, int >=0 )
     max: BQUE      --> pos
     empty: BQUE    --> boolean
     full: BQUE     --> boolean

        2) Write an axiomatic semantic definition of the basic LIST we studied in class. This will be similar to the axioms for STACK (and QUEUE) but a bit more complex, since LIST has operations that manipulate the inner elements as well as the ends. Use these signatures:
     LIST of E

     new:                --> LIST
     add: LIST x E x nat --> LIST   (here, nat means int >=0)
     del: LIST x nat     --> LIST
     get: LIST x nat     --> E
     size: LIST          --> nat
     empty: LIST         --> boolean

Assignment 3: Splay Tree Implementation
        due Tues. Oct 9, by class time.

Assignment 4: Topological Sort
        due Tues. Nov. 6, by class time.

Assignment 5: Graph Algorithms
        due Tues. Nov 27, 11:59 pm.




OK.