Brainscape's Knowledge GenomeTM

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


See full index

[OBSELETE] AQA - A Level CS > Computation > Flashcards

Computation Flashcards

1
Q

What is the definition of algorithm?

A

Set of instructions that can be followed to perform a task

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

How do you break down a problem?

A
  • Does the problem have different levels
  • Can it be broken down intol sections
  • Can the sections be broken down further
  • Each low level problem should be a single task
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the sequence programing construct?

A

DO one statment after the other in order

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

What is the selection programming construct?

A

Do a set of instructions based on a condition
Allows for code to make choices

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

What is the iteration programming construct?

A
  • Do a set of staments again
  • For a fixed amount of times
  • Or until a condition is met
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the rules for pseudo-code?

A
  1. Descirbe each step breifly
  2. Upper case = Close to programming langauge
  3. Lower case = Closer to english
  4. Keywords to show beggining and ending of the block of code
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What does hand tracing algorithms do?

A
  1. Looking at a printed extract of the program code and running through it like th computer
  2. Helps with understanding and finding any logical errors
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the steps in hand tracing the algorithms?

A
  1. Take each line one at a time
  2. Write out current state of each variable in a trace table
  3. Note down any output that program would produce
  4. To help understand and spot any logical errors in the program
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Trace this program?

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

Trace this program?

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

Trace this program

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

What is the process of abstraction?

A

Seperating ideas form reality
By hiding irrelevant details and only showing relevent data

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

What is representational abstraction?

A
  • Arriving at a representation by removing unnecessary detail
  • Like underground tube map only shows stations and intersections
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is abstraction by generalisation?

A
  • Grouping by common characteristics to arrive at a hierarchical relationship of the is a kind of type.
  • Going up is generalising
  • Going down is specilising
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the need for abstraction?

A
  • Needed to accuratly display and model certain situation
  • Depending on the level of detail needed
  • Like a tube map vs tourist map of london
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the different types of abstraction you need to know?

A
  1. Prodecural
  2. Functional
  3. Data
  4. Problem
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is prodecural abstraction?

A
  • Abstracting away actual values
  • Used in particular computation
  • Which is a computational pattern
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is functional abstraction?

A
  • Another layer of abstraction ontop of procedural
  • Disregards the particular computation method
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is data abstraction ?

A
  • Methodology that enables us to isolatehow a compound data object is used
  • From the details of how it is constructed

Like how the operations in a stack hides how the data is represented in arrays and variables using subroutines to carry out that operation

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

What is problem abstraction / reduction?

A
  • Removes details from a problem
  • Until you can represent it that is posssible to solve
  • As the problem has been reduced to one that already has been solved

*You can then unfold this graph and then find the shortest point (dijkstras algorithm) *

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

What is decomposition?

A

Taking big problems and breaking it down into smaller problems

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

What is step-wise refinement / top down modular design

A
  • Top level is name of the problem
  • Breaking down into more levels
  • Which continues until the lowest level has only one task
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is composition?

A
  • Botton up development
  • Solutions developed by putting pre-exsisting components together
  • Provent to work together

Lego - Predefined props hieght and width proven to interlock with each other

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

How is composition shown in programming langagues?

A
  • Dev implements pre-written procedures
  • Which are pre-tested, compiled and working
  • Which are packaged into libaries which allow other developers to use
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What are the steps in constructing computer science solutions from real world problems?

A
  1. Physiocal world scenrio
  2. Abstracted model to filter out uneccesary variables / side problems
  3. Construct algorithms based on abstracted model
  4. Implement algorithms using code and data structures
  5. Run code
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

How does automation apply to the real world?

A
  • Once abstracted models are turned into mathmatical models
  • We can use automation in the implementation of those models to process data much faster
  • Allowing breakthroughs in science like medicine and great discoveries
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is a finite state machine?

A
  • Abstract model of computation (how machine reacts to external events)
  • Used to design computer programs and sequential logic circuits
  • Can be one of a finite number of states at any one time
  • Changes state based on a trigger condition or some input
  • Visuallised through state transition diagrams
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is the structure of the FSM?

A
  1. Start state - where FSM begins
  2. Transition States - Allow us to move from one state to another
  3. Transition condition - Condition / input required to change state
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is the state transition table for this FSM?

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

What is a meanly machine?

A
  • FSM with an output
  • Output determined by both current state adn current input
  • Input for each condition / Output for using transition arrow
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What are sets in maths?

A
  • An Unordered collection of values or symbols in which each value or symbol occurs at most once
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What does a finite set mean?

A

A set whose elements can be counted off by natural numbers up to a particular number

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

What does cardinality mean in sets?

A

The numbe of elements in a set

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

What is an infinite set?

A
  • A set which has no end value
  • Represented by (“…”) at end of set
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is a countable set?

A
  • Can be finite set or a countably infinite set
  • A set which can be counted off against a subset of natural numbers
  • Where every element of a set is associated with a unque natural number
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What are the different expression symbols you need to know?

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

How do you understand expressions?

A
  • Write out expression in plain english
  • Using expression symbol meaning
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What is the cartesian product?

A
  • The product of two sets
  • Which is the set of all ordered pars (a,b)
  • Where a is a memeber of set A
  • And b is a member of set B
    (All Combinations of the two sets elements)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What is subsets and proper subsets in maths?

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

What is the union in maths?

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

What is intersection in maths?

A
42
Q

What is difference in maths?

A
43
Q

What is a regular expression?

A
  • Tool which allows computers to work with text patterns
  • Used for validation, pattern recognition in text files, syntax checking
  • Allows for a spcific set of conditions that stings have to meet to be valid
44
Q

What does the * metacharacter do?

A
45
Q

What does the + metacharacter do?

A
46
Q

What does the ? metacharacter do?

A
47
Q

What does the | metacharacter do?

A
48
Q

What are regular expressions and finite state machines?

A
  • Equivalent wats of defining a regular langague
  • Regular langague = abilitytorepresent it by a regular expression
  • Any regular langauge should be defined as a finite state machine langague input
49
Q

What is the finite state machine for this regular expression?

A
50
Q

What is the regular expression for this finite state machine

A
51
Q

What is Backus Naurus Form (BNF)?

A
  • Formal mathematical way of defining syntax unambiguously
  • Meta langague

Made up of sets of
- Terminal symbols
- Non-terminal symbosls
- Production rules

52
Q

Why do we use meta langagues?

A
  • Defining aspects of langagues is time consuming and lengthy in regular expressions
  • Some aspects have nested brackets so regular expressions cannot be used
  • BNF is a meta langague
53
Q

What is the structure of BNF?

A
54
Q

What does this BNF statment mean?

A
55
Q

What does this BNF stament mean?

A
  • A word is defined by 2 letters
  • A letter is defined as any letter from A to Z
56
Q

What is the BNF statment for defining words as characters?

A
57
Q

What is parsing?

A
  • Process of working out if a given statment is valid -
  • Accordin to the given BNF production rules
58
Q

What are sntax diagrams?

A
  • Graphical representation of BNF
  • Where the two methods of representing syntaz map directly onto one another
59
Q

What are the symbols for a terminal element?

A
  • Termnial element cant be broken down any further
60
Q

What is the symbol for a non-terminal element?

A
  • Defined in another syntax diagram
61
Q

What is the terminal element symbol ?

A
  • Element that may be used more than once
62
Q

What does this diagram mean?

A
  • A digit is any number from 0 to 9
  • Any number is a digit from 0 to 9 and can have as many digits as you want
63
Q

What is the end goal of alogrithm efficientcy?

A

Algorithms should
- Run as quickly as possible
- Take up the least amount of memory possible

64
Q

How do you compare algorithms relative to the size of the problem?

A
  • Considers thier complexity as a fucntion relative to the size of the operation
  • Look at number of operations
  • If the number of operations is the same as the input in a for loop then th algorithm is linear
  • If nunmber of operations stay the same regardless of input then the algorithms constant
65
Q

How do you measure the efficiency of an algorithm?

A
  • Time complexity - How much time they need to solve a given problem
  • Space complexity - The amount opf resouerces they require
66
Q

What are time wise efficient algorithms?

A

Algorithms that are more effiecient time wise

67
Q

What are space wise efficient algorithms?

A

Algorithms that are more effiecient space-wise

68
Q

What is the permutation of a set of objects or values?

A
  • Number of ways you can arrange those objets
  • Factorial - Four factorial = 4x3x2x1
  • Can be large when scaling up
69
Q

What does is mean where a function maps one set of values onto another?

A
  • Mapping one set of inputs onto a set of outpus
  • One elemtn on the input set relates to exactly one element of the output set
70
Q

What are the diffferent parts during function mapping?

A

Domain - All possible inputs of a function
Range - Set of all outpiuuts from a function
CoDoamin - All the possible values that may be output from a function

71
Q

What is the complexity of this psudocode?

A

7 due to having 7 lines

72
Q

Why is the complexity of this code 4 + 3n + 1

A
  • 5 lines of code which doesnt change when increasing or decreasing input
  • 3n is where depending on the output (n) there can be 3 lines for each value n is
73
Q

What are the steps in taking complexity and converting it to Big(O) notation?

A
  1. Remove all terms except for the one with the larget facotr or exponent
  2. Remove any constants and put into big O form
74
Q

What are the different Big O notations complexities you have to know?

A
  1. Constant complexity
  2. Logarithmic complexty
  3. Linear complexity
  4. Polynomial complexity
  5. Expoential complexity
75
Q

What is constant complexity?

A
  • O(1) - 1 can be any number
  • An algorithm that always exectures in the same time
  • Regardless of the size of the data set
  • Best algorithms
76
Q

What is Logarithmic complexity?

A
  • O(Log n)
  • An algorithm that havles the set in each pass
  • Efficientw with large data sets
  • Good algorithms
77
Q

What is linear complexity?

A
  • O(n)
  • An alogrithm whose performance is proprotional to the size of the data setr
  • Declines as the set grows
  • Fair algorithms
78
Q

What is polynomaial complexity?

A
  • O(n^2)
  • An algorithm whos performance is proportional to the square of the size of the data set
  • Significantly reduces efficientcy with increasinly large data sets
  • Poor algorithms
79
Q

What is exponential complexity?

A
  • O(2^n)
  • An algorithm that doubles in size with each addition to the data set in each pass
  • Inefficient
  • Extremely poor algorithms that should be avoided
80
Q

What is the time complexity for adding items to a serial array?

A
  • Contant complexity O(1)
  • Doesnt matter how big the array is
81
Q

What is the time complexity fo looking for a valuse in an undordered list

A
82
Q

What is the time complexity for adding items to a sequanetial array?

A
  • O(n)
  • Linear
  • Due to using a while or for loop to move the items ahead of the new item
  • As the array grows so does the amount of shuffling required
83
Q

What is the time complexity for binary search?

A
  • Logarithmic O(Log n)
  • Due to the number of results to seach halves each time
84
Q

What is the time complexity for pushing and popping items form stacks and queues?

A
  • Constant O(1)
  • Due to size not having an effect on adding or removing items
85
Q

What is the time complexity for searching through stacks or queues?

A
  • Linear O(n)
  • Search one by one due to unsequeneced data so linear search is required
86
Q

What is the time complexity for hashing?

A
  • Constant O(1)
  • The hashing algorithm will always produce a hash in the same amount of time
    UNLESS
  • Hash created is a synonym and searching for the next avaliable space (overflow) is required
  • Which is O(n)

So hashing algorithms that produce minimum synonyms is vital

87
Q

What is the tiem complexity for seaching, inserting and deleting items from a liniked list?

A
88
Q

What is the time complexity for searching binary trees?

A
  • Logarithmic
  • Due to either choosing left or right when trying to find a value
  • So half the dataset is cast as irrrelevent each time
89
Q

What are the time complexity for bubble sort and insertion sort?

A
  • Polynomial
  • O(n^2)
  • Both use a nested loop
90
Q

What are the general rules for deducing time complexity?

A
91
Q

How does hardware impose limits on algorithms?

A
  • Algorithms could require more memory then feasible meaning its unsolvable
  • Exponential work may be required for a problem to be done where adding more computing power wont make a significant difference
92
Q

What are tractable problems?

A
  • Any porblem solvable in a polynomaial time or better
  • Where It will run fast enough for it to be practical and useful
93
Q

What are intractable problems and the issues that come with them?

A
  • Any problem which cannot be solved in a polynomial time or better
  • Solvable but impractical as they take to long
  • You can use heuristic methosdinstead to give a good enough answer rather than the most optimal
94
Q

What are some problems that are difficult to solve for computers?

A
  • Broad or poorly defined probkems
  • Problems thatcallforsubjective evaluations
  • The Halting Problem
95
Q

What question does the halting problem ask?

A
  • Is it possible to write a program that takes in a algorithm and the inputs for that algorithm
  • And tell you if the program will halt when running
  • Without executing the program first
96
Q

What is the answer to the question that the halting problem presented?

A
  • Alan turing - No
  • Since the prooblem is unsolvable there exsists some problems that simply cannot be solved by computers
97
Q

What is the turing machine?

A
  • Aim to find out if every mathmatical task is computable
  • Consists of an infinite tape that contains 0,1and blanks
  • A read/write head where the pointer can read the data present or write new data over the current value

As well as a FSM which details
- Amount of possible states
- Inital start state
- Halt states
- Transition rules - what to do when certain machine is in certain sates

98
Q

How would a turing machine find the first 1 one the tape right of the current readwrite position?

A
99
Q

What are transition functions?

A
  • A way of representing turing machines and state transition diagrams and the accociated transition rules
100
Q

What is the transition state functions for this turing machine diagram?

A
101
Q

Wha is the universal turing machine?

A
  • Acts as interpreter where it takes in a standard description of an algorithm
  • Writes it back to the start of the tape
  • To then be executed which follows the instructions of the algorithm inputted
102
Q

What is the importance of the universal turing machine?

A
  • Anything a turing machine can computer a real world computer couuld also computer
  • Provides us adefiniton of what is omputable
  • General purpose machine - foreunner of modern computers
  • Same approach that programs and data take today

[OBSELETE] AQA - A Level CS (13 decks)

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