Place:

The second test will focus on part of Chapter 4, Chapter 5 and 6 and part of Chapter 7 of the textbook (excluding Section 4.1-4.2.4, 4.4, 5.3.4, 5.4.4, 5.5, finding the insertion position (page 225-226), 6.3.4, 6.4, 7.2.2-7.7) and the additional material available on the course webpage and discussed in class. Students are also considered to be familiar with the material for the first test.

The test is a closed book test. No aids are permitted. The test will consist of two questions. Manage your time carefully. The last page of the test can be used as scrap paper. Tests written in pencil will not be considered for remarking. Do not leave during the last 10 minutes and stay seated until all tests have been collected.

Maybe. Both are part of the material to be studied.

*I would like to know if you have copies of previous tests or exams that we
could use as practice for the upcoming test and the one after as well.*

Last year's tests are not very useful for practicing. The assignments (excluding the parts about coding in Java) should give you some idea what kind of questions to expect.

*I wonder whether the test will cover the proposition. If it will,
do I have to memorize some of the basic propositions about the height as
well as the number of external nodes and internal nodes.*

It is good to know these propositions. You should even be able to prove them.

*About the property of the key comparator. Should I study them too.*

Yes, it is part of the material.

*Will we be asked an induction proof?*

Maybe, it is part of the material.

*If we are asked to write pseudo code for a method, will you
specify which implementation you would like us to use (i.e. Arrays or
linked lists) or may we chose?*

If I specify which implementation to use, then you better use that implementation. If I do not specify which implementation to use, then you just use the operations of the data structure, that is, give an algorithm which does not depend on a particular implementation of the data structure.

*I am trying to use sequence to implement Dictionary according to textbook,
I have a question about how to declare Sequence. Is it we need to declare
it based on the given implementation either by using linked list or array,
such as:*

Sequence S = new linkedSequence() or Sequence S = new arraySequence()

That is right. In the test I will only ask for pseudo code. In that case the above problem does not arise.

*Also, for the exam and also for the course, when we review the course
materials, we need to focus on the all kinds of implementations (how to code
these data structures in Java) or we need to focus on the general pictures
about the data structrue (how to use these data structures interactively).*

Both implementing and using data structures are key ingredients of this course. However, do not focus on Java. This is a course about data structures, not Java.

*I still don't understand, why we use* `isBalanced(tree)`

*and* `isBalanced(tree, position)`

*two different
methods?*

Because the empty tree does not have a root.

*Can you tell us, what type of questions do we have expect on the test?
Writing a code or algorithm like first test?*

Only pseudo code, no Java code.

*What is an invariant?*

First of all, distinguish between an invariant and a loop invariant. An invariant is a propostion about the variables used to implement a data structure which holds

- after initialization and
- if it holds before doing a particular operation on the data structure then it holds also after the operation has been performed.

*Is it possible the array-based implementation for insertFirst method of
positional sequence in constant time O(1)? (see text book page128). I am
not sure whether the array is circular.*

The array has to be circular. Otherwise, `insertFirst`

is
*O(n)*.