Half Term 2 Flashcards
Bubble Sort
How does a bubble sort work?
- Compare first set of numbers
- If second number is less than first, swap them
- Compare next set of numbers
- Repeat to end of list
- Start again from the first pair in the list
- Repeat until no pairs need to be swapped
Bubble Sort
How many times does a list have to be scanned?
The maximum number of times a list has to be scanned through the length of the list -1
Bubble Sort
What is the basic bubble sort algorithm?
repeat [number of items - ] times
for each adjacent pair of items in the list
if first of pair is greater than second of pair
swap
Bubble Sort
When should a bubble sort be used?
A bubble sort is good for sorting small lists of data
Object Oriented Programming
What is Object Oriented Programming?
A programming paradigm based on the concept of ‘objects’ which contain attributes and methods
Object Oriented Programming
What is a class?
A class is like a template to ensure that all objects of a certain category have the same kinds of attributes and methods
Object Oriented Programming
What are the components of a class?
Classes are made up of the class name, its attributes and its methods
Object Oriented Programming
What are the benefits of OOP?
Once a class is defined, it is very easy to create hundreds of objects using it
Object Oriented Programming
What is instantiation?
Instantiation is the process of creating an object from a class template
Object Oriented Programming
What is a constructor?
A constructor is a special method which runs when an object is created from the class. It contains “new”. Objects are instantiated by calling the class’ constructor
Object Oriented Programming
What is the syntax for instantiation?
objectName = new ClassName(“attribute1”, “attribute2”)
Object Oriented Programming
What is encapsulation?
All of the object’s attributes are contained and hidden in the object by giving them the private access modifier. They are accessed through public getter and setter methods
Object Oriented Programming
What is the benefit of encapsulation?
Data cannot be changed accidently so reducing the chance of errors, ensures changes to attributes are only made in the way that is intended
Object Oriented Programming
What is an object/instance?
Objects or instances are the things created using a class’ template
Object Oriented Programming
How do you define class functions/methods?
When defining class functions, the keyword “this” must be used to declare class variables (not “let” or “var”) e.g.
constructor() {
this.x = 200;
this.y = 150;
Object Oriented Programming
What is the pseudocode for passing arguments into class constructors
constructor (x,y) {
this.x = x;
this.y = y;
}
object = new class(100,200)
Object Oriented Programming
What is inheritance?
A mechanism that allows an instance of a class to inherit attributes and methods from another class (the superclass/parent class). It can also have methods/attributes of its own
Object Oriented Programming
What is polymorphism?
The ability of an entity such as a variable, operator, method or object to have more than one form
Object Oriented Programming
What is overriding?
When an inherited method is superseded by a method defined in the subclass (an example of polymorphism)
Object Oriented Programming
What is overloading?
When methods have the same name but different signatures. The signature can differ by the number of parameters or type of parameters or both (an example of polymorphism)
Object Oriented Programming
What is an access modifier?
For example public and private which can be applied to attributes and methods in the class. Private means the attribute or method can not be accessed by code in another class while public means it can
Object Oriented Programming
What is an attribute?
A specific piece of data representing a particular characteristic of an object
Object Oriented Programming
What is a method?
For example getters and setters and other subroutines that define the behaviour of the object
Logic Gates & Truth Tables
NOT gate symbols and truth table
¬ ~ ! -
0 → 1
1 → 0
Logic Gates & Truth Tables
AND gate symbols and truth table
^ * &
0 0 → 0
0 1 → 0
1 0 → 0
1 1 → 1
Logic Gates & Truth Tables
OR gate symbols and truth table
v + ||
0 0 → 0
1 0 → 1
0 1 → 1
1 1 → 1
Logic Gates & Truth Tables
XOR gate symbols and truth table
⊻ ⊕
0 0 → 0
1 0 → 1
0 1 → 1
1 1 → 0
Logic Gates & Truth Tables
How do you create a truth table from a logic diagram?
- Create a column for each input
- List combinations
- Create columns for interim outputs
- Find outputs
Stacks & Queues
What is a stack?
A stack is an essential data structure. Items are pushed to the top of the stack when added and popped off the top when deleted. It’s possible to peek at the top item without deleting. It’s a LIFO structure
Stacks & Queues
What is a LIFO structure?
Last In First Out - The last item to be pushed onto the stack must also be the first to be popped off
Stacks & Queues
What is a stack pointer?
A stack pointer points to the node at the top
Stacks & Queues
What are stack underflow/overflows?
Stack overflow is an attempt to push an item onto a full stack. Underflow is an attempt to pop an item off of an empty stack
Stacks & Queues
How are the stacks implemented?
Stacks are often implemented with an array but could use object-oriented techniques instead
Stacks & Queues
How are stacks used?
- Stacks are used by processor to track the flow of programs. When a subroutine is called, it changes the value of the program counterto the first instruction of the subroutine. When the subroutine ends, the PC must return to its previous value. Stacks allow subroutine calls to be nested
- Local variables are held on stacks - their values are lost when a subroutine ends because they are popped off the stack. Interrupts can also be handled with a stack
- Performing depth-first searches on graph structures
- Keeping track of user inputs
- Undo operations
- Backtracking algorithms
- Evaluating mathematical expressions without brackets
Stacks & Queues
What is a queue?
A queue is a linear data structure. Items are enqueued at the back of the queue and dequeued from the front of the queue. You can peek at the front item. In special situations, new items can join at the front. It’s a FIFO structure
Stacks & Queues
What is a FIFO structure?
First In First Out - back/tail pointer points to last item, front/head pointer points at first item
Stacks & Queues
What is the problem with creating a queue with an array?
In an array, since the back and front
