Brainscape's Knowledge GenomeTM

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


See full index

+ CPSC 100 > Algorithms > Flashcards

Algorithms Flashcards

1
Q

What is hardware?

A

physical devicecs

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

What is software?

A

programs that run on hardware to implement applications

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

How has computer storage changed?

A

computers have gotten much better at storing information in smaller spaces

changed computing – much larger number of pieces of data in a device

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

What are the 4 types of computer memory?

A

registers
caches
RAM
hard drive

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

What does the actual work in computers?

A

CPU/”chip” actually does the work

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

What memory does the CPU/”chip” have?

A
  • registers

- several layers of caches

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

What are registers?

A

hold the data that the computer is actively working with

very small, and very fast to access

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

What are caches?

A

fast memory on CPU/chip

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

What memory does the computer have?

A
  • RAM

- hard drive/solid state drive (ssd)

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

What is RAM?

A

random access memory

  • fairly fast and small
  • slower to access + a bit bigger than cache
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Where is the RAM?

A

on motherboard, NOT on chip

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

Where is the hard drive/solid state drive (ssd)?

A

NOT on chip

NOT on motherboard

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

How fast is access to the hard drive/solid state drive (ssd)?

A

very slow to access, but generally much bigger

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

What is Moore’s Law?

A

computer speed and memory on a chip will double every 18 months to 2 years

1965: number of transistors on chips doubles every year
1975: number of transistors on microchips doubles every 2 years
2019: Moore’s law no longer holds true – the trend persists, but it is slowing down

(making chips smaller also makes them faster – but this has come to an end)

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

How big are transistors?

A

around 10 nm

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

Why is it becoming harder to double the number of transistors on a chip?

A
  • harder to work on environments that are that small
  • atom size – we are limited by the size of an atom
  • battery cells too close together – overheating
  • software is not the problem
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is computing speed up due to?

A
  • hardware

- software

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

What is an operating system?

A

special kind of software that allows the other software to run (ie. Windows, Mac OS)

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

How does software work?

A

programmers write down algorithms in a special language that the computer can understand

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

Evaluating Algorithms - Sequential Algorithm

A

-

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

Evaluating Algorithms - Breaking Bad Algorithm

A

-

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

What do signal algorithms use?

A

decomposition

abstraction

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

What must occur before sorting?

A

swapping

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

What are the 3 ways to evaluate algorithms?

A
  • validity
  • time (copies, swaps, comparisons)
  • space (memory slots for cards, markers, dividers)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Simple Sort vs. Selection Sort vs. Insertion Sort

A

on average, Selection Sort and Insertion Sort have roughly ½ as many comparisons, and use roughly ½ as much space as Simple Sort

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

Quick Sort and Merge Sort

A

even faster

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

What is a classifier?

A

algorithm that maps input data to a specific category, derived from patterns or correlations from data

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

What is training data?

A

data that classifiers learn the patterns that has the “answer”

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

What is test data?

A

some training data that is held back to check and see if the classifier works

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

What do classifiers do?

A

apply patterns to new data with no “answer”

31
Q

What is classification?

A

general class of algorithms

32
Q

What is the idea behind classification?

A

want to use patterns and/or correlations to make decisions

33
Q

What are classifiers?

A

algorithms that perform classification, and are specific

34
Q

What are the steps of classification?

A
  1. start with the data you have
  2. split data into training and test sets
  3. build classifier (find pattern in training set)
  4. use classifier on test data - after you come up with a classifier that seems to do okay with your training data, you use it on your test data to see what kinds of decisions it makes
  5. calculate accuracy - if results of your classifier match up with decisions you made in your test data, it’s looking good
35
Q

What is a tree?

A

collection of nodes that…

  • one node is the designated root
  • a node can have zero or more children; a node with zero children is a leaf
  • all non-root nodes have a single parent
  • edges denote parent-child relationships
  • nodes and/or edges may be labeled by data
36
Q

How are rooted trees in CS often, but not always, drawn?

A

with root on top

37
Q

What is a decision tree?

A

trees whose node labels are attributes, and edge labels are conditions

38
Q

How do you build decision trees from training data?

A

look for the best way to reduce entropy

39
Q

How do you determine entropy?

A
  • if all are ‘yes’ or all are ‘no’ then entropy would be 0

- if there is a mix between ‘yes’ and ‘no’ then entropy is the total number of ‘yes’ and ‘no’

40
Q

Building Decision Trees from Training Data

A

-

41
Q

What is the purpose of a decision tree?

A

to decide which class(es) a set of objects belong to

42
Q

Will a greedy algorithm for creating a decision tree always create the most optimal solution? Why or why not?

A

no

optimal choice for now may not be the most optimal choice in the long run

43
Q

What is a greedy algorithm?

A

algorithm that makes choices based on what is the best choice at that current moment

does not consider what would be the best choice in the long run, although sometimes greedy algorithms give you the same answer as what would be the best choice in the long run

44
Q

Which memory type has the highest access speed?

A

CPU registers

45
Q

List the memory types from slowest to fastest access speed.

A

disc storage (virtual RAM, hard drive) - slowest

physical RAM (main memory)

level 2 cache

level 1 cache

CPU registers

46
Q

List the memory types in order from lowest to highest capacity.

A

CPU registers

level 1 cache and level 2 cache

physical RAM (main memory)

disc storage (virtual RAM, hard drive)

47
Q

What are CPU registers for?

A

used for current tasks that the computer is running, and are often overwritten as the computer switches between tasks

48
Q

What may happen to values that CPU registers hold?

A

may eventually get written to memory and stored permanently, but it will not store any values on a permanent basis

49
Q

What do hard drives do?

A

house all the data on your computer on a permanent basis

that’s why you can turn computer on and off and still retain access to the data you had previously

50
Q

What does CPU stand for?

A

central processing unit

51
Q

What is the brain of the computer system? Why?

A

CPU

responsible for telling the computer which instruction it needs to execute

52
Q

What does RAM store?

A

frequently used values

53
Q

What does RAM do?

A

helps increase overall speed of computer tasks since computer does not need to go to the hard disk to get the values it needs

(getting a value from the hard drive is much slower than getting it from RAM)

54
Q

What is the motherboard?

A

circuit board that allows other parts of computer (like CPU and memory) to communicate with each other

55
Q

What are hard drive disks (HDD)?

A

where data is stored on a long term basis

56
Q

What do hard drive disks (HDD) do?

A

allows you to restart or power on computer without losing all values you were working with previous to restarting/powering on

57
Q

What do operating systems do?

A
  • provide platform for applications (bridge between additional software/applications and computer’s hardware)
  • manage computer’s resources (CPU, memory, peripherals)
  • establish user interface (icons, windows, menus)
58
Q

What is the connection between the operating system, software applications, and hardware?

A
  • operating system has instructions that tell hardware what to do
  • software applications are built on top of operating system, and tell operating system what to do in order to run the software
59
Q

What are peripherals?

A

anything connected to your computer such as your mouse, keyboard, printer, etc.

60
Q

What is a transistor?

A

semiconductor device used to amplify or switch electronic signals and electrical power

61
Q

When is fairness a non-issue?

A

for unambiguous tasks

62
Q

What is bias?

A

prejudice in favour of or against one thing, person, or group compared with another, usually in a way considered
to be unfair

63
Q

When do we tend to see bias?

A

for ambiguous tasks

ie. shows
higher hotel prices
to Mac users as
compared to PC
users
ie. rate of getting
misidentified by a
facial recognition
algorithm goes up as
the colour of your
skin becomes darker
64
Q

What are unambiguous tasks?

A

tasks in which there is a clear input, output, and way to evaluate

65
Q

What are ambiguous tasks?

A

tasks in which the input is variable, the mode of evaluation is subjective, and the output is clear or variable

66
Q

Do computers have bias?

A

computers are susceptible to bias that humans have because humans are still the ones collecting data and feeding the algorithm

67
Q

What is the Garbage In, Garbage Out (GIGO) principle?

A

flawed (nonsense) input data produces nonsense output

68
Q

What classifier is fairest?

Max Profit Rationale

A

drops least amount of people, makes most money

69
Q

What classifier is fairest?

Demographic Parity and Equal Opportunity Rationale

A

relatively higher profit while kind of decreasing gap between loan threshold of two different demographics

70
Q

What classifier is fairest?

Equal Opportunity Rationale

A

has highest true positives (best)

71
Q

What classifier is fairest?

Group Unaware Rationale

A

it’s unethical to discriminate based on something racial or similar types of information to that

72
Q

Should sensitive information be considered?

A

yes - fairness through awareness

sometimes, in order to be
fair, it is important to make use of sensitive information…

73
Q

What does fairness mean?

A

similar people are treated similarly

+ CPSC 100 (9 decks)

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