Brainscape's Knowledge GenomeTM

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


See full index

Computer Science > Unit 6 - Algorithms > Flashcards

Unit 6 - Algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What is an algorithm?

Computational thinking

A

An algorithm is a set of instructions for solving a problem or completing a task

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

What is abstraction?

Computational thinking

A

Abstraction involves removing unnecessary detail from a problem so that you can focus on the essential components

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

What is decomposition?

Computational thinking

A

Decomposition involves breaking down a large problem into smaller, more manageablesub-problems

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

What are advantages of decompostition?

Computational thinking

A
  • The problem becomes easier to solve when it consists of a number of small subtasks
  • Some may be reusable, saving development time
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the 2 types of searching algorithms?

Searching algorithms

A
  • Binary search
  • Linear search
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a linear search?

Searching algorithms

A

A linear search requires going through each item in the list, one by one

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

How does a binary search work?

Searching algorithms

Mark Scheme answer

A
  • Select middle number and ..
  • check if selected number matches target number
  • if searched number is larger, discard left half // if searched number is smaller, discard right half
  • Repeat until number found
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the 3 sorting algorithms?

Sorting algorithms

A
  • Bubble sort
  • Merge sort
  • Insertion sort
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How does bubble sort work?

Sorting algorithms

A
  • Start with the leftmost item
  • Compare it with the one next to it
  • If the one next to it is less, swap them
  • Repeat for all the other items
  • At the end of one pass through the list, the largest item is at the end of the list
  • Repeat the process until the items are sorted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How does insertion sort work?

A
  • This algorithm sorts one data item at a time
  • One item is taken from the list, and placed in the correct position
  • This is repeated until there are no more unsorted items in the list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How does merge sort work?

Sorting algorithms

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

Which sorting algorithm is fastest?

Sorting algorithms

A

The Insertion sort is much quicker than the Bubble sort, but the Merge sort is faster still

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

What is a variable?

Developing algorithms

A

A variable is a location in memory in which you can temporarily store a value such as a string or number

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

What are the 2 common tools to write an algorithm?

Developing algorithms

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

What are the 3 basic program stuctures?

Developing algorithms

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

What is a sequence?

Developing algorithms

A

A sequence is a series of steps which are completed one after the other

17
Q

What is selection?

Developing algorithms

A

Selection is the ability to choose different paths through a program

18
Q

What is iteration?

Developing algorithms

A

Iteration means repeating a part of a program (repeating or looping)

19
Q

How is a terminal represented?

Flowcharts

A

A curved rectangle for start + end

20
Q

How is an input/output represented?

Flowcharts

A

A parallelogram

21
Q

How is a decision repesented?

Flowcharts

A

A diamond with arrows for different choices

22
Q

How is the direction of flow represented?

Flowcharts

A

An arrow line

23
Q

How is a process represented?

Flowcharts

A

A rectangle

24
Q

How is a subroutine represented?

Flowcharts

A

A rectangle with lines o each end

25
Q

How is a sequence represented?

Flowcharts

A

In a flow diagram they are shown as process, input or output symbols shown one after the other

26
Q

How is selection represented?

Flowcharts

A

In flowcharts, decision symbols are used for selection

27
Q

How is iteration represented?

Flowcharts

A

In flowcharts, iteration is shown by using arrows that repeat a section of the flowchart. A decision will control whether more iterations are required.

28
Q

What are similarities between insertion and bubble sort?

A
  • Both produce a sorted list / array
  • Both need a temporary variable
  • Both swap values
  • Both use loops/iteration
  • Both (may) need multiple passes
29
Q

What is purpose of temporary variable in sorting algorithms?

A

stores data/value so it can be changed/swapped without being lost.

30
Q

Explain the purpose of the Boolean variable swaps in a bubble sort algorithm

A

record whether a swap has taken place or not, checked as condition to decide whether to repeat

Computer Science (7 decks)

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