Unit 1 - Computational Thinking and Problem Solving (copy)

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