Chapter 7:Computational Thinking Flashcards
linear search
used to sort list and arrays
only option for unsorted data
Algorithm
is a list of steps that perform a task
Pattern matching
Identifying patterns and recognising when two patterns are similar
Decomposition
Breaking a complex task down into a set of smaller and simpler tasks
Abstraction
Ignoring irrelevant details and reducing a problem to its essential features
Computational Thinking
A way of approaching problems that is particularly useful in computing
Name two types of algorithms
Search and sort
Name two search algorithms
Linear search
Binary search
Algorithms should be:
Should be efficient
Consist of finite steps
Easy for people to understand
Clear purpose and flow
Intractable
no algorithm can solve them in a reasonable amount of time
What is the function of equivalence classes?
Allow data to be read on a graph
Allows to compare complexity between algorithms
Advantages of binary search
quicker and more efficient for larger and sorted data
Heuristics
rough estimate of answer
O(n)
linear
e.g. linear search
O(1)
less complex than O(n)
runs in “constant time”
O(n2)
more complex than O(n)
quadratic complexity
bit
basic unit of information in computing is 1 or 0
byte
made of eight bits.
Each represents a single character
ASCII
a standard character set that represents 256 character using one byte (8 bits)
Character set
a collection of characters with a specific purpose
Unicode
universal standard character set
first 128 characters of Unicode are the same as ASCII
UTF-8
UTF-Universal Transformation Format
8-eight bit blocks represent a character
used to encode unicode characters
