Digital Design Principles Flashcards
(25 cards)
what are the four key elements of computational thinking
Decomposition
Pattern Recognition
Abstraction
Algorithim
What is Decomposition
breaking a large complex problem into smaller sub-problems then examining each sub-problem to provide solution
What is pattern recognition
Observing key characteristics, patterns, and trends in data that is being considered
What is abstraction
removing specific details from problem that aren’t needed to solve it
What is an algorithm
Step-by-step set of instructions that specify how problem is going to be solved. flowcharts and pseudo-code can be used in algorithm design.
what are flow charts and pseudo code used for?
Methods of representing solutions to a prolem
What is a flowchart?
A graphical representation that includes special symbols and flow lines to represent solutions to a problem
What is pseudo-code
A set of English-like language-independent instructions that use keywords and control structures to represent the solution to a problem
Whats a sorting Algorithm
used by computers to sort data.
What can sorting Algorithms be evaluated in terms off
speed at which sorts large amount of data
amount of memory used during sorting process
number of comparisons carried out within sort
number of exchanges carried out during sort
stability sort (algorithm said to be stable if 2 objects with equal keys appear in same order in sorted output as they appear in input list)
What are the two types of sorting algorithms
Bubble sort
Insertion sort
What is a bubble sort
Simple sort method that repeatedly steps through list of data items; adjacent elements are compared and swapped if they are in in wrong order
What is an insertion sort
Simple sorting algorithm that builds a sorted sub-list one item at a time; the sub-list becomes the new sorted list
Properties of bubble sort
inefficient for sorting large amounts of data - time taken to sort is related to square of number of items to be sorted
Algorithm works by swapping adjacent data items until are in correct order
Data items “bubble” up through list until they are in correct order untill they are in correct order
Properties of Insertion sort
Adaptive - performance adapts to inital order of elements
Stable - retains relative order of same elements
requires constant amount of memory as entire sort occurs in internal memory
What is used to store data for sorting
An array
What is an array?
An array is a data structure that holds set of data items all of same type.
Given a name and data items or elements accessed using array name followed by position in array
Usually an array is zero indexed (first element accessed by example[0]
How does a bubble sort work
adjacent numbers compared if out of sequence they swap positions
at end of first pass largest value is in the last position in array
process is repeated. On second pass second largest value is moved to second last position on array and so on
How does an insertion sort work
Each comparison examines 2 adjacent elements in array of data when data item is swapped it’s added to sorted sub-list in correct order. at the end of one full pass the array of data is fully sorted
What is a search algorithm
used to locate and return data given certain critera
how does a linear search algorithm work
every data item is examined to see if it matches target value
average number of attempts required to find target value is half number of data items
could take on average ten attempts to find a target value in set of 20 data items
What is a linear search algorithm
simple search algorithm that compares every data item in a list to target value
what is a binary search
works on sorted list of data items
target value located by finding mid point location in list and comparing that to the target value.
This is repeated until target value is found or search space diminished to one item that isn’t target value
How does a binary search algorithm work
More efficient than linear search
only works on data already sorted
binary search first finds middle location
compares middle value to target value if target value not found search determiens if target value is below or above the middle lcoation value
process is repeated until diminished to one item or target found
