Dennis C. Smolarski, S.J.'s Math 61, Homeans.RY Page
R-1) 1 2 3 6 9 5 8 4 (Tenenbaum and Augenstein)
2 1 3 6 9 5 8 4 (Ford and Topp)
R-2) 4 1 5 3 2 6 9 8 (Tenenbaum and Augenstein)
2 4 5 3 1 6 9 8 (Ford and Topp)
S-1) 1 2 3 3 4 5 6 7 8 9 10 11
T-1) a) 3
b) A, D, C
c) No
d) No
e) Yes
f) A B C D E
A 0 1 0 1 1
B 1 0 1 1 0
C 0 1 0 0 1
D 1 1 0 0 1
E 1 0 1 1 0
T-2) (Because of HTML special use of the less than and greater than
symbols, the following graph may look very funny on a screen.
If you download the file and then print it out, it will come out
OK.)
_
( )
D<------A<=========>E--------->F
|\ | ^
| \ | |
| \ | |
| \ | |
| \ | |
| > V |
| B---------->C
| (_) ^
L___________________|
T-3) (b) just the upper half.
U-1) 1 2 3 4 5 6 7 8 9 10
---------------------------------------------------
| | 541 |111 |683 |901 |325 | |897 | | |
---------------------------------------------------
U-2) 1 2 3 4 5 6 7 8 9 10
---------------------------------------------------
| 325| 541| 901| 111| 897| | | 683| | |
---------------------------------------------------
U-3) 1 2 3 4 5 6 7 8 9 10
---------------------------------------------------
| 901| 111| 325| | 541| | | | 683| 897|
---------------------------------------------------
U-4) 1 comparison
V-1) Mark the cells which are in use.
V-2) Traversing a linked structure is best accomplished by recursive
code. Recursive code requires stacks which take up much space. We
are collecting garbage because we are out of space.
V-3) Since linked structures include addresses to the next location,
moving nodes makes the old addresses incorrect. "Forwarding addresses"
are needed in a garbage collection scheme as an interim step to
assure that after the move, the nodes in a linked structure will still
point to the correct next node(s).
W-1) In general, two tri-diagonal matrices will multiply out
to give a 5-diagonal matrix. Therefore, one has to calculate
the five central diagonals independently (plus worry about what
happens at the upper and lower corners). The following program
contains one way (in Procedure Matrixmult) of using space-saving
data structures and still being able to perform the correct
matrix-multiplication.
PROGRAM Mat(output);
CONST
n = 7;
TYPE
tridiagmatrix = ARRAY[1..3,1..n] OF integer;
matrix = ARRAY[1..n,1..n] OF integer;
VAR
a,b:tridiagmatrix;
c:matrix;
PROCEDURE Matrixmult(a,b:tridiagmatrix;
VAR c:matrix);
VAR
i:integer;
BEGIN
c[1,1]:= a[2,1]*b[2,1] + a[3,1]*b[1,1];
c[n,n]:= a[1,n-1]*b[3,n-1] + a[2,n]*b[2,n];
FOR i:=2 TO n-1 DO
c[i,i] := a[1,i-1]*b[3,i-1] + a[2,i]*b[2,i] + a[3,i]*b[1,i];
FOR i:=1 TO n-1 DO
c[i,i+1] := a[2,i]*b[3,i] + a[3,i]*b[2,i+1];
FOR i:=1 TO n-2 DO
c[i,i+2] := a[3,i]*b[3,i+1];
FOR i := 3 TO n DO
c[i,i-2] := a[1,i-1]*b[1,i-1];
FOR i:= 2 TO n DO
c[i,i-1] := a[1,i-1]*b[2,i-1] + a[2,i]*b[1,i-1];
END;
PROCEDURE Createmat(VAR x:tridiagmatrix);
VAR
i:integer;
BEGIN
FOR i:=1 TO n DO
BEGIN
x[1,i] := 1;
x[2,i] := 1;
x[3,i] := 1
END;
END;
PROCEDURE Printdiag(x:tridiagmatrix);
VAR
i,j:integer;
BEGIN
Write(x[2,1]:3,
x[3,1]:3);
FOR j:=3 TO n DO Write('0':3);
Writeln;
FOR i:= 2 TO n-1 DO
BEGIN
FOR j:= 1 TO i-2 DO Write('0':3);
Write(x[1,i-1]:3,
x[2,i]:3,
x[3,i]:3);
FOR j:= i+2 TO n DO Write('0':3);
Writeln
END;
FOR j:=1 TO n-2 DO Write('0':3);
Writeln(x[1,n-1]:3,
x[2,n]:3)
END;
PROCEDURE Printmat(x:matrix);
VAR
i,j:integer;
BEGIN
FOR i:= 1 TO n DO
BEGIN
FOR j := 1 TO n DO
Write(x[i,j]:3);
Writeln;
END
END;
BEGIN
Createmat(a);
Createmat(b);
Matrixmult(a,b,c);
Writeln('Matrix a - tridiagonal');
Printdiag(a);
Writeln;
Writeln('Matrix b - tridiagonal');
Printdiag(b);
Writeln;
Writeln('Matrix c - 5-diagonal');
Printmat(c)
END.
X-1. a) 59
b) 117
c) 79
Y-1. INDIRECT SORT: Sorting using an auxiliary ("key/index")
array, in which these INDICES are rearranged rather than the
actual data of the major array (which may be quite large).
ALMOST-COMPLETE BINARY TREE: A binary tree in which every node
has degree 0 or 2, leaves are either at the last level or
next-to-last level, and at the next-to-last level, the leaves are
to the right of any internal nodes.
STABLE SORT: A sort in which two items with the same key keep
the same position relative to each other after the sort as they
had before the sort.
HEAP STRUCTURE: almost an almost-complete binary tree which
may not be strictly binary, in that the right-most interior node
on the next-to-last level may only have a left child (and not a
right child).
HEAP: a heap structure in which the nodes contain keys and the
key at any node is greater than the keys at each of its
(possible) children.