Studied by 0 people
How can you route pieces of information across a network to the other side of the world?
Routing items of data around the world requires many different protocols. This is a result of decomposing the problem into smaller tasks.
How can you make the images in a computer game look more realistic?
Problems such as 'How can you make the images in a computer game look more realistic?' need abstractions, where we consider the important components of a realistic image
How can you program a computer to work out the school timetable?
There may be many different algorithms that solve the same problem
How can you search 1,000,000 items quickly?
Some problems such as 'how can you search 1,000,000 items quickly?' require a specific algorithm to be considered
what is an algorithm
An algorithm is a set of instructions or a step-by-step solution for solving a problem or completing a task. Algorithms can be designed using pseudocode and flow charts. They are written using statements and expressions.
what are a few examples of some everyday tasks that could need an algorithm?
Making a chocolate cake, Summing the numbers 1 to 1000, Building a Lego model
what is algorithmic thinking?
a logical way of getting from the problem to the solution by identifying the steps involved in solving a problem.
what is divide and conquer?
a technique that splits a big problem into smaller parts on each iteration.
what is an example of a divide and conquer search algorithm?
a binary search algorithm. in binary search, on a sorted array of numbers, we divide (decrease) the array of numbers (search space), conquer the sub problems by recursively looking at the middle point for our target and splitting until we find our target the base case condition.
what is abstraction?
abstraction involves focusing on the important information only, ignoring irrelevant detail
how would a computer 'roll the dice'?
it will depend on the problem being solved as to what is and isn't important
a computer game may need to show a graphical representation of a dice, but they may be able to abstract away all the details about the surface it rolls onto and the physics of the bounce
many programs just need a random number. in which case they don't need to worry about how the dice appears, its weight or how the spots are arranged - they can just find a random number with one line of programming code
what is decomposition?
breaking down a complex problem or system into smaller, more manageable parts. then the sub-problems can be broken down further until each small task is manageable.
how would you decompose a dice game?
you need to think of the main tasks that need to be performed - for example:
display the rules
establish whether this particular game is to be a two-player (or more) game, or one person against the computer
display the board if there is one
play the game
display the result when the game is over
what are some advantages of decomposition?
the problem becomes easier to solve when it consists of a number of small subtasks or subprograms
some subprograms may be reusable in other programs, saving development time
what are structure diagrams?
a structure diagram is used to show how a problem is broken down. it will show subtasks which accomplish an identifiable task and their links to other subtasks
what are a few benefits of subprograms?
subprograms can be reused many times in a program. This reduces the amount of code needed.
code will be easier to maintain and have fewer bugs It makes it easier to adapt the program.
What is a variable?
A variable is a location in memory in which you can temporarily store a value such as a string or a number
what are the 5 flowchart symbols?
slanted rectangle for input/output
what are the 3 program structures?
Sequence: A sequence is a series of steps which are completed one after the other
Selection: Selection is the ability to choose different paths through a program
Repetition / Iteration: Iteration means repeating a part of a program. It is also referred to as repetition or looping. A user input/decision will control whether more iterations are required
what are the 3 types of iteration?
Count-controlled repetition: The repetition occurs a specific number of times - e.g. for i in range(5):
Condition-controlled repetition: The repetition occurs whilst a condition is true - e.g. while score < 10:
Iteration over a data structure: The iteration is carried out to each item in a data structure such as a list or record - e.g. for item in list:
what are the 5 data types?
Integer: a whole number
Floating point: a number with a decimal point
Boolean: Can only be True or False
Character: A single alphabetic or numeric character
String: One or more characters enclosed in quote marks
what is pseudocode?
Pseudocode is an informal written description of a program that does not require strict programming syntax. It allows a programmer to focus on the logic of the algorithm without being distracted by the exact syntax of the programming language.
pseudocode for a program which asks the user to enter the cost of two items, adds the two costs and if the cost is greater than £10.00, displays a message "Sorry, too much". Otherwise it displays the change due from £10.00
item1 = input("Please enter price of first item:") item2 = input("Please enter price of second item:") total ← item1 + item2 if total > 10: print("Sorry, too much") else: change = 10 - item1 - item2 print("Change from £10.00 is £", change)
what are arrays and lists?
An array is a data structure that allows you to hold many items of data which is referenced by one identifier. All items of data in the array must be of the same data type. The length is fixed. However, arrays do not exist in Python/PLS. Instead, Python uses Lists Python lists don't need to store the same data type, but this is. advised. They also don't have a fixed length
what are indexes?
Indexes help retrieve the data quicker, if implemented correctly. Information can be read from or added to the array using the index number. Indexes in most languages start at 0 not 1.
How would you write a FOR loop to output all the usernames in a list?
for user in Usernames: print(user) OR for i in range(0,len(Usernames)): print(Usernames[i])
what are linear search algorithms?
they are brute force search algorithms. they go through all possible choices until a solution is found. The time complexity of a brute force algorithm is often proportional to the input size. Each item in the list is checked against the search item in order. Brute force algorithms are simple and consistent, but very slow.
what are bubble sort algorithms?
Each item in a list is compared to the one next to it, and if it is greater, they swap places. At the end of one pass through the list, the largest item is at the end of the list. This is repeated until the items are sorted.
_________ allow many data items to be stored under one _________. Each item in the array can be accessed by its array _________. Indexes start at _________. By using a _________ we can easily loop through an array. Arrays have a _________ and all items in the array have the same _________. Python _________ do not have these restrictions.
Arrays allow many data items to be stored under one identifier. Each item in the array can be accessed by its array index. Indexes start at zero. By using a FOR loop we can easily loop through an array. Arrays have a fixed length and all items in the array have the same data type. Python lists do not have these restrictions.
In a sorted list of 1,000,000 items, how many items will have to be examined to establish that an item is NOT in the list?
With a binary search, only 20 items have to be examined to discover that an item is not in the list That's because 1,000,000 is less than 2²º but greater than 2¹⁹ If the list were unsorted, 1,000,000 items would need to be checked to prove that the item is not in the list With a linear search, 1,000,000 items would need to be examined
what are binary search algorithms?
This algorithm only works on a sorted list. The middle item of the list is first checked. If the item searched for is less than this item the right of the list is discarded, and a binary search is carried out on the left of the list.
what are 5 types of data that people need sorted?
Index cards/records of customer details Directories and dictionaries House numbers Library books Stock in a warehouse
Reasons why a computer will work more efficiently with sorted lists?
Computers can use a binary search with sorted lists which is far more efficient than a linear search
what are merge sort algorithms?
This is much more efficient than the bubble sort
The basic steps are: Divide the unsorted list in two Continue to divide these lists into two until there is just one item in each list Now merge each list back until there is only one list remaining, which will be the fully sorted list
what are binary situations?
Binary situations are common in daily life and can refer to things that can be in only one of two states
what does binary 1 represent?
true
what does binary 0 represent?
false
what are the 3 main logic gates?
AND gate OR gate NOT gate
AND gate
both inputs need to be true for the output to be true
OR gate
only one input needs to be true for the output to be true
NOT gate
also called an inverter - will output the opposite of the input
Note
Flashcard