Unit 4 Flashcards
Identify inputs and outputs required in a solution
Cycle: Input; Processing; Output; Feedback
Sequential
Following in logical orders/sequences
Preconditions
Constrains the state of a system before the next sector of code starts
Post conditions
Conditions after code has been executed
What to do if there’s an exception?
Inform developer; then crash
What to do if there’s an error?
Inform user; but keep running
Concurrent
When two or more processes are using the same resources at the same time
Describe how concurrent processing can be used to solve a problem
Increases: Computation speed; Complexity of programming language and hardware. Reduces: Complexity of array operations within loops; matrix multiplication/ sorting/ merging files. I(CS; CPL; H) R(CAOL; MM; S; MF)
How do you evaluate the decision to use concurrent processing in solving a problem?
Saved or wasted time? Saved or spent money? Physically possible? Consequence of not doing it?
Advantages of concurrency
Time Cost
Disadvantages of concurrency
May get in each others way Harder to supervise
Abstraction
Removing characteristics from something in order to reduce it to a set of essential characteristics. It’s a technique for managing complexity.
Why is abstraction required?
Reduces complexity; enables concentration on essential; ignores distracting details and essential to problem solving.
How to distinguish between real and abstract?
DETAILS
IB assumptions about collections are
Unordered lists Unknown length
Operations (5 PseudoCode operations)
.addItem() .resetNext() .hasNext() .getNext() .isEmpty()
.addItem()
Adds an item to the collection
.resetNext()
Starts at the beginning of the collection
.hasNext()
To see if it has another item
.getNext()
retrieves next data point from collection
.isEmpty()
Checks whether its empty
Most efficient search algorithm?
Binary; Olog(N) notation; only works on sorted lists
Sequential search
Slower; O(N) notation
Bubble sort
Quits early if no swaps occur; but LOTS of swaps happen. O(N^2)
When bubble sorting on a list
Compares and swaps every two numbers
Selection sort
No quit early; always N passes. O(N^2)
Flow chart shapes (bubble; parallelogram; rectangle and diamond)
Bubble: Terminator Parallelogram: Input/ Output Rectangle: Process Diamond: Decision
What effects run time?
Hardware Abstract data types Compiler Efficiency Programmers skills Complexity Size of input (H; ADT; CE; PS; C; IS)
Worse case scenario
Max run time Number of times the principal activity of the algorithm is performed
Best case scenario
Specific instances of input size N
Average case scenario
Most useful General case
Fundamental operations of a computer
Add; Compare; Retrieve; Store.
Complex operation example
Finding the biggest number in an array
Low level language
Closer to binary; Machine code or Assembly
High level language
Java; C++; HTML
Natural language
Varying vocab Ambiguous Grammar & Syntax inconsistent
Computer language
Fixed vocab Unambiguous meaning Grammar & Syntax consistent
Why grammar and syntax is important
Easy to learn and use Less compilation and logical errors
Need for High Level languages
Similar to human language Needs for computer systems have expanded Time constraints - too long to write machine code (HL; NCS; T)
Need for Low Level languages
Close to binary code that’s used to process instructions
Compiler
Translates from a high level language to a low level (in batches)
Interpreter
High level to intermediate; then executed by CPU
Why you need compliers and interpreters?
High level to low level langauge Translated into machine code for CPU to execute
Why do you need BOTH?
Interpreter is faster and warns about syntax errors; easier when debugging Compiler needed when there’s a need to produce executable version of program
Assembler
Assembly to machine code (mnemonics -> binary)
Variables
Storage locations; naming memory locations with a name and data type that can’t be changed.
Constant
Identifier with associated value that doesn’t change.
Operator
Set of characters that represents an action (CRA)
Object
Instance of a class
Advantages of modular design
Code reusability; Eases program organization and makes future maintenance easier (CR; EPO; ME)
Need for sub programmes
Breaks down tasks into more manageable sections Distributes development Code Reusability Program readability (BM; DD; CR; PR)
Bubble sort algorithm
int temp; loop i from 0 to array.length-1 loop j from 0 to array.length-1 if array[i] > array[i+1] then temp = array[i] array[i] = array[i+1] array[i+1] = temp end if end loop end loop
Selection sort algorithm
int temp; loop i from 0 to array.length-1 loop j from i+1 to array.length if array[i] > array[j] then temp = array[i] array[i] = array[j] array[j] = temp end if end loop end loop
Sequential search algorithm
loop for i from 0 to array.length if searchkey == array[i] then ouput searchkey; ‘has been found!’break; end loop
Finding the minimum and maximum in an array
int min = array[0] int max = array[0] loop i from 0 to array.length if min > array[i] then min = array[i] end if else if max < array[i] then max = array[i] end else if end loop output ‘min =’; min; ‘max =’; max
Binary Search Algorithm
input key low = 0 high = array.length-1 found = -1 loop i while found == -1 && low <= high mid = (low + high) div 2 if array[mid] == key then found = mid else if key < array[mid] then high = mid - 1 else low = mid + 1 end if end while if found >= 0 then output key; ‘ was found!’else output key; ‘ was not found!’end if
Hours given minutes
Div 60
Minutes remaining
Mod 60 (This was a past paper question!)
