CHAPTER 1

Questions

1. Top down design is the process of solving a problem by breaking it down to successively smaller steps whose interrelationship is clearly defined and then solving each of the steps. Bottom up design is focusing on the details, then tackling each one separately, then gradually welding the partial answers into a coherent whole that provides a solution to the whole problem.

2. Step 1: Write everything down. Step 2: Apprehend the problem. Step 3: Design a solution. Step 4: Execute the completed plan. Step 5: Scrutinize the results.

3. Since an abstraction can be roughly defined as deliberately not knowing details, one can consider driving a car an abstraction because one does not need to know how build an automobile or know the details of how the car works in order to drive one.

4. An abstraction is a task that is seen as an organic whole. Going back to the example of the logger, we see abstraction at work. Unexperienced people would detail the steps to take in order to perform the task. The professional logger however, will view it as a whole and not worry about individual steps. It is part of the professional‹a built in function.

5. Answers may vary, depending on whether one believes a human has a soul, and is more than merely a body.

6. Money is a medium of exchange that represents an underlying value; it has no value except by mutual agreement.

7. A paradigm is a way of looking at something by way of analogy or example. A model is a representation in more concrete or accessible form than the original. The word may also be also used of a scale model for some proposed project. A world view is a complete set of philosophic or religious presuppositions within which paradigms and individual abstractions are formed. A meme is a transmittable idea that is the basis of a social movement or a political philosophy.

8. Answers may vary.

9. Data abstractions. --data representation abstractions (data structures). --data manipulation abstractions (expression structure). Machine abstractions. --the computing apparatus itself (machine structures) --the instruction and manipulation of the machine (program structures).

10. Data is a conglomerate of facts that has been collected, and has no particular meaning. Infomation is data that has been assigned a particular meaning. It is useful data that can be understood and applied.

11. (a) compound (b) atomic (c) compound (d) compound (e) atomic (f) compound

12. (a) real (b) unsigned whole number (c) compound : pair of unsigned whole numbers (d) string (e) signed whole number (f) boolean (g) unsigned whole number (h) real (i) boolean (j) compound: set of whole numbers (k) depends on the type of y2 and y1

13. An ADT is a specified set of items with certain properties and operations in comon.

14. There is a difference because of the limitation of the hardware. For some types, such as whole numbers, the abstract set is of infinite size. Abstract reals also have infinite precision. Neither property can be expressed in finite hardware.

15. A variable is a name whose value is subject to change during a course of a computation whereas a constant names a value that is fixed.

16. An expression is a combination of data items with various operators that are available for that data type. An expression is assigned a type according to the type of data produced when the expression is evaluated.

17. The major tasks of computing hardware are: (i) input (ii) memory (iii) processing (iv) control (v) output

18. Read Only Memory is permanently coded into a memory chip at the time of manufacturing. It never loses its data when power to the chip is lost. Random Access Memory contains data that is temporarily stored and can be changed. It loses its data if power is lost.

19. Hardware is the physical components, including the electronics, that make up the computer itself. Firmware are the programs that are coded into ROM chips at time of manufacturing.

20. The virtual machine is the total environment presented to the user by the combination of hardware and software being employed at the moment.

21. The major task of the OS is to handle the disk drives and other I/O devices , and to provide an interface for programs.

22. Niklaus Wirth invented Pascal Modula-2, and Oberon.

23. COBOL is the language principally used for business applications.

24. A compiler is a program that takes code in text form text and translates it into machine language a single time for later execution. An interpreter is a program that translates into machine code as the program is run and every time it is run.

25. Sequence: one instruction following another in order. Selection: the choice among two or more alternative tasks depending on circumstances encountered when the solution is executed. Repetition/Iteration: a series of steps under the control of some condition (also known as a loop). There are 2 kinds‹top-of-loop tested and bottom-of-loop tested. Composition: letting the name of some code stand for the whole; one command containing a number of sequenced steps. Parallelism: The ability for code to be implemented on many processing devices simultaneously.

26. In top-of-loop testing, the test for exiting is made in the beginning of the loop. For example, a WHILE loop tests if the condition is met then proceeds if it is. However in a bottom-of-loop testing, the test is considered at the end of the loop, as in a REPEAT loop.

27. The advantage of writing programs in pseudocode before actual coding is as follows: (i) One need not pay particular attention at this stage to the specific grammatical details of the actual code in a particular notation. (ii) The pseudocode is general enough so that the solution can later be expressed in any one of several different actual coding notations. (iii) Writing in pseudocode forces the programmer to pay sufficient attention to detail to ensure that the solution is completely thought out. (iv) The pseudocode is easy to examine for possible efficiency imporvements and for the elimination of logical errors.

28. An algorithm is a technique to solve a problem expressed as a series of steps or instructions.

29. The syntax of a programming notation consists of a set of legal symbols, together with the grammatical rules expressing how those symbols may be employed to write correct programs. Sematics on the other hand is the meaning of code, either in the context of the notation or in that of a program.

30. Syntax errors are errors caused by incorrect spelling, misplaced or missing punctuation (such as semicolons ) or otherwise incorrect use of some part of the notation. It can be prevented by good proof reading.

Logical errors are caused by insufficient planning, fuzzy thinking, or poor program orgainztion. They are also caused by a failure to express the meaning of the problem in a fashion that can be translated into a solution. These can be corrected by good planning, organization, and development.

Problems

31. (a) 522 (b) -0.8 (c) 47 (d) true (e) true (f) false (g) bad expression: mixed whole and boolean (h) bad expression: mixed whole and real (i) bad expression: mixed boolean and whole (j) 7.0

32.

	start at zero
	set a counter to zero
	while counter < 20 
	  set number variable to counter times itself
	  print counter
	  increase counter by 1
	end while

33.

	read in number
	if number mod 2 = 0
	  even
	else
	  odd

34.

	Pass01:	1, 1
	Pass02:	2, 1
		2, 2
	Pass03:	3, 1
		3, 2
		3, 3
	.
	.
	.
	Pass10:	10, 1
		.
		.
		.
		10, 10

35.

	SumOfNSquares
	  ask user for number
	  read number
	  set counter to 1
	  set sum of square to 0
	  while counter <= number
	    add counter * counter to sum of square
	    increase counter by 1
	  end while
	end SumOfNSquares

36.

	SumOf10
	  set counter to 1
	  set sum to 0
	  while counter <= 10
	    read n
	    add n to sum
	    increase counter by 1
	  end while
	end SumOf10

37.

	SumOfN
	  ask user for number
	  read number
	  set counter to 1
	  set sum to 0
	  while counter <= number
	  add counter to sum
	  increase counter by 1
	  end while
	end SumOfN

38.

	SumNSumofSquare
	  ask user for number
	  read number
	  set counter to 1
	  set sum to 0
	  set sum of square to 0
	  while counter <= number
	    add counter to sum
	    add counter * counter to sum of square
	    increase counter by 1
	  end while
	end SumNSumofSquare

39.

	Sort3
	  set counter to 1
	  if first > second
	    set temp to second
	    set second to first
	    set first to temp
	  end if
	  if first > third
	    set temp to third
	    set third to first
	    set first to temp
	  end if
	  if second > third
	    set temp to third
	    set third to second
	    set second to temp
	  end if
	end Sort3

40.

	compute average
	  read n (* number of reals to do *)
	  set count to 1
	  set partial sum to 0
	  while count <= n
	    read currentReal
	    add currentReal to partial sum
	    add 1 to count
	  end while
	  set average to partial sum/ n
	  write out average
	end compute average

41.

	FindSequence
	  set total to number of items
	  fetch first number
	  set small to first number
	  set large to first number
	  set counter to 2
	  while counter <= total
	    fetch current number
	    if current number < small
	      set small to current
	    end if
	    if current number > small
	      set large to current
	    end if
	    increase counter by 1
	  end while
	end Find Sequence

42.

	LargeNSmall
	  read n
	  set count to 0
	  set sum to 0
	  fetch first number
	  set largest to first
	  set smallest to first
	  while count <= n
	    read current
	    add current to sum
	    if current > LargestNumber
	      set LargestNumber to current
	    end if
	    if current < SmallestNumber
	      set SmallestNumber to current
	    end if
	    increase count by 1
	  end while
	  set average to sum/n
	  print average
	  print LargestNumber
	  print SmallestNumber
	end LargeNSmall

43.

	MatrixAddition
	  set row to 0
	  set col to 0
	  set sum to 0
	  while row < 3
	    while col < 5
	      set sum to sum + matrix[row,  col]
	      increase col by 1
	    end while
	    increase row by 1
	  end while
	end MatrixAddition

44.

	MatrixAddition
	  set row to 0
	  set col to 0
	  set sum to 0
	  read numrows
	  read numcols
	  while row < numrows
	    while col < numcols
	      set sum to sum + matrix[row, col]
	      increase col by 1
	    end while
	    increase row by 1
	  end while
	end MatrixAddition

45.

	Project
	  set index to 1
	  while index <= 12
	    set b(index) to a(index) * 1.05
	    increase index by 1
	  end while

	  (* or using a matrix more explicitly
	  set index to 1
	  while index <= 12
	    set table(b, index) to table(a, index) * 1.05
	    increase index by 1
	  end while *)

	end Project

46.

	3Fields
	  set row to 1
	  set col to 1
	  while row <= lastItemNumber
	    set table(row, col+2) to table(row, col) - table(row, col+1)
	    increase row by 1
	  end while

	  (* or, if the columns are labeled, use
	  set table(row, netprofit) to table(row, reverse) - table(row, expense)
	  without a column variable *)

	end 3Fields

47.

	3FieldsB
	  set row to 1
	  set col to 1
	  while row <= lastItemNumber
	    set table(row, col+1) to table(row, col) * 0.07
	    set table(row, col+2) to table(row, col) + table(row, col+1)
	    increase row by 1
	  end while

	  (* same option will apply for question 46 *)

	end 3FieldsB