Computational Thinking

Question 1

Computational Thinking Techniques

Answer 1

-Pattern matching. -Abstraction. -Decomposition. -Algorithms

Question 2

Pattern Matching

Answer 2

identifying patterns and recognising when 2 are similar

Question 3

Abstraction

Answer 3

removing irrelevant details and reducing a problem down to essential elements

Question 4

Decomposition

Answer 4

breaking a complex task down into smaller and simpler tasks

Question 5

Algorithms

Answer 5

sequence of steps used to solve a problem

Question 6

Continuous data

Answer 6

analog data. Has an infinite number of potential values. E.g. height 1.8 1.82 1.8254

Question 7

Discrete data

Answer 7

distinct seperate values for data. E.g. Number of students in a room

Question 8

Bit

Answer 8

1 binary digit. 0 or 1

Question 9

Byte

Answer 9

8 bits. 0 to 255

Question 10

Kilobyte

Answer 10

1024 bytes(because 2 to the power of ten is 1024)

Question 11

Megabyte

Answer 11

1024 kilobytes (2 to the power of 20 bytes)

Question 12

Converting binary to decimal

Answer 12

write table

Question 13

Benefits of binary numbers in computers

Answer 13

-simple and quick to carry out operations for computers.
-binary signals are less affected by noise than others.
-easy to make exact copies of digital info

Question 14

Hexadecimal

Answer 14

base 16. So positions are powers of 16

Question 15

How to convert from decimal to hexadecimal

Answer 15

divide by 16 and write down number then divide the remainder by 16 and repeat from left to right

Question 16

Why is hexadecimal useful

Answer 16

provides a way of representing numbers using fewer digits. Only uses 2 digits can represent numbers up to 255 which would require 8 digits in binary

Question 17

Do computers use hexadecimal

Answer 17

not but programmers use them as shorthand for binary as they are easier to understand and remember

Question 18

Character set

Answer 18

collection of characters that are used for a purpose. English uses the roman character set.

Question 19

ASCII

Answer 19

character set allowed for 128 characters using 7 bit binary

Question 20

Extended ASCII

Answer 20

allowed 256 characters using 8 bit binary

Question 21

Limitations of ASCII

Answer 21

only set number of characters(128 / 256) that did not include non-roman character sets for languages like Chinese or Russian. Or symbols like emojis

Question 22

Unicode

Answer 22

universal standard character set that is being extended regularly. Includes characters for all major languages and symbols like emojis

Question 23

UTF-8

Answer 23

Unicode Transformation Format. Uses 8 bit blocks to represent a character. Method for encoding to save space taken up by unicode. Backwards compatible with ASCII

Question 24

How UTF-8 works

Answer 24

uses 1 to 4 bytes for each character. Only uses necessary number of bytes for each character saving space

Question 25

Importance of ASCII and Unicode

Answer 25

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

Question 26

NIbble

Answer 26

4 bits

Question 27

kilobit

Answer 27

1024 bits

Question 28

elegance

Answer 28

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

Question 29

comparing algorithms

Answer 29

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

Question 30

amount of work algorithm does

Answer 30

-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)

Question 31

Ignoring constants

Answer 31

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

Question 32

Linear complexity

Answer 32

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

Question 33

Big O notation

Answer 33

describes algorithmic time complexity. always features n the input size. Tells us how complexity of an algorithm grows as input grows. Describes worst case complexity of a program

Question 34

Equivalence classes

Answer 34

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!)

Question 35

constant time

Answer 35

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

Question 36

why equivalence classes are important

Answer 36

-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)).

Question 37

O(n^2) class

Answer 37

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

Question 38

algorithmic time complexity

Answer 38

how long an algorithm would take to complete given an input of n. Independent of human measures of time(Seconds). The dominant term is the highest order of n (e.g. between n and n^2 it would be n^2)

Question 39

complexity cases

Answer 39

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

Question 40

n^2 - n

Answer 40

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

Question 41

worst case scenario for quicksort

Answer 41

-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

Question 42

intractable problems

Answer 42

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

Question 43

Examples of intractable problems

Answer 43

-traveling salesman
-knapsack problem
-subset sum

Question 44

traveling salesman

Answer 44

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.

Question 45

knapsack problem

Answer 45

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

Question 46

Subset sum

Answer 46

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.

Question 47

Heuristic

Answer 47

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.

Question 48

Recursive algorithm

Answer 48

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

Question 49

Worst case time complexity of quicksort

Answer 49

O(n^2)

Question 50

Average case time complexity of quicksort

Answer 50

O(nlog(n))

Question 51

Worst + Average case time complexity of bubble sort

Answer 51

O(n^2)

Question 52

Worst + Average case time complexity of insertion sort

Answer 52

O(n^2)

Question 53

Worst + Average case time complexity of insertion sort

Answer 53

O(n^2)

Question 54

Worst + Average + Best case time complexity of selection sort

Answer 54

O(n^2)