Unit 2 - J276 Flashcards
Computational thinking is all about the ______ taken to find the best ________ to a complex _________.
stages, solution, problem
Abstraction - Picking out the _________ bits of information from the ________ whilst _______ the specific ______ that don’t matter
important, problem, ignoring, details
Decomposition - _________ a complex ________ into smaller ________ and ________ each one __________.
Splitting/Breaking, problem, problems, solving, individually
Algorithmic thinking - using a series of ______ steps to find ________ to a ________. - Algorithms can be ______ and ______ to solve ______ problems in the _______.
logical, solutions, problem, reused, adapted, similar, future
The 3 types of Computational thinking are
- __________
- D_________
- ___________ thinking
Abstraction
Decomposition
Algorithmic Thinking
Searches allow a set of ____ to be _______ in order for a specific ____ to be ______.
data, examined, item, found
The 2 types of searching ________ are
- ________ search
- ________ search
algorithms
Binary Search
Linear Search
Binary search looks for items in an ______ list.
1) Set _______ to the ______ position in the list
2) If the ______ value matches, the search ___
3) Otherwise, if the desired _____ is less than the _______, then the _____-____ of the list is ______ and the search keeps to the _____-___ of the list
4) Or, if the desired _____ is more than the _______, then the _____-____ of the list is ______ and the search keeps to the _____-___ of the list
5) Steps _ to _ are _______ until a ______ is found or there are no more items to be ______.
ordered,
counter, midpoint
desired, ends
value, midpoint, upper-half, ignored, lower-half
value, midpoint, lower-half, ignored, upper-half
2-4, repeated, match, found
A binary search is much more _______ algorithm than a _______ search - In an ordered list of every number from 0-100, a linear search would take __ steps to find the number 99, whilst a binary search will find it in just 7 steps
Binary search only works for _______ lists tho ;(
efficient, linear, 99 steps
ordered
A linear search can be used on an ________ list.
Starting at the ________ of the data set, ____ item of data is _______ until a ______ is found or there are no more ______ to find.
unordered
beginning, each, examined, match, items
A way to describe a linear search would be
1) Find out the _______ of the data ___
2) Set _______ to 0
3) ________ value held in the list at the _______ positon
4) ______ to see if the value at that ________ matches the ______ value
5) If it _______, the value is found and the search is ____.
6) If not, ________ the counter by __ and go back to step 3 until there are no more ____ to ______
length, set
counter
Examine, counter
Check, position, desired
matches, ended
increase, 1, items, find
Linear searches are ______ to make due to its ________ and they work on both _______ and ________ lists.
Although, they can be quite _______. - Suppose a list contained 100 items, and the 99th item had to be found, 99 steps would have to be taken to find that single item.
easy, simplicity, ordered, unordered
inefficient
A ______ search in psuedocode might look like this
find = 2
found = Falselength = list.length
counter = 0
while found == False and counter < length
if list[counter] == find then
found = True
print ('Found at position', counter)
else:
counter = counter + 1
endif
endwhile
if found == False then
print('Item not found')
endif
.
A _______ search in psuedocode might look like this
find = 11
found = False
length = list.length
lowerBound = 0
upperBound = length
while found == False
midpoint = int((upperBound + lowerBound))/2
if list[midPoint] == find then
print('Found at' , midPoint)
found = True
else
if list[midPoint]> item then
upperBound = midpoint-1
else
lowerBound = midpoint+1
endif
endif
endwhile
if found == False then
print('Not found')
endif
.
The 3 methods of sorting are
- B______ Sort
- M_____ Sort
- I________ Sort
Bubble Sort
Merge Sort
Insertion Sort
A bubble sort is the ______ of sorting algorithms. It works like this.
1) Start at the _______ of the list
2) Compare the ____ value in the list with the ____ one up. If the _____ value is bigger, _____ the positions of the ____ values
3) Move on to the ______ value in the list. Again, _______ this value with the next and swap if the value is ______.
4) Keep going until there are no more _____ to ________
5) Go back to the _____ of the list
simpliest
beginning
first, next, first, swap, two
second, compare, bigger
items, compare
start
Each run through the list, from _____ to ______ is known as a _____.
A bubble sort continues until a ____ is made where no ______ have been _______ - This is when the list is completely ______.
start, finish, pass
pass, values, swapped
sorted
The advantages of a bubble sort are
- Easy to ________ due to its simplicity
- Efficient if the list is in ______
- Not much _______ is used as all the sorting is done on the ________ list
implement
order
memory, original list
The disadvantages of bubble sorts are
- _________ for large list
- An extra ____ occurs even if the list is in ______.
Inefficient
pass, order
A psudeocode algorithm for a bubble sort might be
counter = 0
swapped = True
swaps = 0
length = list.length
while swapped == True
while counter < length-1
if list[counter] > list[counter+1] then
temp = list[counter]
list[counter] = list[counter+1]
list[counter+1] = temp
swaps = swaps + 1
endif
counter = counter + 1
endwhile
if swaps == 0 then
swapped = False
else:
swaps = 0
counter = 0
endif
endwhile
.
A merge sort ______ a list apart then ______ it back together in its ______ order. - It is an example of a ______ and _______ algorithm.
splits, merges, sorted, divide and conquer
A merge sort works like this.
1) Split the list in _____ to form ___-____ ( the second sublist should start with the ______ term for odd no. of items)
2) Keep ______ step 1 until each ___-_____ only contains ____ item
3) Merge pairs of ____-____ so that each ___-____ has _____ as many items. Each time you merge ____-____, ____ the items in the correct ______
4) ______ step 3 until you have _____ all ___-____ together
half, sub-lists, middle
repeating, sub-list, one
sub-lists, sub-list, twice, sub-lists, sort, order
Repeat, merged, sub-lists
The advantages of merge sorting
- More _______ and _______ than ______ and insertion for ______ lists
- Very consistent _______ ____ regardless of how the items in a list are ______
efficient, quicker, bubble, large
running time, ordered
The disadvantages of merge sorting
- Slower than other algorithms for _____ lists
- Still performs the _____ and _____ process even if the list is already _____.
- Uses more _______ than other algorithms as it creates ________ lists
short
split/divide, merge/conquer, sorted
memory, separate additional
An Insertion Sort just takes each item __ ____ and put them in the _____ place using the _____ item in the list as a starting point.
in turn, correct, first
An Insertion Sort works like this
1) Look at the ______ item in a list
2) Compare it to ___ items ______ it and insert the item in the ______ place
3) _______ step 2 until the ____ number in the list has been inserted into the _______ place
second
all, before, correct
Repeat, last, correct
The advantages of an Insertion Sort are
- Can be easily ____
- Efficient for _____ lists
- Doesn’t use much _______ as all sorting is done on the _______ list
- Quick to ___ items to an _______ list
- Quick at ________ if the list is already _______.
coded
small
memory, original
add, ordered
checking, ordered
An algorithm is a ______, ____ by ____ process for _______ a problem.
logical, step by step, solving
Algorithms are normally written as one of the following
- _________
- _____ diagram
Check BBC for more info
Pseudocode
Flow diagram
Psudeocode is a method of writing up a set of _______ in plain ______ that also closely resembles _______ languages.
It has its own _____, some of which is ______ to _________ languages.
Psuedocode itself cannot be ___ by a computer. - They need to be ______ into an actual ______ language
instructions, English, programming
syntax, similar, programming
run, converted, programming language
Here is an example of psuedocode
while answer != 'computer science'
answer = input ('What is your favourite subject? ')
if answer == 'computer science' then
print('Good choice!')
else
print('Really? ')
endif
endwhile
yep
Advantages of psuedocode
- Can be quickly and easily ______ to _______ language due to them being very ______
- Fairly easy to ________
- Doesn’t matter if there are errors in the _____ -
- _______ to the design can be made quite _____.
converted, programming, similar
understand
syntax
Changes, easily
The disadvantages of pseudocode are
- Can be hard to see how the program ____ if there are multiple _____
- _____ consuming to produce
flows, paths
Time
A flow diagram is a diagram that shows an _______ of a _______.
They use standardised ______ to represent the different types of ________.
These symbols are used to ________ the flowchart and show the ____-__-____ solution to a ______.
Check Bitesize or CGP for the symbols
overview, program
symbols, instruction
illustrate, step-by-step, problem
Advantages of flow diagrams
- Easy to see how a program _____ even with multiple _____
- Flow diagrams are an _________ standard - can be understood ________.
flows, paths
international, worldwide
Disadvantages of flow diagrams
- If the program is large, diagrams can become _____ in size and very _____ to follow
- Changes are hard to ________ as a lot of the diagram will probably have to be ______.
large, hard
incorporate, redrawn
The three basic programming constructs are
- ________ - the _____ in which instructors occur and are ________
- ________ - determines which ____ a program takes when it is _______
- ________ - the _______ execution of a _______ of code when a program is ________
Sequence, order, executed
Selection, path, running
Iteration, repeated, section, running
The two types of iteration are
- _____-________ iteration
- ________ - _______ iteration
Count-controlled
Condition-controlled
Sequence is the _____ in which lines of ____ are executed. In programming, lines of ____ are executed ___ after ______.
Sequence is important as running instructions in the _______ order will lead to _____ in the program, causing it to function _______ as well.
order, code, code, one after another
incorrect, errors, incorrectly
In this pseudocode program designed to find the average of two whole numbers, the instructions are in the wrong sequence:
total = 0
average = number1/number2
number1 = int(input(“Enter the first number: “))
number2 = int(input(“Enter the second number: “))
print(“The average is “, average)
Running this program would result in an error, because it tries to calculate the average before it knows the values of the numbers.
yh
To correct the previous psuedocode, the _______ average should be ______ after the number1 and _______ have been stated.
total = 0
number1 = int(input(“Enter the first number: “))
number2 = int(input(“Enter the second number: “))
average = number1/number2
print(“The average is “, average)
yh man
Selection is the process of making a ______. The result of the _______ decides which ____ the program will take next.
decision, decision, path
For example, a program could tell a user whether they are old enough to learn how to drive a car. If the user’s age meets the required driving age, the program would follow one _____ and execute one ___ of ________. Otherwise, it would follow a ________ path and execute a _______ set of _________.
path, set of instructions, different, different, instructions
Selection works by testing a _______ - The test gives a _______ result which could either be ____ or _____.
If the result is ____, the program follows one ____, otherwise it follows _______.
condition, boolean, TRUE or FALSE
TRUE, path, another
Selection is implemented using __ ____ ____ statements.
if then else
age = int(input(“How old are you? “)
if age > 16 then
print(“You are old enough to drive a car!”)
else
print(“Come back when you are older!”)
endif
In the above pseudocode program, the path the program takes depends on the _______. A ______, in this case age, is used to ____ the condition.
If the value age is greater than 16, the result of the tested condition is ____ and the program follows the ___ path, which follows the statement ____. This path informs the user that they are old enough to drive.
If the value of age is less than 16, the result is _____ and the program follows the ______ path, which follows the statement ___. This path informs the user that they are not yet old enough to drive.
The statement _____ ends the selection.
condition, variable, test
TRUE, first, then
FALSE, second, else
endif
Iteration is the _______ execution of a _______ of ______ within a computer program.
Iteration is also often referred to as ______, since the program “loops” back to _______ sections of _____. Sections of code that are iterated are called ______.
repetitive, section of code
looping, earlier, code, loops
Iteration enables programmers to greatly _______ a _______. - _____ lines of code don’t need to be _______ many times, the section can only be written _____, and the program can _______ it _____ times until it is no longer ______.
simplify, program,
similar/same, rewritten, once, execute, multiple, needed
Count-controlled iteration _______ executes a section of ____ for a fixed ______ of _________ times.
It uses statements ____ and _____ to determine what section of _____ is repeated and how many ____.
repeatedly, code, number, predetermined times
For example
This program would also print out a message six times:
for count = 1 to 6
print(“Coding is cool”)
next count
The first line of the program determines how many _____ the code is to be ______. It uses a ______, in this case count, known as the _______ variable, to keep track of how many _____ the code has been _______ so far. The variable is given a ______ value (in this case one) and an ____ value (in this case six).
Every time the code is iterated, the value of count _______ by one. At the end of the iteration, the value of count is _____ to see if it matches the ___ value. If the result is FALSE, the code _____ ____ to the _____ of the iteration and runs again. If it is TRUE, the iteration ____ and the program continues with the next line of code.
times, iterated/executed, variable, condition variable, times, executed, start, end,
increased, checked, end, loops back, start, ends
By using iteration, a program is simplified, less _____ prone and more ______. This is because
- There are fewer ____ of ____, meaning fewer ________ for typing _____ to creep in
- to increase or decrease the number of _______, all the programmer has to do is ______ the loop’s ___ value
error, flexible
lines, code, opportunities, errors
iterations, change, end
While loops test the ________ at the ________ of the loop. if the condition is met, the ____ within the loop is ______ before the program loops ____ to ____ the condition again.
condition, beginning, code, executed, back, test
This program would print out a message six times:
count = 0
while count < 6
print(“Coding is cool”)
count = count + 1
endwhile
The while statement defines the ____ of the loop. The ______ statement declares the ___ of the loop. A ______, in this case count, is used for the _______. The while statement also ____ the condition, in this case to see if the value of count is less than ___. If the result is TRUE, the code within the loop is ______, then the program loops ____ to the condition, which is _____ again.
The iteration continues until the condition test result is _____, at which point the loop ____ and the program executes the next line of code in sequence after the loop.
start, endwhile, end, variable, condition, tests, 6, executed, back, tested
FALSE, ends
Repeat condition-controlled loops works in the same way as while loops, BUT, the _______ is tested at the ____ of the loop (rather than the start like while loops)
condition, end
Repeat condition -controlled loop example
count = 0
repeat
print(“Coding is cool”)
count = count + 1
until count = 10
The repeat statement defines the ____ of the loop. The ____ statement tests the condition. Because the condition is tested at the ___, the code within the loop is always executed at least ____, even if the result of the test is ______.
start, until, end, once, FALSE
Condition-controlled loops can be written to continue forever. This is known as ______ loop.
Infinite loops can be created using either _____ or ______ loops
infinite
while, repeat
his program would run infinitely:
count = 10
repeat
print(“Coding is cool”)
count = count + 1
until count = 10
At the end of the loop, the value of the variable count will be 11. Because with each iteration the value of count increases by ___, count will never have the value ___, so the loop will run _______.
one, 10, infinitely
Nesting occurs when one programming ______ is included within ______.
It ______ the amount of _____ needed, whilst making it simple for a programmer to ______ and _____ the program.
construct, another
reduces, code, debug, modify
Nested selection
When using selection, the number of possible ____ at a _______ point can be _______ by including one selection within ______.
paths, decision, increased, another
This program uses nested selection:
age = int(input(“How old are you? “)
if age > 16 then
print(“You are old enough to drive a car and ride a moped!”)
else
if age == 16 then
print(“You are old enough to ride a moped!”)
else
print(“Come back when you are older!”)
endif
Endif
Here, there are two ______ that may be tested, resulting in _____ possible paths to follow. The _____ condition is only tested if the result of the first test is ______.
Nested selection can be built up over and over to include ____ possibilities and _____ for a program to follow. It allows for ______ decisions to be made.
conditions, three, second, FALSE
many, paths, complex decisions
This program uses nested selection:
age = int(input(“How old are you? “)
if age > 16 then
print(“You are old enough to drive a car and ride a moped!”)
else
if age == 16 then
print(“You are old enough to ride a moped!”)
else
print(“Come back when you are older!”)
endif
Endif
Here, there are two ______ that may be tested, resulting in _____ possible paths to follow. The _____ condition is only tested if the result of the first test is ______.
Nested selection can be built up over and over to include ____ possibilities and _____ for a program to follow. It allows for ______ decisions to be made.
conditions, three, second, FALSE
many, paths, complex decisions
Iteration can also be nested. This program uses two count-controlled for next loops, one within another, to print out the times table for all numbers from one to ten:
for x = 1 to 10:
for y = 1 to 10:
result = y * x
print(y, " * ", x, " = ", result)
next y
next x
For every iteration of x, y is iterated ten times.
.
This program uses condition-controlled while endwhile loops, one within another, to print out the times table for all numbers from one to ten:
x = 1
y = 1
while x < 11:
while y < 11:
result = y * x
print(y, " * ", x, " = ", result)
y = y + 1
y = 1
x = x + 1
For every iteration of x, y is iterated ten times.
.
A variable is a ______ ______ _______ that holds a value. The value held in the variable can _______ as the program is running
named memory address, change
An identifier is a _____ given to a ____ of a program, such as a _______, constant, function etc.
name, part, variable
Variables make it easy for a programmer to use _______ locations. The computer keeps _____ of which memory ______ the variable refers to. All the programmer has to do is remember the _______ the variable was given.
memory, track, location, identifier
Variables need to be _____ and ______ before a value is assigned to it. - This is known as ________ (ie declaring the variable)
created, identified, declaration
Assignment - giving a variable a _____. A variable must be assigned a _____ before it can be ____.
value, value, used
A constant allows a _____ to be assigned a _____. The value assigned to a constant can’t be _____ when the program is running
value, name, changed
Constants are useful because they are _______ and _______ once, but can be ______ to over and over again throughout the program.
They are used for values that are unlikely to \_\_\_\_\_\_ for example: Pi - const PI = 3.142
declared, assigned, referred
change
The two types of variables are
- G_____ variables
- ______ variables
Global variables
Local variables
A global variable is one that can be _______ and _______ throughout the program.
Usually a programmer has to ______ that the variable is a global. For example:
global ID = 75
accessed, changed
declare
Local variables are confined to a ____ or a _________. This has the advantage of the programmer being able to use the same variable _____ again and again for different ________.
loop, program, name, purposes
A local variable should not have the same _____ as a global variable. If this happens, the ______ of the global variable will be _______, causing the program to function _______.
name, value, changed, incorrectly
The 5 types of data types are
- I______
- F____
- C_______
- S______
- B______
Integer Float Character String Boolean
Integers are ______ ________,
Eg 27
whole numbers
Floats are _______ _______
Eg 27.5
decimal numbers
A character is a single _________ _________.
Eg N
single alphanumerical character
A string consists of one or more __________ ________.
Eg REVISE EDIOT
alphanumerical characters
Boolean could either be _____ or ______
Eg heheh not gonna say u tell meh
TRUE, FALSE
Different data types have ________
- ______ and ______ cannot be _____ together
- numbers held in ______ cannot be subject to _______ operations
limitations
Integers, floats, joined
strings, mathematical
Casting is _______ the data ____ of a ________.
str(68) returns “68”
int(“54”) returns 54
changing, type, variable
String Manipulation
It is usually possible to manipulate a string to provide ______ or to alter the ________ of a string
information, contents
Length
The length of a string can be determined using the ___ statement. This gives the _______ as an _____.
___(wordOne) - would give the answer _____, as there are _____ characters in the word “Computer”
len, length, integer
len(wordone), eight, eight
Character Position
wordOne = "Computer" wordTwo = "Science"
It is possible to determine which ________ features at a ________ within a string.
wordOne[2] - would give the answer “__, as “__” is the _____ character in the word “Computer” (remember computers start counting at zero)
wordOne[0:2] - would give “____”, the first _____ characters in the string
wordOne[3:3] - would give “____”, the three characters starting from position _____.
character/s, position
m, m, third
com, three
put, three
Character Position
wordOne = "Computer" wordTwo = "Science"
It is possible to determine which ________ features at a ________ within a string.
wordOne[2] - would give the answer “__, as “__” is the _____ character in the word “Computer” (remember computers start counting at zero)
wordOne[0:2] - would give “____”, the first _____ characters in the string
wordOne[3:3] - would give “____”, the three characters starting from position _____.
character/s, position
m, m, third
com, three
put, three
To concatenate strings means to ____ them to form another _____.
wordOne = "Computer" wordTwo = "Science"
For example
sentence = wordOne + “ “ + wordTwo - would give “_____________”
Alternatively, a string can be lengthened by ______ more ________. For example:
wordOne = wordOne + “ Science” - would result in the value of wordOne becoming “__________ ________”
join, string
Computer Science
adding, characters
Computer Science
An array a set of data _____ of the same ____, stored in a _______ in a computer ________.
Also known as a ____.
values, type, sequence, program
list
An array is like a collection of boxes, each of which is called an _______. Each element has a _______ in the array, and can hold a _____. The data in an array must all be of the same ____ ____.
This way, all data is stored under one ________ (name).
element, position, value, data type
identifier
Before an array can be used, it must be ______. To declare an array it must be given at least two properties:
- an \_\_\_\_\_\_\_\_ a \_\_\_\_ (the number of \_\_\_\_\_\_\_ it will hold)
For example:
array score[9] - would declare an array with ___ elements (zero to nine)
Once declared, the ______ and ________ of an array cannot be ______.
declared
identifier
size, elements
ten elements
name, structure, changed
Values are assigned to an element in an array by referring to the element’s ________. For example:
score[0] = 100 - would assign the value ___ to the ____ element in the array
Values in elements can be ________ at any point, simply by assigning another value to that element.
position
100, first
overwritten
Values are retrieved from an element in the array by again referring to the element’s _______. For example:
print(score[7]) - would display the _____ value held in the array. In the above example, the value would be ___ - Check bitesize
position, eight, 98
A two-dimensional array can hold more than ___ set of ____. This type of array is like a table, with data held in ____ and ________.
one, data, rows, columns
A two-dimensional array is declared using ___ values- the _______ of ___ and the ________ of _______.
Eg
array score = [1,9] - would give an array with ___ rows and ___ columns
two, number of rows, number of columns
two, ten
Data is _______ or retrieved by referring to an element’s ___ and ______ number.
assigned, row, column
