Brainscape's Knowledge GenomeTM

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


See full index

Computer Science > Computational Thinking (I) - Algorithms > Flashcards

Computational Thinking (I) - Algorithms Flashcards

1
Q

What is computational thinking?

A

The steps you take to find the best solution to a complex problem

Before a problem can be tackled, the problem itself - and the ways in which it could be solved - needs to be understood

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

What are the three key techniques of computational thinking?

A

Decomposition

Abstraction

Algorithmic Thinking

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

Give an example of computational thinking when planning a visit to the cinema

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

What does the following show?

A

Pseudocode

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

What are algorithms?

A

Sets of instructions

In real life – recipes / directions / game rues

In computer science – often written as pseudocode

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

What is pseudocode?

A

Pseudocode should show an algorithm’s steps without worrying about the finer details (e.g. syntax)

It should be quick to write and then easily converted to a programming language

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

What is pseudocode not?

A

A programming language

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

What should pseudocode be like for it to be useful?

A

Readable

Easy to interpret

Not too vague

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

Write an algorithm in pseudocode to calculate the salary of a worker after a 10% pay rise

A

input salary

newsalary = salary x 1.1

output newsalary

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

Write an algorithm in pseudocode to check is a password is 6 characters long and different from the username of a user logging into a website. If invalid, it should say why

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

What is a flowchart?

A

A flowchart is a diagram that represents a set of instructions

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

What do flowcharts normally contain?

A

Flowcharts normally use standard symbols to represent the different types of instructions

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

What are the symbols of a flowchart used for?

A

Symbols are used to construct the flowchart and show the step-by-step solution to the problem

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

Name, draw the image and give the usage for common flowchart symbols

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

Draw a flow diagram to ask what the best subject is (trying again if it isn’t computer science)

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

What can flowcharts be used for?

A

Planning out programs

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

What can flowcharts show?

A

Sequences, Selections and Iterations

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

What is a sequence?

A

Sequence – only one way from the start to the end

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

What is a selection?

A

Selection – multiple ways from start to stop

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

What is an iteration?

A

Iteration – contains a loop allowing for a task to be repeated

21
Q

Draw a flowchart with a sequence

A
22
Q

Draw a flowchart with a selection

A
23
Q

Draw a flowchart with an iteration

A
24
Q

What are the two main types of algorithm search?

A

Linear search

Binary search

25
Q

Describe a linear search?

A

A linear search is the simplest method of searching a data set.

Starting at the beginning of the data set, each item of data is examined until a match is made. Once the item is found, the search ends

26
Q

Write the instructions for a linear search

A

Find out the length of the data set

Set counter to 0

Examine value held in the list at the counter position

Check to see if the value at that position matches the value searched for

If it matches, the value is found. End the search

If not, increment the counter by 1 and go back to step 3 until there are no more items to search

27
Q

What is the advantage / disadvantage of a linear search?

A

Simple (data does not have to be ordered)

Not efficient – if the search value is at the end of the list, the algorithm will need to go through all previous values first

28
Q

Describe a binary search

A

Start by setting the counter to the middle position in the list (if a match the search ends)

If the value at the midpoint is less than the value to be found, the list is divided in ½. The lower ½ of the list is ignored and the search keeps to the upper ½ of the list (and vice versa)

The search moves to the midpoint of the remaining items. The step above continues until a match is made or there are no more items to be found.

29
Q

What is the advantage / disadvantage of a binary search?

A

Much more efficient

Requires the list to be ordered

30
Q

Complete a linear search to find the value 2 in the list

A 
Position 0 (first item) is not value 2 – counter +1
Position 1 is not value 2 – counter + 1
Position 2 is not value 2 – counter + 1
Etc…
Position 5 is value 2 – stop search
31
Q

Complete a binary search to find the value 11 in the list

A

Midpoint = 8 (highest position) + 0 (lowest position) and dividing by 2 = 4

Midpoint = 8 (highest position) + 5 (lowest position) and dividing by 2 = 7 (r)

Midpoint = 7 (highest position) + 5 (lowest position) and dividing by 2 = 6

32
Q

What are the three types of algorithm sorting?

A

Bubble

Merge

Insertion

33
Q

Describe bubble sorting

A

Start at the beginning of the list.

Compare the first value in the list with the next one up. If the first value is bigger, swap the positions of the two values.

Move to the second value in the list. Again, compare this value with the next and swap if the value is bigger.

Keep going until the there are no more items to compare.

Go back to the start of the list

34
Q

In a bubble sort, what is each run through known as?

A

A pass

35
Q

Bubble sort the following (first two moves)

A
36
Q

What are the advantages of a bubble sort?

A

Simple algorithm

Efficient way to check for a list is in order – only one pass

Doesn’t use much memory

37
Q

What are the disadvantages of a bubble sort?

A

Inefficient to sort a list

Does not cope well with a very large list

38
Q

Describe merge sorting

A

A merge sort uses a technique called divide and conquer.

The list is repeatedly divided into two until all the elements are separated individually. Pairs of elements are then compared, placed into order and combined.

The process is then repeated until the list is recompiled as a whole.

39
Q

Complete the first divide and conquer of a merge sort for the following

A
40
Q

What does the following show?

A

Divide and conquer – merge sort

41
Q

What are the advantages of a merge sort?

A

Efficient and quicker than bubble / insertion with large lists

Consistent running time regardless of how ordered the items are in the original list

42
Q

What are the disadvantages of a merge sort?

A

Slower than other algorithms for small lists

Even if the list is already sorted still goes through the whole splitting and merging

Uses more memory than other sorting algorithms in order to create the separate lists

43
Q

Describe an insertion sort

A

Comparing values in turn, starting with the second value in the list.

If this value is greater than the value to the left of it, no changes are made. Otherwise this value is repeatedly moved left until it meets a value that is less than it. The sort process then starts again with the next value.

This continues until the end of the list is reached.

44
Q

Complete the first insertion sort for the following

A
45
Q

What does the following show?

A

Insertion sorting

46
Q

In an insertion sort, what happens when two adjacent values are compared?

A

If the second value is greater than the value to the left of it, no changes are made.

Otherwise this value is repeatedly moved left until it meets a value that is less than it.

47
Q

List the advantages of an insertion sort

A

Intuitive and easily coded – copes well with small lists

Sorting on original list (minimal memory requirements)

Quick to add items on ordered list and quick at checking

48
Q

List the disadvantages of an insertion sort

A

Doesn’t cope well with large lists

Computer Science (8 decks)

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