Computational Thinking Flashcards
Computational Thinking Techniques
-Pattern matching. -Abstraction. -Decomposition. -Algorithms
Pattern Matching
identifying patterns and recognising when 2 are similar
Abstraction
removing irrelevant details and reducing a problem down to essential elements
Decomposition
breaking a complex task down into smaller and simpler tasks
Algorithms
sequence of steps used to solve a problem
Continuous data
analog data. Has an infinite number of potential values. E.g. height 1.8 1.82 1.8254
Discrete data
distinct seperate values for data. E.g. Number of students in a room
Bit
1 binary digit. 0 or 1
Byte
8 bits. 0 to 255
Kilobyte
1024 bytes(because 2 to the power of ten is 1024)
Megabyte
1024 kilobytes (2 to the power of 20 bytes)
Converting binary to decimal
write table
Benefits of binary numbers in computers
-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
Hexadecimal
base 16. So positions are powers of 16
How to convert from decimal to hexadecimal
divide by 16 and write down number then divide the remainder by 16 and repeat from left to right
Why is hexadecimal useful
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
Do computers use hexadecimal
not but programmers use them as shorthand for binary as they are easier to understand and remember
Character set
collection of characters that are used for a purpose. English uses the roman character set.
ASCII
character set allowed for 128 characters using 7 bit binary
Extended ASCII
allowed 256 characters using 8 bit binary
Limitations of ASCII
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
Unicode
universal standard character set that is being extended regularly. Includes characters for all major languages and symbols like emojis
UTF-8
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
How UTF-8 works
uses 1 to 4 bytes for each character. Only uses necessary number of bytes for each character saving space
Importance of ASCII and Unicode
provide standard that is readable by other computers. Ensures outputs between them is consistent when communicating.
NIbble
4 bits
kilobit
1024 bits
elegance
desirable characteristic indicates solution is as simple as possible. Only has necessary features, is clear and works efficiently
comparing algorithms
key factor is efficiency (whichever does less work). This does not use time because that depends on computer executing algorithm
amount of work algorithm does
-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)
Ignoring constants
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
Linear complexity
when the amount of work done is n (or 5n or n +14) the work done is linearly proportional to the input size
Big O notation
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
Equivalence classes
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!)
constant time
when an algorithm always takes the same amount of time to complete. O(1)
why equivalence classes are important
-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)).
O(n^2) class
quadratic complexity algorithms. E.g. bubble sort because it features nested loops
algorithmic time complexity
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)
complexity cases
- Best Case: condition that allows algorithm to be completed in the shortest amount of time
- Worst Case: asituation which causes the longest possible running time of an algorithm. This is generally looked at when evaluating time complexity
- Average Case: expected performance of an algorithm
n^2 - n in big O notation
This is approximately the same size as n^2 so we write O(n^2)
worst case scenario for quicksort
-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
intractable problems
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
Examples of intractable problems
-traveling salesman
-knapsack problem
-subset sum
traveling salesman
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.
knapsack problem
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
Subset sum
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.
Heuristic
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.
Recursive algorithm
breaks down a problem into smaller problems that and then solves each of them in similar fashion. Typically uses recursive functions in code.
Worst case time complexity of quicksort
O(n^2)
Average case time complexity of quicksort
O(nlog(n))
Worst + Average case time complexity of bubble sort
O(n^2)
Worst + Average case time complexity of insertion sort
O(n^2)
Best case time complexity of insertion sort
O(n)
Worst + Average + Best case time complexity of selection sort
O(n^2)
