Brainscape's Knowledge GenomeTM

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


See full index

10B/Cp1 21-22 > 1 Fundamentals Of Algorithms > Flashcards

1 Fundamentals Of Algorithms Flashcards

1
Q

What is Abstraction?

A

Abstraction is the technique that simplifies a problem by removing unnecessary details so you can focus on the important parts that are relevant to the problem

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

What are two examples of Abstraction?

A

Maps and Money

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

How are Maps an example of Abstraction?

A

Maps are an example of Abstraction as they leave out irrelevant information and only leave key parts such as roads and landmarks

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

How is money an example of Abstraction?

A

Money is a type of Abstraction as it is just an abstract concept. Money has no value but represents the value of goods and services.

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

What is decomposition?

A

Decomposition is the breaking down of a complex problem into smaller, more manageable, sub-problems. Each sub-problem can be solved individually, before the sub-solutions are combined to solve the original problem

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

What are the advantages of Decomposition?

A

Decomposition allows large teams to work on a part of the problem and work on it.
Decomposition allows extremely hard problems to be solved easily by splitting it up into simple tasks

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

What are Hierarchy or Structure Charts?

A

Hierarchy or Structure Charts are used to visually represent breaking a large problem down into the smaller parts that make it up.
Each box represents a smaller problem to be solved.
Lines show which bigger problem the box is a part of.

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

What is Algorithmic thinking?

A

Algorithmic thinking is the way of solving problems by producing algorithms.

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

What is an algorithm?

A

An algorithm is a reusable set of instructions that solve a given problem

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

How do we represent algorithms in computing?

A

We mainly represent algorithms as Pseudocode or Flow diagrams

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

What is Pseudocode?

A

Pseudocode is a way to write out algorithms using code-like statements. It is intended to be readable and easy to understand.

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

What is the purpose of Pseudocode?

A

Pseudocode is used to plan algorithms, focusing on logic and steps rather than language specific syntax

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

Can Pseudocode be run on a computer?

A

No as it isn’t an actual programming language

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

What are flow diagrams?

A

Flow diagrams are used to visually represent the steps that make up an algorithm

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

What do the arrows in a flow diagram represent?

A

Arrows in a flow diagram represent the flow of control, or what to execute next.

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

What is an oval used for in a flow diagram?

A

An oval is used for the start and end of a process

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

What is a rectangle used for in a flow diagram?

A

A rectangle is used to represent a process

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

What is a parallelogram used for in a flow diagram?

A

A parallelogram is used to represent an input or an output

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

What is a diamond used for in a flow diagram?

A

A diamond is used to represent a decision.

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

How many arrows comes out of a decision?

A

Two

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

What are some tips for interpreting algorithms?

A
  • Look out for Identifiers
  • Identify Inputs and Outputs
  • Examine Output Messages
  • Look for comments
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are identifiers?

A

Identifiers are the names of constants, variables and subroutines. They give a strong clue about the purpose of an algorithm

23
Q

How can you use output messages to help interpret algorithms?

A

Output messages often format the result of an algorithm in a human readable way.

24
Q

How can you use comments to interpret algorithms?

A

Comments are descriptions of the code. Comments will often state the purpose of a given algorithm. They are often the clearest method to identify an algorithm.

25
Q

What are some common mistakes that lead to the algorithm being incorrect?

A
  • Incorrect operators
  • Incorrect identifiers
  • Missing Processes
26
Q

What can be identifiers?

A
  • Variable names
  • Constant names
  • Subroutine names
27
Q

What could happen if there are missing processes?

A

If there are missing lines of code, there could be issues such as infinite loops where the code never ends

28
Q

What is a trace table?

A

A trace table is a technique used to test algorithms or computer programs for logic errors that occur while the algorithm or program executes. The trace table simulates the flow of execution

29
Q

Why should you use a trace table to complete an algorithm?

A

You can use the trace table to keep track of the value of each variable and carefully follow through the code till the end.

30
Q

What does completing the algorithm ask you to do?

A

Completing the algorithm means you should state the output of the algorithm

31
Q

What is the most common operator mistake?

A

> compared to >=

32
Q

How do you draw a trace table?

A

First, you draw a table with one column per variable.
Then, you go through the algorithm line by line, updating values of the variables.
Finally, you read off the output from the table at the end of the algorithm

33
Q

What is searching?

A

Searching is finding a certain value in a set of other values

34
Q

What is search algorithm?

A

A search algorithm is a set of instructions for finding a specific item of data within a data set.

35
Q

Why should computers be efficient in finding data?

A

Computer systems can store and process billions of pieces of data so it is vital that computers can find the information they need efficiently.

36
Q

What is effective searching?

A

An effective search is one which will always either find the solution or determine that the target data is not present.

37
Q

What is an efficient search?

A

An efficient search will find the solution quickly regardless of the location within the data set.

38
Q

What are the two common search algorithms?

A

The two common search algorithms are Linear search and Binary search

39
Q

How does a linear search work?

A

A linear search would work from one end to the other in a data set checking each piece of data to find the solution.

40
Q

What is linear search in pseudocode?

A 
for item in dataset
. if item = target then
. .return true
. endif
endfor
return false
41
Q

What are the pros and cons of linear searching?

A

Pro: Very easy to implement
Con: Slow on a long list

42
Q

How does a binary search work?

A

You find the middle of then dataset. If the middle value is greater than the target then, repeat it on the first half of the dataset.
If the middle value is lesser than the target, then repeat on the second half of the dataset.
Keep repeating, until the middle value is the target. If it is the middle value, then we have found the target.
If not, stop repeating once the size of our dataset is zero.

43
Q

What is binary search in pseudocode?

A 
dataset = [.....]
min = 0; max = len(dataset);
while (min target then
. . max = midpt - 1
. else if dataset[midpt] < target then
. . min = midpt + 1
. endif
endwhile
return False
44
Q

What are the pros and cons of binary search?

A

Pro: Faster than linear search on a large dataset.
Con: Dataset must be sorted before starting.

45
Q

What are Sorting Algorithms?

A

Sorting algorithms are a set of instructions to arrange a dataset into a particular order.

46
Q

What are the two Sorting algorithms required to learn?

A

Bubble sort and Merge Sort

47
Q

What is an efficient sort?

A

An efficient sort algorithm is one which can sort a dataset in a short time.

48
Q

How does bubble sorting work?

A

Compare the first two items of the dataset:
If they are in the wrong order, swap them.
Continue for the rest of the cards in the deck.
Repeat the whole process, until a pass with no swaps happens.

49
Q

What is a bubble sort in pseudocode?

A 
repeat
.swapped = False
.for i = 1 to n-1
. if A[i - 1] > A[i] then
. .swap(A[i -1],A[i])
. .swapped = True
. endif
.endfor
until NOT swapped
50
Q

What are the pros and cons of bubble sort?

A 
Pros:
Easy to implement
Does not use much memory
Cons:
Poor for efficiency
51
Q

How does merge sort work?

A

Split the lists into lists of size one.
Merge each pair of sublists by comparing the first value of each list and putting the smaller value into the new list first.
Continue merging until there is only one list.

52
Q

What are the Pros and Cons of merge sort?

A 
Pros:
A very efficient algorithm
Cons:
Can be slower for small lists
Needs additional memory
53
Q

When is it a bad time to use merge sort?

A

On a small list which is unlikely to grow

10B/Cp1 21-22 (3 decks)

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