Dennis C. Smolarski, S.J.'s Math 61, Homeans.DF Page

 
D-1) a)		first 	     middle   	      last 	 # comparisons
		1		5		10		2
		1		2		4		2
		3		3		4		2
		4		4		4		1
 	
	# of comparisons:  7

     b)		first 	     middle  	      last	  # comparisons
		1		5		10		2
		1		2		4		2
		3		3		4		2
		3		-		2		0

	# of comparisons:  6

     c)		first  	      middle   	      last  	  # comparisons
		1		5		10		1

	# of comparisons:  1

D-2)	a) 4
	b) 3
	c) 5

D-3)	a)	 4
	b)	10
	c)	 5

D-4)	a)	2048
	b)	11
	c)	either use linear search or first sort and then use
binary search.

D-5)	a)	5
	b)	256

E-1)	a) B D C A E
	b) C B A E D
	c) A B D E C

E-2)	a) s u s u s u s s u u 
	b) impossible
	c) s s s u u u s u s u 

E-3)	a) push: stack[ptr]:= x;
		 ptr := ptr + 1;
 	   pop : ptr := ptr - 1;
	         pop := stack[ptr];

	b) push: ptr := ptr - 1;
	         stack[ptr]:=x;
	   pop : pop := stack[ptr];
		 ptr := ptr + 1;	         

E-4)  a)	5 possible outputs
	ABC		SUSUSU
	ACB		SUSSUU
	BAC		SSUUSU
	BCA		SSUSUU
	CBA		SSSUUU
	NOTE:  CAB is NOT possible.

	b)   ABC, ACB, BAC, BCA  are all possible.
	CBA is NOT possible, since it requires 3 items on the stack.


F-1)	a) AB+CDE/-*    NOTE: the letters MUST be in the same order
	b) ABCD*+/E-	as in the original expression (i.e.
	c) ABC-D/+	alphabetical order).  Re-arranging the order
	d) AB+CD/-	is an illegal conversion.

F-2)	a) (A-B) + (C*D)
	b) ((A+B) * (C-D))/E
	c) A + (B -(C*D))
	d) (A * (B/C+D))