INDA
Tenta
March 11, 2000


READ THESE INSTRUCTIONS VERY CAREFULLY.  YOUR SUCCESS ON THIS EXAM MIGHT DEPEND ON IT.  IF YOU DO NOT FOLLOW THESE INSTRUCTIONS, WE WILL BE COMPLETELY MERCILESS.

There are three parts to this exam.  The point values of the first, second, and third parts are 30, 30, and 40 points respectively.  You may use your points for Quiz1 instead of taking the first part of the exam.  Likewise and independently, you may use your points from Quiz2 instead of taking the second part of the exam.  As for the third part of the exam, you are on your own!

You need 50 points to pass.  The number of points required for a 4 or 5 will be determined after the exams have been graded.  So, if you have a total of at least (i.e., >=) 50 points from Quiz1 and Quiz2, then you do not need to take the exam provided you are satisfied with a 3 on the exam.

NOTE:  You must decide whether to use any of your quiz points before you turn in your papers.  You must put a note on the cover page (i.e., the blue page where your name and ID number is written) clearly telling us what you want us to do.  If you tell us that you want, for example, to use your points from Quiz1, then we will not even look at anything you might have written for the first part of the exam.

WARNING!!!!!!!!!
(1)  If you do not tell us what to do with your quiz points for either quiz, then we will BY DEFAULT use your quiz points - even if you have solved the problems on the tenta and even if you got ZERO points on the quiz.
(2)  Your instructions must be clearly written on your blue cover sheet, otherwise they will be ignored.

You may have the following materials with you during the exam:
(1)  A Java programming book of your choice.
(2)  Your Aho & Ullman text.
(3)  A dictionary in the language of your choice.

No other materials will be allowed.

Good luck!

Rand


PART I

This part consists of 5 short answer type questions.  Each question is worth 6 points.


1.

Consider the following piece of code:
 

int[] numbers = {3, 2, 3, 6, 9, 10, 12, 32, 3, 12, 6};
for (int count = 1; count <= numbers.length; count++) {
    System.out.println(numbers[count]);
}
(a)  (3 points)

Will this code run correctly?  If your answer is no, you must explain what is wrong with it and describe a way to fix the problem (otherwise, no credit).

(b)  (3 points)

Given that the code is correct or it is incorrect but you implement the fixes that you suggested, explain the result of running the code.


2.

Write a Java statement or a set of Java statements to accomplish each of the following:

(a)  (3 points)

Sum the odd integers between 1 and 99 using a for structure.  Assume the integer variables sum and count have been declared.

(b) (3 points)

Print the integers from 1 to 20 using a while loop and the counter variable x.  Assume that the variable x has been declared, but not initialized.  Print only 5 integers per line.


3.

Answer the following questions regarding an array called table:

(a) (1 point)

Declare the array to be an integer array and to have 3 rows and 3 columns.  Assume the constant variable ARRAY_SIZE has been define to be 3.

(b) (1 point)

How many integer elements does the array contain?

(c) (4 points)

Use a for statement to initialize each element of the array to the sum of its subscripts.  Assume the integer variables x and y are declared as control variables.


4.

For (a)-(b) tell whether the statements are true or false.  If the answer is false, you must explain why.

(a)  (2 points)

When String objects are compared with ==, the result is true if the Strings contain the same values.

(b)  (1 point)

A String can be modified after it is created.

For (c)-(e) write a single statement that performs the indicated task.

(c)  (1 point)

Compare the string in s1 to the string in s2 for equality of contents.

(d)  (1 point)

Append the string s2 to the string s1.

(e)  (1 point)

Determine the length of the string in s1.


5.

Each of the following is worth 1 point.

Questions (a)-(d) are true/false questions.  If the answer is false, you must provide a justification.

(a)

In general, the decimal, octal, and hexadecimal representations of a given binary number contain more digits than the binary representation contains.

(b)

A popular reason for using the decimal number system is that it forms a convenient notation for abbreviating binary numbers simply by substituting one decimal digit per group of four binary bits.

(c)

The highest digit in any base is one more than the base.

(d)

The lowest digit in any base is one less than the base.

(e)

What is the positional value of the digit to left of the rightmost digit of any number in either binary, octal, decimal, or hexadecimal?

(f)

Convert the binary number 1101110 to decimal.


PART II

This part consists of two problems each worth 15 points.


6.

In most programming languages, parenthetic symbols (), [] and {} must be balanced and properly nested.  We define a parenthetically correct string of characters as a string that matches one of the following patterns, where S denotes a (possibly empty) string without any parenthetic symbols, and P, P' and P'' recursively denote parenthetically correct strings:

Design an algorithm that checks whether a string is parenthetically correct in time proportional to the size of the string using a stack as an auxiliary data structure.

Describe your algorithm in both words and pseudocode.  In your pseudocode, you may assume that you have the usual stack operations as given.  You must argue convincingly that your algorithm is correct and performs in the required time.


7.

Recall that in order to prove a statement S(n) for all n >= 1 by induction, we must do the following.

Consider the following proof of the statement:  All sheep in any given flock must be the same color. What is wrong with this proof?!


PART III


8.  (10 points)

Congratulations!  You have just been hired by the Historical Section of the Swedish Academy.  The chief historian has gathered 8000 texts describing a variety of insignificant historical events.  He wants you to store these texts in the section's computer in such a way that these events can be accessed according to the date on which they occurred.  The chief is somewhat of a computer enthusiast and has decided that the texts should be stored in a hash table using a hash key consisting of 8 digits:  The first four digits represent the year of the event, the next two digits represent the month of the year and the final two digits represent the day of the month.  For example, the key

17760704
is used to store the text describing the signing of the American Declaration of Independence on July 4, 1776.

In his infinite amateur wisdom, the chief directs you to implement the hash table using collision resolution by chaining.  He has also directed you to use a hash table of size 10000 with the hash function

key mod 10000.
(a)  (5 points)

Something does not sound quite right to you about all this.  So, you go away and do some simple back of the envelope calculations to estimate an upper bound on the number of table locations actually used and the average length of the collision chain corresponding to each location.  What do you find?

(b)  (5 points)

At the risk of insulting your new boss, you come to him with a counterproposal.  You say, "What about using a table roughly one tenth the size of the one you propose with the hash function "key mod 1003"?  Rather than becoming angry with you, he pleasantly surprises you with a questioning comeback:  "What is average length of the collision chains that result after storing my 8000 texts with your new scheme?"  What is your answer?


9.  (15 points)

You are given a sequence, S, of nonintersecting line segments s0, s1, ..., sn-1 with endpoints on the lines y=0 and y=1, and ordered from left to right.  Given a point q = (x, y) with 0 < y < 1, design an efficient algorithm that computes the segment si of S immediately to the right of q, or reports that q is to the right of all the segments.

Be sure to carefully describe your algorithm, argue for its correctness, and analyze its complexity.


10.  (15 points)

Let G be a graph whose vertices are the integers 1 through 8, and let the adjacent vertices of each vertex be given by the table below:

    vertex    adjacent vertices
        1            (2, 3, 4)
        2            (1, 3, 4)
        3            (1, 2, 4)
        4            (1, 2, 3, 6)
        5            (6, 7, 8)
        6            (4, 5, 7)
        7            (5, 6, 8)
        8            (5, 7)

Assume that, in a traversal of G, the adjacent vertices of a given vertex are returned in the same order as they are listed in the above table.

(a)  (5 points)

Draw G.

(b)  (5 points)

Give the sequence of vertices of G visited using a Depth First Search traversal starting at vertex 1.

(c)  (5 points)

Give the sequence of vertices visited using a Breadth First Search traversal starting at vertex 1.