Computational Thinking Flashcards

Question

Importance of ASCII and Unicode

Answer 1

**provide standard** that is **readable by other computers.** Ensures **outputs between them is consistent** when communicating.

Answer 2

desirable characteristic indicates solution is as **simple as possible**. Only has necessary features, is clear and works efficiently

Answer 3

key factor is efficiency (whichever does less work). This does not use time because that depends on computer executing algorithm

Answer 4

-depends on input size -depends on specific properties of input data( e.g. no 17's or all 17's) -not affected by small constant numbers of operations(e.g. +3)

Answer 5

done because they have no significant impact because its the variable that actually changes the operation size. In 3n the 3 has little significance compared to n

Answer 6

when the amount of work done is n (or 5n or n +14) the work done is linearly proportional to the input size

Answer 7

describes algorithmic time complexity. always features n the input size. Tells us how complexity of an algorithm grows as input grows. Usually describes worst case complexity of a program. Also can describe best and average case. In Big O, The dominant term is the highest order of n (e.g. between n and n^2 it would be n^2) so you'd write O(n^2)

Answer 8

**groups algorithms** that have an equivalent(more or less the same) complexity, meaning they grow at similarly. From least most complex: O(1/n^2), O(1/n), O(1), O(logn), O(n), O(n logn), O(n^2), O(2^n), O(n!)

Answer 9

when an algorithm always takes the same amount of time to complete. O(1)

Answer 10

-allow us to **see algorithms in the same class** -**quantify the difference in complexity** between algorithms in a different class -**Prevent wasting time looking for better algorithm** because the best equivalence class can often be proven mathematically. (e.g. for linear search of a list there is no better algorithm than O(n)).

Answer 11

quadratic complexity algorithms. E.g. bubble sort because it features nested loops

Answer 12

how long an algorithm would take to complete given an input of n. It is the **Execution Time** of an algorithm which is independent of human measures of time(Seconds). Often expressed using **Big O notation** to provide the best, worst and average time taken to complete an algorithm

Answer 13

1. Best Case: condition that allows algorithm to be completed in the **shortest** amount of time 2. Worst Case: asituation which causes the **longest** possible running time of an algorithm. **This is generally looked at when evaluating time complexity** 3. Average Case: **expected** performance of an algorithm

Answer 14

This is approximately the same size as n^2 so we write O(n^2)

Answer 15

-1.) keep picking the largest number as the pivot. Each below piv list will have all numbers except the last pivot -2.) Each loop will have to make one less comparison than the last. -3.) This creates a scenario with [ (n-1)+(n-2)+...+2+1 ] comparisons made by the algorithm. -4.group the comparisons into pairs like [ (n-1)+1] they will cancel out to become just n -5.) there will be (n-1)/2 total pairs that create n -6.) therefore ((n-1)/2) X n = (n^2 - n)/2 n^2 is the highest order term therefore quicksort has O(n^2) time complexity

Answer 16

no algorithm exists that can solve them in a reasonable amount of time. May be solvable with low number of possibilities but becomes extremely difficult as number of possibilities increases

Answer 17

-traveling salesman -knapsack problem -subset sum

Answer 18

salesman needs to visit n towns. He starts at home and knows the distance between all the towns. He needs to find the shortest route between all the towns and return to home. You have to check all O(n!) possible solutions to know which would be the shortest route.

Answer 19

knapsack can only hold certain weight. You have n items with particular weights and price values. You must make the contents of the knapsack as valuable as possible without exceeding the weight limit. No algorithm to solve it

Answer 20

You have a set of n numbers. You have a target number. You must find all the subsets of the set which add up to the target.

Answer 21

a **"rule of thumb"**. Produces an **approximate yet usable** solution to a problem. Often involve **small changes that sacrifice precision**. Useful when you need a **solution to an intractable problem**. Best applied when consequences of assumptions can be known and understood.

Answer 22

**breaks down a problem into smaller problems that and then solves each of them in similar fashion**. Typically uses recursive functions in code.

Answer 23

O(nlog(n))

Answer 24

JIS X 0201 for basic japanese characters encoded in 7 bit and later 8 binary encoding. Dominant before Unicode replaced it.

Answer 25

Has two discrete values (ON/OFF). In electrical circuits these are represented by voltages (5V = ON, 0V = OFF) E.g. pushbutton, switch, keyboard, keypad

Answer 26

Have any value within a certain range. Values constantly vary. Represent continuous data. E.g. temperature, sound, light, CO2 sensors

Answer 27

1. Infinite tape (can hold symbols usually 1, 0 or B) 2. Tape head (that reads and writes symbols on tape moving left or right) 3. Transition Table (set of rules that define how the machine changes its state, reads/writes symbols, and moves the tape head)

Computational Thinking Flashcards

(58 cards)