EECS3311 Fall 2020
Lab Exercise 1
Implementing and Specifying a Balanced Search Tree
Chen-Wei Wang and Jinho Hwang
Released Date: Monday, September 14
Due Date (Sections A & E): 11:59pm (EST), Sunday, September 27
– Check the Amendments section of this document regularly
for changes, fixes, and clarifications.
– Ask questions on the course forum on the eClass site for Sections A and E.
Never share code on the course forum.
Policies
– Your (submitted or un-submitted) solution to this lab exercise (which is not revealed to the public)
remains the property of the EECS department. Do not distribute or share your code in any public
media (e.g., a non-private Github repository) in any way, shape, or form. The department reserves
the right to take necessary actions upon found violations of this policy.
• You are required to work on your own for this lab. No group partners are allowed.
• When you submit your lab, you claim that it is solely your work. Therefore, it is considered as an
violation of academic integrity if you copy or share any parts of your Eiffel code during any stages of
your development.
• When assessing your submission, the instructor and TA will examine your code, and suspicious submissions
will be reported to the department/faculty if necessary. We do not tolerate academic dishonesty, so
please obey this policy strictly.
– You are entirely responsible for making your submission in time.
• You are encouraged to submit multiple times prior to the deadline: only the last submission before the
deadline will be graded.
• Practice submitting your project early even before it is in its final form.
• No excuses will be accepted for failing to submit shortly before the deadline.
• Back up your work periodically, so as to minimize the damage should any sort of computer failures occur.
Follow this tutorial series on setting up a private Github repository for your Eiffel projects.
• The deadline is strict with no excuses: you receive 0 for not making your electronic submission in time.
• Emailing your solutions, or links to a cloud drive, to the instruction or TAs will not be
accepted.
– You are free to work on this lab on your own machine(s), but you are responsible for testing your code at a
remote Prims lab machine before the submission.
1
Contents
1 Learning Outcomes of this Lab Exercise 3
2 Background Readings 3
3 An Important Syntax to Note 3
4 Problem 4
4.1 Representing a Binary Tree (BT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.2 Binary Search Tree (BST) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.3 Splay Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.4 Perfomring a Rotation on a Tree Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.5 Performing a Splay Operation on a Tree Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.6 Self-Adjustment of a Splay Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.7 Useful Web Tool for Visualizing Splay Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 (Optional) Tutorials on Tree Nodes and Splay Trees 9
5.1 Test Environment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.2 Starter Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.3 Intermediate & Advanced Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6 Getting Started 10
6.1 Work Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2 What if You Get Stuck? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.3 How to Read the Given Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
7 Grading Scheme 13
8 Submission 14
9 Amendments 15
2
1 Learning Outcomes of this Lab Exercise
1. Implement functionalities of a tree node and a self-adjusting splay tree.
2. Specify contracts (preconditions and postconditions) for the implemented functionalities.
3. Practice Test-Driven Development (TDD):
– Write unit tests (using the ESpec library) as soon as a unit of functionality becomes executable.
– Accumulate a suite of test classes (each of which containing test cases) for regression testing.
– Use the debugging tool in EStudio IDE when failing tests.
– Add more test until all the normal scenarios (where actual outputs of your programs match the expected
outputs) and the abnormal scenarios (where contract violations are expected) are tested in your developed
test suite.
2 Background Readings
– Introductory tutorial videos from Lab0:
https://www.youtube.com/playlist?list=PL5dxAmCmjv_4bxISJrwPoBrzVdCfVgVnN
– Lecture Materials (and relevant parts of the lecture recordings) from W1 and W2 on:
• DbC
• TDD
• Copying Objects
• Writing Complete Postconditions
3 An Important Syntax to Note
– In the introductory tutorial, you learn about how to make use of a detachable value in context of the implementation
(i.e., within the do block):
check attached bb.get_detachable_birthday("yuna") as yuna_bd then
Result := yuna_bd.month = 5 and yuna_bd.day = 19
end
where attached bb.get_detachable_birthday("yuna") as yuna_bd is a Boolean expression: it evaluates to true if the return
value is not void (in which case a new local variable yuna bd is introduced for use); otherwise, it evaluates to
false if the return value is void.
Q. The above fragment of code appears in the context of implementation. But what if you want to manipulate
a detachable value in the context of a contract (which requires a Boolean expression)?
A. You can write something like:
...
ensure
yuna_birthday:
attached bb.get_detachable_birthday("yuna") as yuna_bd
and then
yuna_bd.month = 5 and yuna_bd.day = 19
where and then is a logical conjunction with the runtime short-circuit effect (i.e., same as && in Java): when
evaluating b1 and then b2, the evaluation of expression b2 is only necessary if b1 evaluates to true.
The left conjunct attached bb.get_detachable_birthday("yuna") as yuna_bd is as explained above, which introduces the
new local variable yuna bd. The right conjunct, then, makes use of that new variable yuna bd if the left conjunct
evaluates to true.
3
4 Problem
This section provides the necessary background knowledge required for you to complete Lab1. Section 4.1 and Sec-
tion 4.2 cover topics which you have learned in EECS2011.
4.1 Representing a Binary Tree (BT)
– A tree is an acyclic graph an originating node (with no incoming edges): the root. A binary tree is a tree where
each node has at most two child nodes (via up to two outgoing edges): the so-called left child and right child
nodes.
– A tree node is represented by the TREE NODE class with the following declaration:
TREE NODE[K -> COMPARABLE, V -> ANY]
The two variables K and V above are called type parameters (K for search keys and V for data values). A client
or user of the TREE NODE class must specify what K and V are when declaring a variable. As an example, by
writing node 1: TREE NODE[INTEGER, PERSON] , the stored keys are integers and values are references of person
objects. As another example, by writing node 2: TREE NODE[STRING, REAL] , the stored keys are references
of string objects and values are single point float values.
That is, the type of a node key or a node value may either be a reference type (e.g., STRING, PERSON) whose
default value is void, or a primitive type (e.g., INTEGER, REAL, BOOLEAN) whose default value is standard.
A tree node is implemented by having five detachable attributes (i.e., variables whose values are allowed to be void):
search key, data value, parent node, left child, and right child. An obvious property is that the root of the
tree stores void for its parent node.
– There are two kinds of tree nodes (see Figure 1 for an example):
• An external node appears at the bottom level of a tree: it does not have any child nodes (i.e., both left
and right store void), and its key and data values are both “undefined”. We sometimes call the external
node an “empty” node. Diagrammatically, we draw a square to represent an external node.
Note. As discussed above, the type of key or value of a node may be either a reference type or a primitive
type. For example, for a reference-typed node key, its value being “undefined” means it stores void, whereas
for a primitive-typed node key, its value being “undefined” means it stores the default value (e.g., 0 for an
integer key).
• An internal node has a key that is comparable (for searching purpose) and a value. To initialize, an
internal node, its left and right nodes must be external (rather than void). Diagrammatically, we draw a
circle, containing the stored key-value pair, to represent an internal node (see Figure 1).
– Figure 1 shows an example a binary tree, where circles and squares represent, respectively, internal and external
nodes. Each internal node stores a key-value entry. e.g., (10, "Grant") denotes that the stored key is 10 and
the value is "Grant". Each arrow indicates a parent-child relation.
4.2 Binary Search Tree (BST)
A binary search tree (BST) is a binary tree satisfying the search property (e.g., Figure 1). For every internal node n:
– Every internal node nleft in n’s left subtree is such that key(nleft) < key(n).
– Every internal node nright in n’s right subtree is such that key(nright) > key(n).
4
(10, "Grant")
(2, "Joy") (17, "Frank")
(1, "Manda") (7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(key, value)
External Node
Internal Node
Legend
Figure 1: Example: Binary Tree (satisfying the search property)
4.3 Splay Tree
In this lab exercise you are required to implement and specify a splay tree, a special kind of BST (Section 4.2) which
is self-adjusting and whose amortized (or average) running time for search, insertion, or deletion is as satisfactory as
a strictly balanced BST (e.g., an AVL tree).
– A splay tree attempts to balance heights of the left and right subtrees with a splay operation. When a splay
operation is performed, a number of rotations are performed from a node along its ancestor path to the root.
– A splay operation is necessary somewhere in search, insertion, or deletion. Consequently, the amortized running
time (i.e., the average running time) for each search, insertion, or deletion is O(log n) (where n is the number of
nodes in the tree).
– A splay tree is balanced BST, not strictly always, but so over time. More precisely, a splay tree does not enforce
a maximum height difference between the left and right subtrees as strictly balanced BST does such as an AVL
tree. However, whereas the worst-case running time of search, insertion, or deletion of a splay tree may still
be O(n), it is self-adjusting (via splay operations) over time and its amortized running time is thus equally
satisfactory: O(log n). Therefore, we still consider a splay tree as a balanced BST.
Reference. Information summarized in this lab manual suffices for you to complete the assigned tasks about a
splay tree. However, optionally, if you wish to explore more about this idea of a self-adjusting BST, see the original
paper by D. Sleator and R. Tarjan: https://www.cs.cmu.edu/˜sleator/papers/self-adjusting.pdf.
4.4 Perfomring a Rotation on a Tree Node
– A rotation on a node n in a splay tree (which is identical to a node rotation in an AVL tree):
• Moves n up one level towards the root;
• Moves n’s parent down one level; and
• Maintains the search property (so that the resulting splay trees reamins as a BST).
– Let np be n’s parent and ngp be n’s grand parent (equivalently, np’s parent). Given that np or ngp may or
may not exist, there are five cases to consider in order to rotate a node n. In each case, we color n in green, np
in blue (if it exists), and ngp in red (if it exists).
5
Case 1: np does not exist (i.e., n is the root). Do nothing.
Now, for the reaming Cases 2, 3, 4, 5, we assume that np exists. The example shown below for each rotation
case can be generalized such that: sub-trees of n, np, or ngp may be arbitrarily complicated, and ngp is not
the root.
• Cases 2 and 3 assume that np and ngp exist. In general, np may be the left or right child of ngp.
Examples for Case 2 and Case 3 below only show the case where np is the left child of ngp.
Case 2: n is the left child of np. Replace np with n. Then, set n’s right child as np. For example:
(10, "Grant")
(2, "Joy") (17, "Frank")
(1, "Manda") (7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(10, "Grant")
(1, "Manda") (17, "Frank")
(7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(2, "Joy")
n
np
ngp
n
np
ngp
Case 3: n is the right child of np. Replace np with n. Then, set n’s left child as np. For example:
(10, "Grant")
(2, "Joy") (17, "Frank")
(1, "Manda") (7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(10, "Grant")
(7, "Chung") (17, "Frank")
(1, "Manda")
(8, "Nick")
root
(2, "Joy")
(5, "Jeffrey")n
nnp
np
ngpngp
• Cases 4 and 5 assume that ngp does not exist (i.e., np is the root).
Case 4: n is the left child of np. Replace the root with n. Then, set root’s right child as np. For example:
(10, "Grant")
(2, "Joy") (17, "Frank")
(1, "Manda") (7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(2, "Joy")
(1, "Manda") (10, "Grant")
(7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(17, "Frank")
n
np
np
n
Case 5: n is the right child of np. Replace root with n. Then, set root’s left child as np. For example:
(10, "Grant")
(2, "Joy") (17, "Frank")
(1, "Manda") (7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(17, "Frank")
(2, "Joy")
(1, "Manda") (7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(10, "Grant")
n
nnp
np
6
4.5 Performing a Splay Operation on a Tree Node
– A splay operation is an iterative process: each iteration performs either one or two node rotations (see the four
cases below). To splay a given node n, we keep rotating n upwards until n becomes the root of the tree. This
iterative process is guaranteed to terminate, given that each rotation moves n up by one level, and that the tree
height is finite. Given that each rotation maintains the search property, the resulting tree from a splay operation
is still a BST.
– As in Section 4.4, let np be n’s parent and ngp be n’s grand parent. In each case, we color n in green, np in
blue (if existing), and ngp in red (if existing).
– In each iteration of a splay operation, there are four possible scenarios to consider.
Case 1: np does not exist (n is the root). Do nothing.
Case 2 (Zig): np exists but ngp does not. Perform a rotation from n. For example:
(10, "Grant")
(2, "Joy") (17, "Frank")
(1, "Manda") (7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
np
n
Roatation
Case 4
at n
(2, "Joy")
(1, "Manda") (10, "Grant")
(7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(17, "Frank")
np
n
Symmetrically, you also need to consider when n is the right child of np.
• Cases 3 and 4 assume that both np and ngp exist.
Case 3 (Zig-Zig): ngp, np, n slant the same way. Perform one rotation on np followed by another rotation
on n. For example, if they all slant to the left, rotate np to the right, then n to the right:
(10, "Grant")
(2, "Joy") (17, "Frank")
(1, "Manda") (7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(2, "Joy")
(1, "Manda") (10, "Grant")
(7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(17, "Frank")
(1, "Manda")
(2, "Joy")
(7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(10, "Grant")
(17, "Frank")n
np
ngp
n
np
ngp
np
n
ngp
Roatation
Case 4
at np
Roatation
Case 4
at n
Symmetrically, you also need to consider when they all slant to the right.
Case 4 (Zig-Zag): ngp, np, n slant different ways. Perform two rotations on n. For example, if they first
slant to the left then to the right, rotate n to the left then to the right.
(10, "Grant")
(2, "Joy") (17, "Frank")
(1, "Manda") (7, "Chung")
root
(5, "Jeffrey") (8, "Nick")
(7, "Chung")
(2, "Joy")
(10, "Grant")
(1, "Manda") (5, "Jeffrey")
root
(8, "Nick") (17, "Frank")
ngp
np
n
n
ngp
np
Roatation
Case 3
at n
Roatation
Case 4
at n
(10, "Grant")
(7, "Chung") (17, "Frank")
(1, "Manda")
(8, "Nick")
root
(2, "Joy")
(5, "Jeffrey")
n
np
ngp
Symmetrically, you also need to consider when they first slant to the right then to the left.
7
4.6 Self-Adjustment of a Splay Tree
There are three basic routines which we may perform on a splay tree: search, insertion, and deletion. Additionally, a
splay tree adjusts itself, via a splay operation (Section 4.5), at somepoint in their routine, so as to achieve an amortized
logarithmic running time. We summarize how you should perform each of these routines:
– Search
1. A search operation proceeds by recursively searching either the left or the right child, depending on whether
the input k is smaller or bigger than the key of the current node.
2. Given a key k:
2.1 If k exists, we get the internal tree node that stores k and its associated value.
2.1.1 We splay this internal node to adjust the tree balance.
2.1.2 Then we return the value of the internal node we found.
2.2 If k does not exist, we get the external tree node that resides at the end of the search path.
2.2.1 We splay this external node’s parent, if it exists, to adjust the tree balance.
2.2.2 Then we return nothing.
– Insertion
1. Given that the node key k does not exists already in the tree, we are guranteed to find an external node
where an internal node with the key k would have existed.
2. To insert a new key-value pair (k, v) into the tree, we convert the external node we found into an internal
node storing key k and value v.
3. We splay the inserted internal node to adjust the tree balance.
– Deletion
1. We search for the internal node, say n, with the key k to delete.
2. We splay the internal node n we found.
3. There are three cases to cover in order for the deletion to be completed:
• Case 1. If n’s left and right child nodes are external, then delete n by replacing it with an external
node.
• Case 2. If exactly one of n’s child nodes is internal, then delete n by replacing it with its only internal
child.
• Case 3. If both of n’s child nodes are internal, then replace n by n’s left child, then find n’s inorder
predecessor, npred (the node with the largest key in n’s left subtree), splay npred, and connect npred
with n’s right-subtrees (See Section 5.3 for a tutorial video on splay tree deletion).
4.7 Useful Web Tool for Visualizing Splay Trees
To implement and specify the intermediate and advanced features of a splay tree, you may experiment with this
website to visualize how the various splay tree operations are performed: https://www.cs.usfca.edu/˜galles/
visualization/SplayTree.html. See Section 5.3 for two tutorial videos on the detailed walk-through of an insertion
into and a deletion from a splay tree.
8
5 (Optional) Tutorials on Tree Nodes and Splay Trees
Here we provide optional, short tutorials on some features which you may review before starting your development:
5.1 Test Environment Setup
– As emphasized, you are expected to treat tests given to you as the precise documentation for the to-do features.
– Specially, it is critical for you to understand how connected TREE NODE objects are created in each test.
– For example, consult with the this tutorial video (8:44) for understanding commands env empty and env int int
in class TEST ENVIRONMENT.
5.2 Starter Features
– {TREE NODE}.tree search
• Look up relavent tests in STARTER TESTS.
• Also, read the comments in the TREE NODE class.
• Optionally, consult with this short tutorial video (11:54) to understand how it works.
– {TREE NODE}.nodes
• Look up relavent tests in STARTER TESTS.
• Also, read the comments in the TREE NODE class.
• Optionally, consult with this short tutorial video (3:50) to understand how it works.
– {TREE NODE}.is same tree
• Look up relavent tests in STARTER TESTS.
• Also, read the comments in the TREE NODE class.
• Optionally, consult with this short tutorial video (4:06) to understand how it works.
5.3 Intermediate & Advanced Features
– {SPLAY TREE}.rotate, {SPLAY TREE}.splay, {SPLAY TREE}.search, {SPLAY TREE}.insert
• There are no starter tests given to you.
• There is one test showing how this feature can be used in some simple scenario in EXAMPLE TESTS.
• Also, refer to Section 4 for a summary of splay tree routines.
• Optionally, consult with this short tutorial video (34:13) to understand how it works.
– {SPLAY TREE}.rotate, {SPLAY TREE}.splay, {SPLAY TREE}.search, {SPLAY TREE}.delete
• There are no starter tests given to you.
• There is one test showing how this feature can be used in some simple scenario in EXAMPLE TESTS.
• Also, refer to Section 4 for a summary of splay tree routines.
• Optionally, consult with this short tutorial video (16:54) to understand how it works.
9
6 Getting Started
6.1 Work Sequence
1. Download the starter code (splay.zip) from the course eClass.
2. Unzip and compile the project in EStudio.
3. Start by running the Workbench System (Run, then Run Workbench System), and you will see the initial results
of running all starter tests:
4. We suggest the following workflow on completing this lab:
4.1 Finish all to-do features in class TREE NODE. The to-do features in class SPLAY TREE depend on them.
4.2 Finish the Basic section in class SPLAY TREE. This is as far as the given tests in STARTER TESTS cover.
4.3 Then finish to-do features in the Intermediate and Advanced sections of class SPLAY TREE.
4.4 Figure 2 summarizes the caller-callee relations among all to-do features and may help you understand better
the big picture.
10
Figure 2: The dependency graph. A node represents a feature in the Lab 1 project. This dependency graph was used
11
6.2 What if You Get Stuck?
When you are not sure about how a node or tree feature should be implemented or specified, always consult with:
– Section 4
– Section 5
– Given test cases in STARTER TESTS and EXAMPLE TESTS
All Boolean test queries given to you in these two classes should be treated as a precise documentation on how
the features under development are expected to be used. You are expected to study them in order to have a
clearer idea for your development.
– Comments for the feature
– Hints for the TODO
6.3 How to Read the Given Tests
Tests included in class STARTER TESTS cover all to-do features in class TREE NODE and basic features in class SPLAY TREE.
– Tests in STARTER TESTS are grouped by features to test. To read about tests related a particular feature, there
are two ways for you to easily find them. For example, if you want to look up tests for {TREE NODE}.tree search:
(Approach 1) Recall how we find ancestors of the ARRAY class in the introductory tutorial (Video 2)?
By right-click drag-and-drop the tree search feature into the Feature panel, you can choose to show its
callers.
(Approach 2) Simply search for the string "tree search" in STARTER TESTS.
– The deferred/abstract class TEST ENVIRONMENT defines commands for setting up node and tree objects for testing:
env int int, env root insert int int, and env root insert str str. These setup commmands are inherited
to the STARTER TEST class, and they exist to make re-usable the setup procedure of the same tree structure.
You may also reuse these setup commands when creating your own test cases, or you can just create your setup
commands.
– Tests in the STARTER TEST class are named systematically:
• The name of each test feature has the prefix of either tn or splay, indicating it is a TREE NODE test or a
SPLAY TREE test.
• What follows the name prefix, tn or splay, indicates the feature being tested. For example, splay has1
represents test # 1 for {SPLAY TREE}.has.
• All the local variables are prefixed with l .
• All the attached variables are prefixed with a .
• All the iteration variables in across notation are prefixed with i .
Tests included in class EXAMPLE TESTS cover some simple scenarios of using the Intermediate and Advanced
features in class SPLAY TREE. These tests are meant as starting points for you to develop the intermediate and advanced
features in class SPLAY TREE, and to write your own test cases to cover more scenarios.
12
7 Grading Scheme
When we grade you submission, a set of test cases are run automatically on your submitted project (given a large
number of submissions we receive). Consequently, there are two common reasons for your submission receiving a zero
for this lab (and in fact, for all subsequent labs and the project):
– When your submitted project does not compile (in which case it is not even possible to run test cases on your
submitted software).
– When your submitted project compiles, but it passes none of the grading tests (e.g., incorrect implementation,
infinite loops, infinite recursions).
That is, if your submitted code compiles, then the more test cases it passes, the higher marks you will receive. More
precisely, we divide all test cases into four non-overlapping categories:
1. Starter
The STARTER TESTS class given to you corresponds to all tests in the starter category.
Features that you must implement correctly in order to pass all starter tests are:
– All TODO features from the TREE NODE class.
– All TODO features under the Basic section of the SPLAY TREE class.
Notes.
– Besides the STARTER TESTS class, you are also given the EXAMPLE TESTS, which illustrate additional usages
of the intermediate and advanced features. These example tests will not be used to grade your submission;
however, passing them implies you have a good chance to pass some tests in the intermediate and advanced
categories.
– Treat tests in EXAMPLE TESTS as a starting point: in order to gain the maximum marks from the intermediate
and advanced categories, you should write more of your own test cases.
2. Basic
– The BASIC TESTS class is not given to you.
– BASIC TESTS class tests all the contracts you should have written for the following features:
• All TODO features from the TREE NODE class.
• All TODO features under the Basic section of the SPLAY TREE class.
3. Intermediate
– The INTERMEDIATE TESTS class is not given to you.
– The INTERMEDIATE TESTS class tests all the implementations and contracts of the following features:
• All TODO features under Intermediate section of the SPLAY TREE class.
4. Advanced
– The ADVANCED TESTS class is not given to you.
– The ADVANCED TESTS class tests all the implementations and contracts of the following features:
• All TODO features under Advanced section of the SPLAY TREE class.
The following table summarizes the distribution of percentage weight of each test category:
Test Category Summed Weight of this Category
Advanced 25%
Intermediate 10%
Basic 10%
Starter 55%
Consider an example student: if their submission passes all starter tests, they will receive a D+ (55%); if their
submission also pases all basic tests; they will receive a C+ (65%); if their submission also passes all intermediate
tests, they will receive a B+ (75%); and so on.
13
8 Submission
To get ready to submit:
– Close EStudio
– Delete the EIFGENs directory from your project directory splay.
– Please make sure the directory and project structures of your project are identical to following (with no EIFGENs):
By the due date, log into your account at the red server and submit via the following command:
submit 3311 Lab1 splay
where splay is your project directory for Lab1.
– Here is a short tutorial video guiding you the process of submitting your labs/project from home (It is just an
example for Lab0, and you would need to adapt it to Lab1).
– Submissions via Web Submit or email attachments are unacceptable and will not be graded.
– After you submit, there will be some automated program attempting to perform some basic checks on your
program: if your submitted directory has the expected structure, if Eiffel project compiles, and etc. Please be
patient and wait until it finishes.
– You are encouraged to submit multiple times before the deadline (this also allows you to backup
your work on the EECS server). Only the latest submission before the deadline will be graded.
– You may check the last submission status at any time:
feedback 3311 Lab1
– You may save the check result for later review:
feedback 3311 Lab1 > Lab1-check-result.txt
14
9 Amendments
List of changes, fixes, or clarifications will be added here.
– Comments in {SPLAY TREE}.out was changed to reflect its output.
”[x< −−(1, 1)−− >(2, 2), (1, 1)< −−(2, 2)−− >x]” → ”[x< −−(1, 1)−− >(2, 2), x¡−−(2, 2)−− >x]”
– TREE NODE’s invariant left is not itself was changed to check all nodes.
”attached left as a left and then a left.is internal” → ”attached left as a left”
– {TREE NODE}.insert left’s precondition left is external’s hint was corrected:
”p node.left must be external” → ”left child must be external.”
– {TREE NODE}.insert right’s precondition right is external’s hint was corrected:
”p node.right must be external” → ”right child must be external.”
– {SPLAY TREE}.has node and {SPLAY TREE}.count’s comments, which were supposed to be removed on the
development, were removed.
”Both implementation and postconditioin are completed for you. Nothing todo.” → ””
– Text highlightings were changed to be consistent.
e.g. ”TREE NODE” → ”‘TREE NODE‘”
– {TREE NODE}.has node’s postcondition correct search result’s comment has been fixed. (It is meant to be a
postcondition for students to write.)
”This postcondition is completed for you. Do not modify.” → ”Hint: Result must be same as the internal node
we found from subtree rooted at ‘Current‘ with the key ‘p key‘.”
15

欢迎咨询51作业君