Computing Abstraction Information

Discuss computing as a discipline and the role of abstraction in advances made in computing

Computing has been defined in various ways, including “the body of knowledge that surrounds computers and computation” used by the Computing Sciences Accreditation Board (Denning et al 1989), and “any goal-oriented activity requiring, benefiting from, or creating computers” (Shackelford et al 2006).

According to the Joint Task Force for Computing Curricula's definition therefore, computing encompasses design and implementation of hardware and software systems for a wide range of purposes; processing, structuring, and managing various kinds of information; doing scientific studies using computers; making computer systems behave intelligently; creating and using communications and entertainment media; finding and gathering information relevant to any particular purpose, and so on.

By its nature, computing draws knowledge and skills from the fields of engineering, mathematics and science, from which the discipline itself is rooted.

Abstraction is a mental model which removes complex details, and leaves only the information necessary to accomplish the goal (Dale & Lewis, 2006). The concept is widely used in Electrical Engineering circuit analysis as Thevenin and Norton's theorems for representing complex circuits as equivalent simple circuits.

Abstraction has also been key in the development of computing as it allowed innovations within individual layers of computing systems to be researched and developed independently of each other, e.g. the developments in Operating Systems designs and User Applications were all happening independent from advances in processor construction.

• Discuss Unicode standards.

The Unicode standard is a universal means of character encoding, developed by the Unicode Consortium, that is used to represent every character in every language (Wikipedia).

The Unicode character set 16 bits per character, enabling it to represent over 65,000 characters (Dale & Lewis, 2006); a lot more than the ASCII set's 256 characters, which were incorporated as a subset of the Unicode character set.

Each character is represented by a hexadecimal code, and the characters are classified under their source, e.g. ASCII/Latin, Thai, Greek, Chinese, etc.

The versatility of the standard has made it widely popular, and is used in many programming languages and computer systems.

Not all of the available codes in the standard have been assigned to characters, and although more than 30 writing systems are currently included, more are constantly being added.

The standard was first published in 1991, and has also been in constant revision since then; version 5.1 is expected during March 2008.

• Who first thought about the idea of using the binary number system to be able to create electronic devices that can present numbers and do calculations?

The binary number system as we know and use in computing today, was first used in the early 20th century on early non-mechanical computers.

The word “bit”, short for “binary digit” was coined by John Wilder Tukey, an American statistician and early computer scientist, who was working on an early computer project with John von Neumann in 1946(Stefan Porubský 2007).

However, George Stibitz of the Bell Telephone Laboratories (Bell Labs), New York City, had build a demonstration 1-bit binary adder using relays in 1937. Although it was just a demonstration machine, it was still the first binary computer (Stephen White 1996).

• Write the decimal number 127 as a Hexadecimal, an Octal and as a Binary number.

According to the Free Dictionary, the Hexadecimal Number System is a positional system of numeration that uses hexadecimal digits and a radix of sixteen.

To convert the decimal 127 to hexadecimal, we shall employ the recursion method.

Division	Quotient	Remainder	Hex Number
127/16	7	15	F
7/16	0	7	7F

So the hexadecimal equivalent is 7F

The Octal Number System is a positional system of numeration that uses octal digits and a radix of eight.

To convert the decimal 127 to octal, we shall employ the recursion method.

Division	Quotient	Remainder	Octal Number
127/8	15	7	7
15/8	1	7	77
1/8	0	1	177

So the octal equivalent is 177

The Binary Number System is defined as a positional system of numeration that uses binary digits and a radix of two

To convert the decimal 127 to binary, we shall employ the recursion method.

Division	Quotient	Remainder	Binary Number
127/2	63	1	1
63/2	31	1	11
31/2	15	1	111
15/2	7	1	1111
7/2	3	1	11111
3/2	1	1	111111
1/2	0	1	1111111

So the binary equivalent is 1111111

• What is the minimum number of bits is needed to represent marital status? Given that marital status can be one of the following options: married, divorced, widowed or never married. Explain your answer.

In the inherent nature of the binary system, each bit can only have two states, such as zero or one, one or off, etc.

Each bit can, therefore, only represent two things, i.e. with one being the “one-state”, and the other, the “zero-state”. In order to represent a more varied field, more bits would be required.

In this case the marital status field contains has four possible states, namely married, divorced, widowed and never married.

In general 2n bits represent n states (Dale), so in this case, 2n = 4 = 22.

So 2 bits would be required to represent the marital status, and this would use one of the combinations of 00, 01, 10 or 11 to correspond to one of the possible states.

• Given a fixed-size number scheme where k in the formula for the ten's compliment is 6 (see page 61), answer the following questions: a) How many positive integers can be represented?

In the formula for ten's complement, Negative (I) = 10k-I, k is the number of digits.

For k=6, then the largest integer possible is 999,999.

In a fixed size number system, half of the numbers represent negative integers, and in this case the positive integers would range from 1 to 499,999.

Therefore, 499,999 positive integers can be represented.

b) How many negative integers can be represented?

The negative integers are represented by integers 500,000 till 999,999.

Thus giving (999,999-500,000)+1=500,000 negative integers represented.

c) Draw the number line showing the three smallest and largest positive numbers, the three smallest and largest negative numbers and zero.

• Show the behaviour of the following circuit with a truth table

Inputs Gate 1 Gate 2 Gate 3 Gate 4 Gate 5 A B C (AB) (BC)' C' (AB+C')' (AB+C')'+(BC)'

Output

0	0	0	0	1	1	0	1	1
0	0	1	0	1	0	1	1	1
0	1	0	0	1	1	0	1	1
0	1	1	0	0	0	1	1	1
1	0	0	0	1	1	0	1	1
1	0	1	0	1	0	1	1	1
1	1	0	1	1	1	0	1	1
1	1	1	1	0	0	0	0	0

• Draw a circuit corresponding to the following Boolean expression: A'B + (B + C)'

• a) Calculate the capacity of a hard disk with 3736 Cylinders, 128 Heads and 63 Sectors with 512 bytes per sector. Give the answer in gigabytes (GB) and in gibibytes (GiB).

We shall use the equation:

Disk Size in Bytes = No. of Cylinders * No. of Heads * No. of Sectors * Bytes per sector

= 3736 * 128 * 63 * 512

= 15696221184 Bytes

According to the decimal definition of Gigabyte,

1 Gigabyte= 109 Bytes

Therefore, the disk size in Gigabytes is

= 15696221184/109

= 15.696 GB

Since, 1 Gibibyte= 230 Bytes

= 1,073,741,824 Bytes

Then the disk size in Gibibytes is,

= 15696221184/ 230

= 14.618 GiB

b) Why do you think that the practical use of binary prefixes remain mostly ignored by marketing literature.

According to James Wiebe, hard drive manufacturers have historically used decimal computations to determine disk size (Wiebe 2003). This gave them numbers to describe capacity which were direct and easily understandable by their clients. Marketing literature have a much greater impact and sales appeal to an audience when advertising a disk as having a capacity of 120GB, as opposed to 115.039GB. A less complicated number is also more comfortable for the general public to deal with, than mathematical jargon.

c) The following image is how windows reports the disk usage of a hard disk with a capacity reported to be 50GB by its manufacturer. Explain why it does not seem to add up.

The discrepancy in the sizes of the disk reported by the manufacturer, and the Windows operating system is due to the dissimilar computations used to obtain the decimal representation of the disk capacity.

Disk manufacturers use decimal or Base10 arithmetic to perform the computation, while Operating system vendors use binary, or Base2 arithmetic.

The decimal GB is (1000x1000x1000) Bytes, while the binary GB is (1024x1024x1024) Bytes (Wiebe 2003).

Therefore the binary size of this disk is:

52,428,795,904/(10243)

=48.8281

=48.8 GB

• a) Write a pseudo code algorithm to get three positive integers from a user and print them in numerical order.

Print “Please enter three positive integers separately”

Set List 1 to 0 Set List 2 to 0 Set List 3 to 0

Read num1 Read num2 Read num3 If (num1<num2) & (num1<num2) Set Li to num1 If (num2<num3) Set List2 to num2 Set List3 to num3 else Set List2 to num3 Set List3 to num2

ElseIf (num2<num1) & (num2<num3) Set Li to num2 If (num1<num3) Set List2 to num1 Set List3 to num3 else Set List2 to num3 Set List3 to num1

Else Set Li to num3 If (num1<num2) Set List2 to num1 Set List3 to num2 else Set List2 to num2 Set List3 to num1

Print “The numerical order of the numbers is:” Print Li+” “+List2+” “+List3

b) Enclose the algorithm within a loop that repeat until the user enters the first value of the trio as negative. When the user enters a negative value for the first value the program must not require the second and third values to be entered.

Print “This program will sort 3 positive integers. To end, please enter a negative value for the first entry” Print “Please enter three positive integers separately” Set num1 to zero

While (num1>=0)

Set List 1 to 0 Set List 2 to 0 Set List 3 to 0

Read num1 If (num1<0) break Read num2 Read num3 If (num1<num2) & (num1<num2) Set Li to num1 If (num2<num3) Set List2 to num2 Set List3 to num3 else Set List2 to num3 Set List3 to num2

ElseIf (num2<num1) & (num2<num3) Set Li to num2 If (num1<num3) Set List2 to num1 Set List3 to num3 else Set List2 to num3 Set List3 to num1

Else Set Li to num3 If (num1<num2) Set List2 to num1 Set List3 to num2 else Set List2 to num2 Set List3 to num1

Print “The numerical order of the numbers is:” Print Li+” “+List2+” “+List3

Print “Thank you for using the program”

c) List the identifiers in the algorithm in b) and tell whether they named data or actions.

The algorithm uses the following variables:

num1:data, integer num2:data, integer num3:data, integer

List 1:data, integer List2:data, integer List3:data, integer

Print:action - output data to display Set:action - store value into the variable If … ElseIf …Elseaction - perform the indented statements depending on the whether the condition is true or false. While:action - repeat the indented statements if the condition is true

d) Verify the algorithm in b) using a walk-through.

num1

num2

num3

Li

List2

List3

At the beginning

0

?

?

0

0

0

After first entry

4

?

?

0

0

0

After second entry

4

7

?

0

0

0

After third entry

4

7

5

0

0

0

After If statement

4

7

5

4

5

7

On second iteration

-1

-

-

0

0

0

• a) Use Pep/7 assembly language instructions to write a program to add the decimal values 7 and 19 and store the result in memory location 7D (Location is given in hexadecimal).

BR Main

num1:.WORD d#7

num2:.WORD d#19

Main:LOADA h#0000,i

ADDA num1,d

ADDA num2,d

STOREA h#007D,d

DECO h#007D,d

STOP

.END

b) Write the above program in Pep/7 machine language using hexadecimal notation.

70 00 07 00 07 00 13 08 00 00 19 00 03 19 00 05

11 00 7D F1 00 7D 00 zz

• Distinguish between the four programming paradigms mentioned in Chapter 8 and discuss the benefits of using each of them as purported in the literature. Also give an example of a programming language that supports each of the paradigms and the URL of a vendor for each language.

In their discussion of programming paradigms, Dale and Lewis (2006) introduce four programming paradigms namely: imperative, functional, logic programming, and object-oriented paradigms.

As the name implies, the imperative programming paradigm is characterized by sequential instructions executed in an order governed by control structures to solve a task. The languages in this class allow the programmer to express algorithms as a hierarchy of tasks, and they tend to use a syntax that is similar to descriptions of everyday routines.

One such language in this category is C++, which is available from Borland/CodeGear. Information on their product and tutorials and downloads can be obtained from https://www.codegear.com/products/cppbuilder.

The functional programming paradigm is based on the mathematical theory of functions. Computations are crafted and expressed as function calls, with no need for variables or value assignments, making it quite simple.

One of the popular languages in this paradigm is Lisp, which is available from Franz Inc. and more information on the product can be accessed their website at https://www.franz.com/.

The third kind discussed by Dale and Lewis is the Logic programming paradigm, which is based, as the name suggests, on the principles of symbolic logic. It utilizes axioms, inference rules, and queries and program execution is by systematic search in a set of facts declared by one type, and another type making use of a set of inference rules.

It is widely utilized in artificial intelligence, and PROLOG is a popular logic programming paradigm language. EZY Prolog is a PROLOG compiler which is available from EZY-Software at: https://www.ezy-software.com/ezyprolog/Prolog_Inference_Engine/ezy_prolog_overview.htm.

In the object-oriented programming paradigm the data and operations are encapsulated in objects, which interact with each other. Programmers are able to express their algorithms using a hierarchy of objects.

Smalltalk is a popular object-oriented programming language available from Cincom in their VisualWorks product, whose website is https://www.cincomsmalltalk.com/userblogs/cincom/blogView.

What exchange will be made next?

The Selection Sort algorithm works by progressively working through the array from the first or last index, and exchanging the positions of the current element and the next matching element in the unsorted section of the array. The sorting procedure may be by numerical or alphabetical precedence in ascending or descending order.

In the given example, the sorting algorithm is performing a numerical sorting procedure in descending order from right to left. The next position to be processed is that occupied by element “10”, and it shall be exchanged with element “14”, which is the highest numerical element in the unsorted subsection.

• Compare Bubble Sort and Quicksort by giving an example of a scenario where each of these algorithms would outperform the other.

Bubblesort and Quicksort are simple sorting algorithms that are classified under exchange sorts, as they sort data by systematically exchanging the positions held by individual items in an array (Knuth 1997).

Bubble sort works by progressively working from one end of the array, comparing the two adjacent items, switching them if so determined by the sort criteria, and then shifting the focus one step forward in the array to repeat the procedure on the next item in the array with the one from the prior sort.

The operation continues until the end of the array has been reached, at which point the highest or lowest value shall have “bubbled” to the end of the array.

The rest of the items in the array may have altered their positions in the array, but may not be in their sorted positions. Therefore, the procedure may have to be repeated a number of times, in order to get the second, third, and all other items into their correctly sorted positions.

Due to its operation, the bubble sort is an inherently slow procedure, and a common method used to improve the performance, is to reverse the direction and invert the sort criteria when at the end of the array.

Quicksort, on the other hand, works by progressively breaking down the data for sorting, first into two lists of greater-than and less-than around an element in array called a “pivot”, recursively sorting the sub lists, and then combing the two sorted sub lists to give the final sorted array.

The Quicksort algorithm can be further enhanced when sorting really large lists of data, by recursively breaking down the sub lists into smaller ones using pivot elements in the sub lists.

This would be handy when, for example, sorting names of participants attending a conference. The first pivot could be surnames starting with M, giving sub lists of A-L and M-Z. The A-L sub list could then itself be pivoted using F, and so on until a level is reached at which point simple sorting can be done. After which, the sub lists would be recombined to give the sorted list of data.

Sorting such a large list of data using the Bubble sort would be extremely slow and impractical. However, the Bubble sort algorithm can be used as a simple confirmation algorithm to verify if the data list has been correctly sorted.

If we setup the Bubble sort algorithm to keep count of any exchanges it performs, and we obtain a result of nil, then the list has been arranged correctly.

• Use examples to show when each of the three partition selection approaches mentioned in chapter 10 is optimal.

Partition selection describes the decision process by which memory locations for new programs in variable length. Partitions are allocated. There are three general methods used in the allocation (Dale & Lewis, 2006) namely: first fit, best fit and worst fit.

The First fit method simply places the program into the first partition big enough to hold it. For example, in a system that uses fixed partition sizes determined at boot time, the system may divide the memory into partitions of size X, Y and Z, where Y is greater than X and Z is greater than Y. When a new program is started, and is determined to require a memory size larger than X but less than Y, then it is loaded into the first Y or Z size partition that is available. If a Z size partition is available ahead of any Y size partition, then it shall be allocated that partition.

Best fit criteria works by allocating the program the smallest partition that it can fit in. In the above example, if the program is determined to require a size larger than X, but less than Z, then it shall be allocated an available Y size partition.

The worst fit method allocates the program the largest partition that is big enough to hold it. In the above example, a Z size partition would be allocated. This method is impractical to use in fixed partition sizes, as it would be wasteful. In dynamic partitions, though, where partition sizes are constantly getting resized to fit programs, this allocation method leaves the largest partitions intact to accommodate other programs later on.

• The term virtual machine is used in three different contexts (Page 235, 328 and 343). Discuss the relation between the different definitions of a virtual machine.

According to Dale and Lewis (2006), a virtual machine can be defined in three different contexts as:

• A hypothetical computer entity operating on a computer and running programs by interpreting Byte code.

• An implementation on a computer system where a user utilizes the computer resources as they would on their own computer, although in effect the resources are shared with other users in a similar environment on the same computer system.

• The illusion created by a timesharing system that each user has a dedicated machine.

The first definition refers to an interaction between processes running on computer, for example The Java Virtual machine is a computer process running on a computer that provides a separate computer environment for the execution of Java bytecode.

The second and third definitions are interconnected and are in the domain of computer system and its timesharing user environment. One is the virtual machine from the perspective of the user, who is primarily concerned with their own virtual computing environment created through the sharing of resources, e.g. a Linux terminal window. The other is as seen by the computer system itself, which is running a managerial process overseeing the administration of the timeshared resources for all the users on the system, e.g. IBM's VM/370 operating system (Creasy, 1981).

Bibliography

Bubble sort From Wikipedia, the free encyclopedia [Online] Available at:https://en.wikipedia.org/wiki/Bubble_sort Creasy R.J 1981. ‘The Origin of the VM/370 Time-sharing System' IBM Journal of Research and Development Volume 25 No. 5

Dale N. & Lewis J. 2006. Computer Science Illuminated, Third Edition Sadbury, Massachusetts: Jones & Bartlett Publishers

Denning, P.J et al 1989 ‘Computing as a Discipline'Computer Volume 22, Issue 2 Pages: 63 - 70

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.1: Minimum-Comparison Sorting, pp.180-197.

James Wiebe 2003 "When One Billion does not equal One Billion, or: Why your computer's disk drive capacity doesn't appear to match the stated capacity" White-paper on the controversy over drive capacities

Quicksort From Wikipedia, the free encyclopedia [Online] Available at: https://en.wikipedia.org/wiki/Quicksort

Shackelford R. et al 2006 ‘Computing Curricula 2005: The Overview Report ‘ ACM SIGCSE Bulletin Volume 38, Issue 1 Schwartzman, S. (1994). The Words of Mathematics: an etymological dictionary of mathematical terms used in English. ISBN 0-88385-511-9.

Stefan Porubský: Bit. Interactive Information Portal for Algorithmic Mathematics, Institute of Computer Science of the Czech Academy of Sciences, Prague, Czech Republic [Online] Available at: https://www.cs.cas.cz/portal/AlgoMath/ComputerScience/DataStructures/Bit.htm [Accessed on 24 February 2008] Unicode From Wikipedia, the free encyclopedia [Online] Available at: https://en.wikipedia.org/wiki/Unicode

Cite this page