Lecture 1 Homework
1. Does fixed-point representation or floating-point representation provide a wider range of values for a specific number of bits? Explain.
2. Write a type definition for each of the following::
a. A collection of ten integers
b. Student information containing a 25 character name, an integral final exam grade, a real average, and a character for the final grade
c. A group of 45 students
d. A class definition containing a 45 character instructor name and information for 45 students
3. Provide each of the following array or record aggregates:
a. A collection of ten integers initialized to all zeroes
b. Student information containing your name, a final exam grade of 90, an average grade of 96.5, and a final grade of A
4. Given the following type declarations:
TYPE Seasons IS (Winter, Spring, Summer, Autumn);
SUBTYPE Semesters IS Seasons RANGE Spring..Autumn;
TYPE Quarters IS NEW Seasons;
which are subtype declarations and which are derived types?
5. Given the following variable declarations based on the type declarations of the preceding problem:
Season: Seasons;
Semester: Semesters;
Quarter: Quarters;
indicate whether each of the following assignments is type compatible and, for those that are, whether they are always range compatible:
a. Season := Semester;
b. Quarter := Season;
c. Quarter := Semester;
d. Semester := Season;
Lecture 2 Homework
1. Write a package specification to implement complex numbers--numbers that contain a real and imaginary part. Make the type definition private. Provide two operations: addition and subtraction.
2. Write the body of the package defined in problem 1.
3. Define encapsulation and explain how encapsulation is accomplished in Ada.
4. Define the package specification for a child package of the package defined in problem 1 that performs input and output of complex numbers.
5. Write a client program that uses the packages defined in the previous problems. The program should read in two complex numbers, add them and print out their sum.
Lecture 3 Homework
1. The sequence of pentagonal numbers is the sequence 1, 5, 12, 22 ... It is computed by taking successive sums of the arithmetic progression 1, 4, 7, 10, 13 ... For example, 1 + 4 + 7 = 12, so 12 is the third pentagonal number. Write both an iterative and a recursive function to compute pentagonal numbers.
2. Write both an iterative and a recursive function that accepts a string as a parameter and returns the reversal of the string as the result.
3. Explain why recursion can lead to highly inefficient programs when used to solve certain classes of problems.
4. Determine the big-O for execution time and memory utilization of both functions written for problem 1 and both functions written for problem 2.
5. Rank the following big-O classes from least efficient to most efficient: O(n2), O(2n), O(log n), O(1), and O(n log n).
Lecture 4 Homework
1. Write a type declaration for the following array types:
a. A string of unspecifed length of upper case letters
b. Rainfall statistics which maintains the amount of rainfall for each hour of the day of each day of the month
c. An array of unspecified length of days of the week
d. A eight by eight checkerboard, where each square is a red checker, black checker, red king, black king or empty
2. Provide each of the following array aggregates:
a. A month with no rainfall using the type defined in 1b
b. An empty checkboard using the type defined in 1d
3. Write a Put procedure that prints out the table of rainfall, as defined in 1b, for a given month. The hours of the day should be the columns of the table. The days of the month should be the rows.
4. Write a function that takes an array of the type defined in 1c as a parameter and returns a count of the number of Mondays in the array.
5. Assume that the checkboard array, defined in 1d, is stored using row-major format. Also assume that the first element of the array is stored at memory location 1000 and that each square requires one byte of memory. At what memory location is the piece in the second row, seventh column stored?
Lecture 5 Homework
1. Explain why generic units are more likely to be reusable than nongeneric units.
2. Write a generic function that returns the smallest element of an array. The subscripts of the array should be an unconstrained range of integers. The components should be any ordered type.
3. Instantiate the function defined in problem 2 for both integer arrays and floating-point arrays.
4. Write a generic package specification to implement integer vectors of any length. Provide two operations: vector addition and vector subtraction. An exception should be raised for either operation if the vectors have different lengths. The elements of the vectors should be able to be any numeric type.
5. Instantiate the package defined in problem 4 for both integer vectors and for floating-point vectors.
Lecture 6 Homework
1. Write the package specification to define a package type for computer courses. All courses should include the course name defined as 30 character string. There are two kinds of computer courses: programming courses and nonprogramming courses. Programming courses have a data component specifying the language used. The choices are Ada 83, Ada 95, C, C++, LISP, or Prolog. There is only one operation defined: a Put procedure. Use a variant record to define the type.
2. Write the body of the package defined in problem 1.
3. Rewrite the package specification for the type defined in problem 1 using tagged and derived types.
4. Write the body of the package defined in problem 3.
5. What are the specialization relationships, is a relationships, that exist in the data defined in problem 1?
Lecture 7 Homework
1. Indicate whether of the following problems requires a stack, a first-in first-out queue, a priority, or some other data structure for its solution:
a. A program that needs to read in the names of students and write them out in reverse order.
b. A resource manager that assigns resources based on a first-come, first-served basis.
c. A payroll system that processes employee records by employee number.
d. A task scheduler that schedules tasks on a priority basis
2. Write a procedure that accepts an integer stack as a parameter and removes all the negative entries. This procedure should use a local stack to accomplish its task. Provide a driver procedure to test it. The driver should contain an instantiation of the generic stack package.
3. Suppose a priority queue were implemented by enqueuing new arrivals at the back of the queue and dequeuing by searching for the member with the highest priority. What would the big-O of these two operations be?
4. Evaluate the following prefix expressions:
a. × + 2 3 + 1 3
b. + × - 4 1 2 6
c. + + + 1 2 3 5
d. - + 9 1 × 2 3
5. Translate the following infix expressions to postfix:
a. 4 + 7 - (2 × 3)
b. (8 / 2) - 4 + 3 - 2
c. 9 × 2 + 6 - 1 + 3
d. 5 - 4 + 6 / 3 × 2
Lecture 8 Homework
1. Declare access type declarations to point to each of the following types:
a. An upper-case string of unspecified length
b. A record containing integer pound and floating-point ounces
c. An array of twenty-five Boolean values
d. A single integer value
2. Given the following assignments:
Pointer_1.ALL := 2;
Pointer_2.ALL := 3;
Pointer_3 := Pointer_2;
Pointer_4.ALL := Pointer_1.ALL;
Evaluate the following:
a. Pointer_1.ALL
b. Pointer_2.ALL
c. Pointer_3.ALL
d. Pointer_4.ALL
3. Why do dynamically allocated variables have to be allocated from a pool of memory different from the pool of memory used to allocate ordinary variables?
4. Explain why a linked list is more flexible than an array.
5. Write a function that accepts a pointer to the head of a singly linked list of integers and an integer constant as parameters. The function should return the number of occurrences of that constant within the list.
Lecture 9 Homework
1. Indicate which of the problems in lecture 7, problem 1, requires a keyed table for its solution.
2. Instantiate the sorted list package for a telephone directory. Define a record containing a fifteen character first name, a fifteen character last name and a seven digit telephone number. The last name should be the key field. Write the necessary function to extract the key from the record.
3. Rewrite the binary search procedure of the sequentially implemented sorted list package so that it is recursive.
4. What is the big-O of the binary search procedure in problem 3, with respect to both execution time and memory utilization.
5. Compare the sequentially allocated sorted list with the linked sorted list. What are the advantages of each implementation?
Lecture 10 Homework
1. Draw the following directed graph and determine whether it is connected and whether it contains cycles:
V = {a, b, c, d, e}
E = {<a,b>, <a,c>, <c,d>, <a,d>, <c,e>}
2. Construct both an adjacency matrix and an adjacency list representation for the directed graph defined in problem 1.
3. List the nodes of the directed graph in problem 1 in the order resulting from both a breadth-first and depth-first search starting at node a.
4. Determine one correct topological order for the directed graph in problem 1. Are there any other topological orders for this graph?
5. Write a procedure that determines whether a undirected graph of integers is connected. The program should use an instance of the generic undirected graph package. Write a driver procedure to test it.
Lecture 11 Homework
1. List the nodes of the binary tree shown below in the order resulting from each of the following
traversals: preorder, inorder, postorder, and level order.
2. Draw the binary tree representation for the following arithmetic expressions:
a. X + 3 * Y
b. (A + 7) - (B * 6)
c. B - 9 * T / 5
d. A REM B + 8
3. Refer to the binary tree in problem 1. Determine whether that binary tree is a binary search tree. Explain your answer.
4. Rewrite the search procedure of the binary search tree package so that it is recursive.
5. Draw the binary search tree that would result if the following numbers were inserted into an originally empty tree: 4, 9, 18, 28, 75. What is the big-O for searching this tree?
Lecture 12 Homework
1. Compute the maximum number of nodes for a full binary tree of height 4.
2. Give an example of a binary search tree that is as unbalanced as possible. Give an example of a binary tree that is height-balanced-(2), but not height-balanced (1).
3. Is the binary tree in lecture 11 homework, problem 1, full? Is it complete? Is height-balanced (1). Is it a heap? If it is not, transform it into a heap.
4. What are the most important characteristics of any hash function? Explain why collisions occur in hash tables and describe the effect they have on the efficiency of searching these tables.
5. Rank the big-O efficiencies of the search algorithms for a linear keyed table, a binary search table, and a hash table.
Lecture 13 Homework
1. Trace the execution of the insertion and bubble sorts on the following array of integers: 5, 12, 56, 14, 3, 23.
2. Give an example of a sort algorithm whose efficiency is dependent on the initial data. Compare the best case execution time efficiency of this algorithm with the worst case, in terms of big-O.
3. Compare the efficiency, in terms of big-O, of the merge sort with the efficiency of the heap sort, with respect to execution and memory. Which is most efficient?
4. Name one sort algorithm that uses recursion. What is the drawback to recursive sort algorithms?
5. Rewrite the insertion sort of the sorting package so that it is recursive.