Studied by 2 people
Abstraction
Separating ideas from reality…
by removing irrelevant details…
to create a focused representation of reality.
How to/why abstract?
Remove unnecessary elements…
to reduce unnecessary programming…
which would require extra computational resources…
and detracts from the main purpose of the program.
Realities relationship to Abstraction
Abstraction is a simplified version of reality in which…
real-world entities are represented as tables in databases and…
real-world values are stored as variables and constants.
Thinking Ahead + why do it?
Identifying the…
Preconditions
Inputs
Outputs
Reusable components
…of a system.
We do this to maximise efficiency and minimise errors.
Preconditions
Conditions that must be true for an algorithm to complete successfully without errors. For example:
A binary search algorithm must be supplied with an ordered list.
Reusable Program Components + Benefits/Drawbacks
Commonly used functions are packaged into libraries.
Reusable components like:
Classes
Subroutines (Functions or Procedures)
Abstract Data Structures (Queues & Stacks)
+ More reliable than new code as they’ve been tested.
+ Saves time, money, and resources.
+ Can be used in future projects.
- Components may need to be modified to be compatible with a project.
Caching + Benefits/Drawbacks
Storing instructions/data in cache memory after they’ve been used as they might be frequently used.
+ Faster than RAM or Secondary Storage so saves time
- Cached data may not reflect latest updates to that data. (E.G a webpage you frequent may be cached, but it may have been updated since you last visited)
What is Thinking Procedurally?
Decomposing a problem to identify it’s components.
What is Thinking Concurrently?
Identifying parts of the problem that can be tackled at the same time.
Concurrent Processing
When system appears to do multiple things simultaneously (on one core) but it kinda switches between them really quickly so they are done ‘at the same time’.
“One process does not have to finish before the other starts” - mark scheme
“Processes are happening at the same time / at overlapping times” + “Only 1 process can actually happen at a time on a single core processor, concurrent tries to simulate multiple processes”
Sequence, Selection, and Iteration (Branching)
One statement after another
Code is executed line by line, from top to bottom
Decision-making points (if else, switch case)
decision based on a condition
Loops (for, while, do until)
can be looped until a count is done or condition is met
count controlled [definite]
condition controlled [indefinite]
What is a Procedural Programming Language?
A high-level language that gives a series of instructions in a logical order. (what to do and how to do it)
What is a Parameter and how to pass to a subroutine?
Data structures that are passed into a subroutine when called.
By Value: A local copy of the data in the variable is used, and then discarded, so the original data is unaffected.
By Reference: Reference to the variable's memory location is passed to the function, which means the actual value is affected.
Variables + Scope
Identifier of a memory location used to store data.
The range that a variable is accessible for.
Local Scope:
Accessible in the subroutine that it was defined in.
Eraed when subroutine ends
+ Ensures subroutines are self-contained
Global Scope:
+ Accessible across the entire program.
+ Risk of being unintentionally edited.
- Requires more memory as not deleted until the program ends
What is an IDE? + Features?
Integrated development environment. A single program that is used to develop programs.
Syntax highlighting to identify mistakes quickly
Stepping to run one line at a time and check the result
Variable watch to check the value of variables during execution
Error messages to locate errors
Breakpoints to stop and test the program works up to certain points
Recursion + Essential features?
Routine calls itself…
and has a stopping condition…
which must occur after a finite number of calls.
- can cause stack overflow
- slower and uses additional system resources
Function vs Procedure
A block of code with a unique name to call it to complete a task. Takes parameters.
Function is Fun so returns a value.
Procedure does not return a value.
Recursion Vs Iteration
Recursion:
+ Fewer lines of code
+ Better for a problem can’t be solved with a fixed amount of memory.
More likely to cause a stack overflow
Iteration:
+ Easier to follow/understand
+ Faster
Benefits/Drawbacks of Concurrent Processing?
+ More tasks completed in a given time.
+ Less time wasted waiting for input/interaction, as other tasks can be completed during the waiting.
- May take longer when a lot of users/tasks are involved.
- Long to coordinate and switch between processes.
- Task may not be suited to be broken up and performed concurrently
Class, Object, Attributes in OOP
A Template of an object that defines the state (attributes) and behaviour (methods) of objects.
An instance of a class
Benefits of OOP
Modular
pluggable
protected
reusable
faster development
Encapsulation
Bundling attributes and methods together within a class.
Ensures data remains secure and is not unintentionally modified (by making attributes private)
Hides complexities
Polymorephism
Backtracking
When an algorithm finds a solution by trying different sequences and abandoning a path that leads to an invalid solution.
trial and error
Data Mining
Identifies patterns and trends in large data sets.
Pipelining
is when an output of and other process is used in another
Breadth First Traversal
From left to right, visit children of root/start node. Then visit children of each of those nodes, still left to right. Continuing until every node has been visited.
Depth-first (Post order)
Goes as far into the tree as possible. Goes to the left child node when possible, if not possible then goes to the right. When it get’s to the point of when a node has no children, it visits that node. Backtracks to the previous node, attempts to go right, if it can, then contin
Performance Modelling
Testing a system before it is used by users.
cost effective
simulating/modeling the performance/behaviour of the system before is sent.
problem de position
taking a large complex problem and breaking it into smaller more manageable subproblems.
the types:
top down
divide and conquer
top down design
take the main problem and break them to major task that need to be performed.
break further until u reach separate subtasks
continue until sufficiently simple to be written as a selfcontain module or subroutine.
divide and conquer
uses recursion, task is divided until an easy to solve subtask is reached
the subtasks are then combined to create the solution
common - searching, sorting and pathfinding.
time complexity
time taken by the algorithm in relation to the data size
space complexity
refers to the amount of memory required by an algorithm to solve a problem, depending on the size of the data.
O (1)
the algorithm takes the same amount of time no matter the data size
O (n)
linear time - the time taken is linear to the data size
O (n²)
polynomial time - algorithm performance is squared the data size
eg - bubble sort and insertion
O Log(n)
the time taken by the algorithm increases slowly as the data size increase
O (2^n)
Exponential time - time taken to execute will double with every additional item added.
eg - fibanacci sequence
brute force search
insertion sort:
splits list into 2 parts:
sorted
unsorted
the algorithm takes the unsorted and moves them into the sorted in the right order.
effective than bubble sort
steps of insertion sort
first value of the list is in the sorted sub list
move through the unsorted list and take the values one by one and add them to the sorted list, ensuring they are in the right order.
time - O(n) = best
O(n²) = Avg, worst
Merge sort
divide and conquer
splits list into individual lists and merges them together in order
time complexity - O n(Log(n))
Quick sort
divide and conquer
uses a pivot point
quick sort steps
selects pivot point
the values to the right of the pivot should be lower and the value to the left higher.
it checks the right most value and compares it with the left most value
the values are moved until condition is true
this creates 2 partitions
its repeated in smaller and smaller partitions
Stacks
FILO - first in last out
added from the top and removed from the top
maintain pointer to the top of the stack
stack operations
push()-adds data to the top of the stack
pop()- removes data form the top of the stack
IsEmpty()- checks if the stack is empty [returns Boolean value]
IsFull()- checks if the stack is full [returns Boolean value]
Queues
FIFO - first in first out
elements can only be added from the back and retrieved from the front
the sequence is determined by the order of they were inserted.
queue operations
enqueue()- add items to the end of the queue
dequeue()- remove the item from the front
isempty() - checks if the queue is empty [returns Boolean value]
isfull() - checks if the queue is full [returns Boolean value]
state the binary tree traversals
pre order
post order
in order
pre order
visit root node
traverse left subtree
traverse right subtree
visited sequence = 1,2,5,6,3
in order
traverse left
visit
traverse right
goes to the left most node and works back
then go back and check right
visit sequence - 5,2,6,1,3
post order
traverse left subtree
traverse right subtree
visit node
visit sequence - 5,6,2,3,1
linked list
Definition: A linked list is a linear data structure where elements are not stored contiguously in memory, but are linked using pointers. Each element, called a node, contains data and a reference (pointer) to the next node in the sequence.
Structure: Consists of nodes, each with data and a pointer to the next node.
types of linked list
Types: Single-linked, doubly-linked, and circular linked lists.
ad of linked list
Advantages: Dynamic memory allocation, efficient insertion/deletion, and serves as a foundation for other data structures.
Dijkstra's shortest path
A* algorithm
Note
Flashcard