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()After Sequence is declared, then I can use the methods related sequence such as first, insertFirst(), etc. Is that right? If this kind of question is given in the exam, will this kind of information be given to us?
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
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).