1.3 Algorithms

Question 1

Describe what happens to a file when it is compressed and give two reasons why files are often compressed

Answer 1

When a file is compressed the file size is made smaller
· To send as an email attachment
· Upload to a web site
· Save storage (disc, solid state, optical, server) space

Question 2

Fragmented meaning

Answer 2

Fragmented files are split up and stored on different parts of the disc

Question 3

Fragmented file compared to the time it takes to access a file that is not fragmented

Answer 3

· It can take longer to access a fragmented file because there is more read/write head movement to locate all the file parts and this movement takes time.

· If a file is not fragmented then it will be stored in consecutive blocks with minimal read/write head movement.

Question 4

Describe what happens to fragmented files when a hard disc drive is defragmented

Answer 4

When a hard disc is defragmented parts of files are physically moved closer together to reduce read/write head movement.

Question 5

Give two reasons why it is good programming practice to use procedures (subprograms) when writing large programs.

Answer 5

It is good programming practice to use procedures when writing large programs because:
· Procedures can be re-used in other programs
· They can be tested independently before incorporating into program
· They can be used when solving problems using stepwise refinement
· They make the programs easier to read
· They make programs easier to debug

Question 6

Explain the term recursive algorithm and briefly describe how quicksort operates

Answer 6

A recursive algorithm is one which calls itself.

It must also have a “base case” to allow it to terminate

Quicksort description:
· An item/pivot selected
· Produce two new lists of smaller and larger numbers
· Repeat above points on new sub lists (recursively) until sorted

Question 7

A benefit, describe a situation where data compression

Answer 7

· To send as an email attachment as smaller files transfer quicker or may have maximum size of an attachment

· Upload to a web site as larger files take longer to upload or might be restrictions on maximum file size that can be uploaded

· Saving a file to disc if short on disc space or to save disc space

Question 8

Explain how a sequential search is used to locate an element called SearchValue in an array sorted in ascending order called SearchArray

Answer 8

Starting at the beginning of the array and SearchValue is compared to every consecutive item
in SearchArray until either an item matches
SearchValue or the end of the array is reached
or an item in the array is found to be bigger than Searchvalue

Question 9

Briefly describe what sub procedure ProcOne does.

Answer 9

Purpose of algorithm is to swap (consecutive) two elements of an array

Question 10

Pseudo-code is often used to define algorithms. Name two other methods of defining algorithms

Answer 10

· structured English

· flowcharts

Question 11

Describe how an insertion sort works.

Answer 11

· Items are copied/placed into a (new) array one at a time
· Each item is inserted in the correct place
· All succeeding items in the new array are moved up one place.

Question 12

Give one reason why it is useful to standardise computer languages

Answer 12

• program written in a certain language on one computer/environment is likely to run easily on a different computer/environment
• programmer familiar with the language on one computer/environment is likely to be able to adapt easily to working on a different computer/environment

Question 13

Briefly describe an issue associated with standardising computer languages

Answer 13

• different manufacturers / developers approaching problem differently - may not be keen to share for commercial reasons

Question 14

Describe the purpose and give a benefit of using subprogram libraries

Answer 14

Subprogram libraries contain utilities / common tasks, etc 1

and can be used by any user, avoiding re-writing

Question 15

Describe the disadvantage of compiling the whole program in one operation

Answer 15

Any one of:
•   A module might be useful in another program. If it has been complied as part of a whole program, it will not be available in compiled form for the new program. 
•   If any errors are corrected /changes made, the whole program will have to be re-compiled.
•   It may be preferable to test each module before combining into the whole program / It is easier to find errors in smaller modules.

Question 16

Describe what is meant by the term algorithm and name two methods of defining algorithms

Answer 16

An algorithm is a set of rules / instructions 
to solve a (specific) problem 
Any 2 of:
·   structured English 
·   flowchart
·   pseudo-code

Question 17

Explain lossy data compression techniques.

Answer 17

· Data compression reduces the file size
· When compressed files are decompressed they do not give back the original data, i.e. data is lost
· Because lossy compression cannot be decompressed to yield the exact original data, it is not a good method of compression for critical data, such as textual data
· It is most useful for digitally sampled analogue data, such as sound, video, graphics or images
· Some examples of lossy data compression algorithms are JPEG, MPEG, and MP3.
· Algorithms for lossy compression vary, but many use a threshold level truncation. / suitable lossy data compression example

Question 18

Define the term algorithm. Other than pseudo-code, state one method of expressing an algorithm.

Answer 18

An algorithm is an (unambiguous) set of instructions to solve a problem
An alternative method to pseudo code of expressing an algorithm is a flowchart / structured English

Question 19

Describe the main characteristics of a recursive algorithm

Answer 19

A recursive algorithm is one which calls itself (with a parameter which changes) and It must have a terminating condition (base case) to stop the calls

Question 20

Describe two disadvantages of using a recursive algorithm

Answer 20

· Memory overheads of stack use with many recursive procedural calls
· Difficult to program / dry run/debug if there is a fault
· Stack overflow
· Infinite loop

Question 21

Describe how bubble sort and insertion sort algorithms operate.

Answer 21

Bubble
· A number of passes is made until the data is in order.
· For each pass through the data, each value is compared with the following one and swapping them if necessary.

Insertion sort
· Items are copied one by one
· Each new item is inserted in the correct place in the output