UNC-CH COMP 410
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
Splay Tree Implementation
due Tues. Oct 9, by class time.
due Tues. Nov. 6, by class time.
Using the COMP SCI undergrad classes and their prerequisites as data,
create a DAG representing them... meaning draw it.
Use the classes numbered less than 600 and greater than 99 to do this.
You may ignore all prerequsites that are not COMP courses as well.
Also, if there is some "OR" prerequisite like "COMP455 requires
COMP 110 OR COMP401" then treat that like an "AND". Our goal here
is not to guide a COMP student in class-picking; the goal is to
practice the Topo Sort algorithm on a non-trivial graph.
Once you have the course graph made, generate 2 different topological
sorts for it. Do all this on paper... no need to write any code.
due Tues. Nov 27, 11:59 pm.