Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer Science Cards Rewrite > Algorithms & Programs > Flashcards

Algorithms & Programs Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What is an algorithm

A

A set of rules to solve a specific problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the 3 most common methods for describing an algorithm

A

Pseudocode
Structured English
Flow Chart

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are 3 good programming practices to follow do that your program can be edited more easily in the future

A

Self documenting identifiers - suitable names for identifiers

Annotation - describe what the code is doing

Program layout - looks tidy and easy to differentiate different parts

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are parameters

A

Sets of conditions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Define a variable

A

A variable is a store of data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a constant

A

A constant is a variable which value doesn’t change during the runtime of a program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the lifetime of a variable

A

The lifetime of a variable is the duration of time for which the variable holds the value during the execution of a program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the scope of a variable

A

The scope of a variable describes the parts of the program in which the variable can be accessed.

E.g. a global variable would have a scope of the entire program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a subroutine

A

Performs a specific task packaged as a unit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the advantages of subroutines

A

Makes the program easier to understand by splitting into smaller chunks

By splitting the program into separate subroutines, it is easier to test each procedure in isolation before being used with the rest of the program

Allows team-working as different members of a team can be allocated different procedures to write

Procedures can be reused in future programs. It is also possible to compile procedures and put them into subroutine libraries so that they can be called from other programs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the two types of subroutine?

A

Procedures or functions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the difference between a function and a procedure?

A

A function produces am output/returns a value whereas a procedure doesn’t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a function?

A

A section of code that, when programming, can be called by another part of the program with the purpose of returning one single value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is a procedure?

A

A section of code which performs a specific task when called from elsewhere in the program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a parameter?

A

Values that can be sent to a procedure and/or received from a procedure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the two types of parameters

A

Value or reference

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is passing by value?

A

Parameters that are used to pass information into a procedure but which do not receive information back

E.g. this works by sending a copy of the parameter to the procedure so any changes made are to the copy and therefore so not affect the original value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is passing by reference?

A

Parameters that need to be able to pass information back.

E.g. this works by sending a copy of the memory address is passed into the procedure and therefore any changes made are to the memory location of the variable sent to the procedure.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Subroutines as a black box, what does this mean?

A

Separate from the rest of the program, hides the complexity within the subroutines

Ignored by programmers who are developing it ofc

A programmer only need to know the parameters (inputs and outputs) to the procedure and doesn’t need to know how the procedure works (I.e. what goes on inside)

Therefore code inside the procedure can be modified/improved without other parts of the program bring affected as long as it continues to use the same parameters

This is also why global variables are best avoided where possible as these are ways in which the procedure can interact with the rest of the program without using parameters

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are modules

A

Modules are collections of subroutines (procedures & functions)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Modules should he loosely coupled and highly cohesive, what does this mean?

A

Loosely coupled - independent or almost independent (they can function completely without the presence of the other) (the module is not much dependent on other modules)

Cohesion - the degree at which different parts of the module related to eachother
E.g. a module used to calculate tax returns should just contain subroutines used in different steps od the tax return process, and not routines used for other parts of the system (the parts of a module fit together to a high degree)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is validation?

A

Checking how appropriate the data being entered is

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What are the 6 types of validation

A

Range check - makes sure data is between a min and max val

Presence check - ensures that a particular data item hasn’t been omitted

Length check - could be min or max length of characters entered

Type check - ensures that the correct type of data has been entered e.g. quantity field only contains digits

Format check - correct format e.g. dd/mm/yy

Lookup check - checks the data entered is present in a list of possibilities e.g. confirms a postcode exists

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is verification?

A

Checking to see if the data entered is consistent

E.g. asking for you to enter password twice when changing it to avoid locking yourself out of your own account

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is DIV

A

Returns the amount one number goes into

E.g.

7 DIV 3 = 2

26
Q

What is MOD

A

Returns remainder

E.g.

7 DIV 3 = 1

27
Q

What is a recursive algorithm

A

An algorithm that calls itself and has a terminating condition

Any algorithm that is recursive could instead be written in an iterative way (using loops)

However, recursive algorithms usually require much less code and are therefore more elegant and in many cases a more natural way of thinking about the problem.

Downside is when a recursive algorithm runs it can use more memory as it needs to keep track of each of the multiple calls to the procedures on the run time stack

28
Q

Why are sorting algorithms important, why do we sort data?

A

Makes it easier to do tasks with

29
Q

Write bubblesort pseudocode

A

Answer on flashcard sheet

30
Q

Describe a bubble sort

A

Bubble sort is a simple sorting algorithm

It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order

After 1 pass the largest number should be moved to the last spot in the list

The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted

31
Q

Describe an insertion sort

A

Starting with the second item, compare to all items before it in the list, shifting them up one place until the correct place to insert the item is found

E.g.

32
Q

Insertion sort pseudocode

A

Check sheet

33
Q

What are the three characteristics of a recursive algorithm

A
  • parameters
    -function that has a terminating condition
    -calls itself
34
Q

When testing a sorting algorithm what different types of data should we use?

A

Random numbers
Same numbers
Nearly sorted
Unordered
Using 0 in list
Low to high order
High to low order

35
Q

Describe quick sort

A
  1. Find a pivot (data before pivot is listA, data after pivot is listB)

2.Move data less than the pivot into ListA and data after the pivot into ListB

  1. Split into sub-lists and quicksort again
  2. Terminate when there is only one item left in the list

The terminating condition is that it only calls quicksort if the list has more than 1 item in it

It is extremely fast when compared to the other sort algorithms, particularly with longer lists. However, as with all recursive algorithms it will use more memory when executing.

36
Q

Quicksort pseudocode

A

See sheet

37
Q

Why not make all parameters reference parameters?

A

There is a danger that the programmer of the procedure might accidently change the parameter values and so it is safer to pass a parameter by value so that the data can not be changed, even accidently

38
Q

Describe a serial search

A

Looking at each item one after the other until the item is found or the end of the list is reached

39
Q

Describe a sequential search

A

search is a slight improvement over serial search and can be used where the data is already sorted in order of the search field but where binary search can’t be used because direct access isn’t possible (e.g. searching a file on tape).

When searching through the list if an item is read that would be after the item being searched for then the search can stop immediately rather than waiting until end of list.

40
Q

Binary search

A

Extremely fast way to find data in a list, the data has to be sorted in order of the field being searched.

Can only be used where there is direct access to items in the list (e.g. data in memory or on disk)

Can’t be used to search data in a file on tape storage

41
Q

How does binary search work

A

The middle item is examined to see if it is the item being searched for
If it isn’t then either the bottom half or the top half of the list is discarded and the search then continues by again choosing the middle item in that half of the list.

This is a ‘divide and conquer’ algorithm where the amount of data to search reduces very quickly.

Binary search is sometimes implemented using recursive methods and sometimes using non-recursive (iterative). There isn’t really much difference between them: the recursive version is a little shorter and more elegant but will take up more memory on the stack when running.

42
Q

What is dijkstras algorithm

A

Used to find the shortest path between 2 nodes

Used in e.g. satnav, routing around the Internet, path finding in video games etc.

43
Q

Do big O questions

A

..

44
Q

Do dijkstras algorithm questions

A

..

45
Q

What do algorithms consist of

A

Sequence - executing lines of code one after the other in the order given

Selection - where there is a choice as to whether a set of instructions are executed (e.g. if statement)

Repetition - where the same instructions can be repeated in a loop

45
Q

What do algorithms consist of

A

Sequence - executing lines of code one after the other in the order given

Selection - where there is a choice as to whether a set of instructions are executed (e.g. if statement)

Repetition - where the same instructions can be repeated in a loop

Co

45
Q

What do algorithms consist of

A

Sequence - executing lines of code one after the other in the order given

Selection - where there is a choice as to whether a set of instructions are executed (e.g. if statement)

Repetition - where the same instructions can be repeated in a loop

Counts - where we need to keep track of the number of items or where we are in a list e.g. total = total + 1

Rogue value - a special value in a data set that indicates the end of the data

46
Q

What do algorithms consist of

A

Sequence - executing lines of code one after the other in the order given

Selection - where there is a choice as to whether a set of instructions are executed (e.g. if statement)

Repetition - where the same instructions can be repeated in a loop

47
Q

Why should you split programs into modules?

A

Can help to logically split a program up into sections relating to the task at hand e.g. sound effects, combat

Can be easier to test modules in isolation before linking it to the rest of the program

Modules can be worked on at different times by different people which would be difficult otherwise

Modules can be compiled separately and can be linked to other modules using the linkage editor

After compilation, can be stored on a computer in a subroutine library which can be used in future applications

Are loosely coupled and highly cohesive

48
Q

Why are subroutine libraries used

A

They are a folder (or folders) which store compiled, tried and tested, documented modules that can be used in other programs

Saves a lot of time as they don’t have to be written again

49
Q

Data compression

A

When the size of a file (or any block of data) is reduced

Two types
Lossy
Lossless

50
Q

Describe lossy compression

A

Reduces the size of a file but does it by losing some of the information

E.g. reducing the quality of jpeg or mp3 files

51
Q

Describe lossless compression

A

Reduces the size of a file without losing any information

E.g. png images, zip files, rar files

52
Q

Describe lossy compression

A

When compressed files are decompressed they do not give back the original data, because data was lost during compression

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

53
Q

What is run length encoding

A

A simple lossless compression technique

Where there are sections of a file where the same data repeats this is replaced with a single data value and a count.

This is less successful with text but is used with image and audio files.

54
Q

Dictionary encoding

A

A lossless compression technique

A dictionary of commonly occurring sequences of characters is created and in the text these sequences are replaced by pointers to the relevant dictionary entry.

The references are shorter than the data they replace so the file is reduced in size.

Huffman Coding looks at the frequency of each character with the most frequently used characters given a shorter code than others.

55
Q

How do you Dry run an algorithm

A

You may be asked to dry-run an algorithm with specified test data, either to try to identify what the algorithm does or to identify why an algorithm gives an error.

To dry-run, use a trace table with a column for each variable and if applicable, a column for output. As values change you should note those changes in the table.

56
Q

Why are procedures used in algorithms

A

Algorithm can be broken into smaller parts

Used to avoid the duplication of code

Procedures are used to make an algorithm/program more efficient and secure

Each procedure can be tested in isolation

57
Q

Standard module benefits

A

A standard module is one which carries out a common / standard task
E.g. print function / input

58
Q

Benefits of passing by reference

A

Avoids the larger amount of processing/storage (associated with padding by value)

  • allows the desired change to be passed back into the calling program

Computer Science Cards Rewrite (18 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions