Computation Flashcards
What is the definition of algorithm?
Set of instructions that can be followed to perform a task
How do you break down a problem?
- Does the problem have different levels
- Can it be broken down intol sections
- Can the sections be broken down further
- Each low level problem should be a single task
What is the sequence programing construct?
DO one statment after the other in order
What is the selection programming construct?
Do a set of instructions based on a condition
Allows for code to make choices
What is the iteration programming construct?
- Do a set of staments again
- For a fixed amount of times
- Or until a condition is met
What are the rules for pseudo-code?
- Descirbe each step breifly
- Upper case = Close to programming langauge
- Lower case = Closer to english
- Keywords to show beggining and ending of the block of code
What does hand tracing algorithms do?
- Looking at a printed extract of the program code and running through it like th computer
- Helps with understanding and finding any logical errors
What are the steps in hand tracing the algorithms?
- Take each line one at a time
- Write out current state of each variable in a trace table
- Note down any output that program would produce
- To help understand and spot any logical errors in the program
Trace this program?
Trace this program?
Trace this program
What is the process of abstraction?
Seperating ideas form reality
By hiding irrelevant details and only showing relevent data
What is representational abstraction?
- Arriving at a representation by removing unnecessary detail
- Like underground tube map only shows stations and intersections
What is abstraction by generalisation?
- Grouping by common characteristics to arrive at a hierarchical relationship of the is a kind of type.
- Going up is generalising
- Going down is specilising
What is the need for abstraction?
- Needed to accuratly display and model certain situation
- Depending on the level of detail needed
- Like a tube map vs tourist map of london
What are the different types of abstraction you need to know?
- Prodecural
- Functional
- Data
- Problem
What is prodecural abstraction?
- Abstracting away actual values
- Used in particular computation
- Which is a computational pattern
What is functional abstraction?
- Another layer of abstraction ontop of procedural
- Disregards the particular computation method
What is data abstraction ?
- Methodology that enables us to isolatehow a compound data object is used
- From the details of how it is constructed
Like how the operations in a stack hides how the data is represented in arrays and variables using subroutines to carry out that operation
What is problem abstraction / reduction?
- Removes details from a problem
- Until you can represent it that is posssible to solve
- As the problem has been reduced to one that already has been solved
*You can then unfold this graph and then find the shortest point (dijkstras algorithm) *
What is decomposition?
Taking big problems and breaking it down into smaller problems
What is step-wise refinement / top down modular design
- Top level is name of the problem
- Breaking down into more levels
- Which continues until the lowest level has only one task
What is composition?
- Botton up development
- Solutions developed by putting pre-exsisting components together
- Provent to work together
Lego - Predefined props hieght and width proven to interlock with each other
How is composition shown in programming langagues?
- Dev implements pre-written procedures
- Which are pre-tested, compiled and working
- Which are packaged into libaries which allow other developers to use
What are the steps in constructing computer science solutions from real world problems?
- Physiocal world scenrio
- Abstracted model to filter out uneccesary variables / side problems
- Construct algorithms based on abstracted model
- Implement algorithms using code and data structures
- Run code
How does automation apply to the real world?
- Once abstracted models are turned into mathmatical models
- We can use automation in the implementation of those models to process data much faster
- Allowing breakthroughs in science like medicine and great discoveries
What is a finite state machine?
- Abstract model of computation (how machine reacts to external events)
- Used to design computer programs and sequential logic circuits
- Can be one of a finite number of states at any one time
- Changes state based on a trigger condition or some input
- Visuallised through state transition diagrams
What is the structure of the FSM?
- Start state - where FSM begins
- Transition States - Allow us to move from one state to another
- Transition condition - Condition / input required to change state
What is the state transition table for this FSM?
What is a meanly machine?
- FSM with an output
- Output determined by both current state adn current input
- Input for each condition / Output for using transition arrow
What are sets in maths?
- An Unordered collection of values or symbols in which each value or symbol occurs at most once
What does a finite set mean?
A set whose elements can be counted off by natural numbers up to a particular number
What does cardinality mean in sets?
The numbe of elements in a set
What is an infinite set?
- A set which has no end value
- Represented by (“…”) at end of set
What is a countable set?
- Can be finite set or a countably infinite set
- A set which can be counted off against a subset of natural numbers
- Where every element of a set is associated with a unque natural number
What are the different expression symbols you need to know?
How do you understand expressions?
- Write out expression in plain english
- Using expression symbol meaning
What is the cartesian product?
- The product of two sets
- Which is the set of all ordered pars (a,b)
- Where a is a memeber of set A
- And b is a member of set B
(All Combinations of the two sets elements)
What is subsets and proper subsets in maths?
What is the union in maths?
What is intersection in maths?
What is difference in maths?
What is a regular expression?
- Tool which allows computers to work with text patterns
- Used for validation, pattern recognition in text files, syntax checking
- Allows for a spcific set of conditions that stings have to meet to be valid
What does the * metacharacter do?
What does the + metacharacter do?
What does the ? metacharacter do?
What does the | metacharacter do?
What are regular expressions and finite state machines?
- Equivalent wats of defining a regular langague
- Regular langague = abilitytorepresent it by a regular expression
- Any regular langauge should be defined as a finite state machine langague input
What is the finite state machine for this regular expression?
What is the regular expression for this finite state machine
What is Backus Naurus Form (BNF)?
- Formal mathematical way of defining syntax unambiguously
- Meta langague
Made up of sets of
- Terminal symbols
- Non-terminal symbosls
- Production rules
Why do we use meta langagues?
- Defining aspects of langagues is time consuming and lengthy in regular expressions
- Some aspects have nested brackets so regular expressions cannot be used
- BNF is a meta langague
What is the structure of BNF?
What does this BNF statment mean?
What does this BNF stament mean?
- A word is defined by 2 letters
- A letter is defined as any letter from A to Z
What is the BNF statment for defining words as characters?
What is parsing?
- Process of working out if a given statment is valid -
- Accordin to the given BNF production rules
What are sntax diagrams?
- Graphical representation of BNF
- Where the two methods of representing syntaz map directly onto one another
What are the symbols for a terminal element?
- Termnial element cant be broken down any further
What is the symbol for a non-terminal element?
- Defined in another syntax diagram
What is the terminal element symbol ?
- Element that may be used more than once
What does this diagram mean?
- A digit is any number from 0 to 9
- Any number is a digit from 0 to 9 and can have as many digits as you want
What is the end goal of alogrithm efficientcy?
Algorithms should
- Run as quickly as possible
- Take up the least amount of memory possible
How do you compare algorithms relative to the size of the problem?
- Considers thier complexity as a fucntion relative to the size of the operation
- Look at number of operations
- If the number of operations is the same as the input in a for loop then th algorithm is linear
- If nunmber of operations stay the same regardless of input then the algorithms constant
How do you measure the efficiency of an algorithm?
- Time complexity - How much time they need to solve a given problem
- Space complexity - The amount opf resouerces they require
What are time wise efficient algorithms?
Algorithms that are more effiecient time wise
What are space wise efficient algorithms?
Algorithms that are more effiecient space-wise
What is the permutation of a set of objects or values?
- Number of ways you can arrange those objets
- Factorial - Four factorial = 4x3x2x1
- Can be large when scaling up
What does is mean where a function maps one set of values onto another?
- Mapping one set of inputs onto a set of outpus
- One elemtn on the input set relates to exactly one element of the output set
What are the diffferent parts during function mapping?
Domain - All possible inputs of a function
Range - Set of all outpiuuts from a function
CoDoamin - All the possible values that may be output from a function
What is the complexity of this psudocode?
7 due to having 7 lines
Why is the complexity of this code 4 + 3n + 1
- 5 lines of code which doesnt change when increasing or decreasing input
- 3n is where depending on the output (n) there can be 3 lines for each value n is
What are the steps in taking complexity and converting it to Big(O) notation?
- Remove all terms except for the one with the larget facotr or exponent
- Remove any constants and put into big O form
What are the different Big O notations complexities you have to know?
- Constant complexity
- Logarithmic complexty
- Linear complexity
- Polynomial complexity
- Expoential complexity
What is constant complexity?
- O(1) - 1 can be any number
- An algorithm that always exectures in the same time
- Regardless of the size of the data set
- Best algorithms
What is Logarithmic complexity?
- O(Log n)
- An algorithm that havles the set in each pass
- Efficientw with large data sets
- Good algorithms
What is linear complexity?
- O(n)
- An alogrithm whose performance is proprotional to the size of the data setr
- Declines as the set grows
- Fair algorithms
What is polynomaial complexity?
- O(n^2)
- An algorithm whos performance is proportional to the square of the size of the data set
- Significantly reduces efficientcy with increasinly large data sets
- Poor algorithms
What is exponential complexity?
- O(2^n)
- An algorithm that doubles in size with each addition to the data set in each pass
- Inefficient
- Extremely poor algorithms that should be avoided
What is the time complexity for adding items to a serial array?
- Contant complexity O(1)
- Doesnt matter how big the array is
What is the time complexity fo looking for a valuse in an undordered list
What is the time complexity for adding items to a sequanetial array?
- O(n)
- Linear
- Due to using a while or for loop to move the items ahead of the new item
- As the array grows so does the amount of shuffling required
What is the time complexity for binary search?
- Logarithmic O(Log n)
- Due to the number of results to seach halves each time
What is the time complexity for pushing and popping items form stacks and queues?
- Constant O(1)
- Due to size not having an effect on adding or removing items
What is the time complexity for searching through stacks or queues?
- Linear O(n)
- Search one by one due to unsequeneced data so linear search is required
What is the time complexity for hashing?
- Constant O(1)
- The hashing algorithm will always produce a hash in the same amount of time
UNLESS - Hash created is a synonym and searching for the next avaliable space (overflow) is required
- Which is O(n)
So hashing algorithms that produce minimum synonyms is vital
What is the tiem complexity for seaching, inserting and deleting items from a liniked list?
What is the time complexity for searching binary trees?
- Logarithmic
- Due to either choosing left or right when trying to find a value
- So half the dataset is cast as irrrelevent each time
What are the time complexity for bubble sort and insertion sort?
- Polynomial
- O(n^2)
- Both use a nested loop
What are the general rules for deducing time complexity?
How does hardware impose limits on algorithms?
- Algorithms could require more memory then feasible meaning its unsolvable
- Exponential work may be required for a problem to be done where adding more computing power wont make a significant difference
What are tractable problems?
- Any porblem solvable in a polynomaial time or better
- Where It will run fast enough for it to be practical and useful
What are intractable problems and the issues that come with them?
- Any problem which cannot be solved in a polynomial time or better
- Solvable but impractical as they take to long
- You can use heuristic methosdinstead to give a good enough answer rather than the most optimal
What are some problems that are difficult to solve for computers?
- Broad or poorly defined probkems
- Problems thatcallforsubjective evaluations
- The Halting Problem
What question does the halting problem ask?
- Is it possible to write a program that takes in a algorithm and the inputs for that algorithm
- And tell you if the program will halt when running
- Without executing the program first
What is the answer to the question that the halting problem presented?
- Alan turing - No
- Since the prooblem is unsolvable there exsists some problems that simply cannot be solved by computers
What is the turing machine?
- Aim to find out if every mathmatical task is computable
- Consists of an infinite tape that contains 0,1and blanks
- A read/write head where the pointer can read the data present or write new data over the current value
As well as a FSM which details
- Amount of possible states
- Inital start state
- Halt states
- Transition rules - what to do when certain machine is in certain sates
How would a turing machine find the first 1 one the tape right of the current readwrite position?
What are transition functions?
- A way of representing turing machines and state transition diagrams and the accociated transition rules
What is the transition state functions for this turing machine diagram?
Wha is the universal turing machine?
- Acts as interpreter where it takes in a standard description of an algorithm
- Writes it back to the start of the tape
- To then be executed which follows the instructions of the algorithm inputted
What is the importance of the universal turing machine?
- Anything a turing machine can computer a real world computer couuld also computer
- Provides us adefiniton of what is omputable
- General purpose machine - foreunner of modern computers
- Same approach that programs and data take today
