1.3 Algorithms Flashcards
Describe what happens to a file when it is compressed and give two reasons why files are often compressed
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
Fragmented meaning
Fragmented files are split up and stored on different parts of the disc
Fragmented file compared to the time it takes to access a file that is not fragmented
· 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.
Describe what happens to fragmented files when a hard disc drive is defragmented
When a hard disc is defragmented parts of files are physically moved closer together to reduce read/write head movement.
Give two reasons why it is good programming practice to use procedures (subprograms) when writing large programs.
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
Explain the term recursive algorithm and briefly describe how quicksort operates
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
A benefit, describe a situation where data compression
· 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
Explain how a sequential search is used to locate an element called SearchValue in an array sorted in ascending order called SearchArray
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
Briefly describe what sub procedure ProcOne does.
Purpose of algorithm is to swap (consecutive) two elements of an array
Pseudo-code is often used to define algorithms. Name two other methods of defining algorithms
· structured English
· flowcharts
Describe how an insertion sort works.
· 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.
Give one reason why it is useful to standardise computer languages
- 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
Briefly describe an issue associated with standardising computer languages
• different manufacturers / developers approaching problem differently - may not be keen to share for commercial reasons
Describe the purpose and give a benefit of using subprogram libraries
Subprogram libraries contain utilities / common tasks, etc 1
and can be used by any user, avoiding re-writing
Describe the disadvantage of compiling the whole program in one operation
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.
Describe what is meant by the term algorithm and name two methods of defining algorithms
An algorithm is a set of rules / instructions to solve a (specific) problem Any 2 of: · structured English · flowchart · pseudo-code
Explain lossy data compression techniques.
· 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
Define the term algorithm. Other than pseudo-code, state one method of expressing an algorithm.
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
Describe the main characteristics of a recursive algorithm
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
Describe two disadvantages of using a recursive algorithm
· 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
Describe how bubble sort and insertion sort algorithms operate.
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
