Studied by 2 people

0.0(0)

Get a hint

Hint

1

Abstraction

Separating ideas from reality…

by removing irrelevant details…

to create a focused representation of reality.

New cards

2

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.

New cards

3

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.

New cards

4

Thinking Ahead + why do it?

Identifying the…

Preconditions

Inputs

Outputs

Reusable components

…of a system.

We do this to maximise efficiency and minimise errors.

New cards

5

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.

New cards

6

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.

New cards

7

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)

New cards

8

What is Thinking Procedurally?

Decomposing a problem to identify it’s components.

New cards

9

What is Thinking Concurrently?

Identifying parts of the problem that can be tackled at the same time.

New cards

10

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”

New cards

11

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]

New cards

12

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)

New cards

13

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.

New cards

14

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

New cards

15

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

New cards

16

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

New cards

17

Function vs Procedure

A block of code with a unique name to call it to complete a task. Takes parameters.

**Fun**ction is**Fun**so returns a value.Procedure does not return a value.

New cards

18

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

New cards

19

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

New cards

20

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

New cards

21

Benefits of OOP

Modular

pluggable

protected

reusable

faster development

New cards

22

Encapsulation

Bundling attributes and methods together within a class.

Ensures data remains secure and is not unintentionally modified (by making attributes private)

Hides complexities

New cards

23

Polymorephism

New cards

24

Backtracking

When an algorithm finds a solution by trying different sequences and abandoning a path that leads to an invalid solution.

trial and error

New cards

25

Data Mining

Identifies patterns and trends in large data sets.

New cards

26

Pipelining

is when an output of and other process is used in another

New cards

27

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.

New cards

28

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

New cards

29

Performance Modelling

Testing a system before it is used by users.

cost effective

simulating/modeling the performance/behaviour of the system before is sent.

New cards

30

problem de position

taking a large complex problem and breaking it into smaller more manageable subproblems.

the types:

top down

divide and conquer

New cards

31

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.

New cards

32

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.

New cards

33

time complexity

time taken by the algorithm in relation to the data size

New cards

34

space complexity

refers to the amount of memory required by an algorithm to solve a problem, depending on the size of the data.

New cards

35

O (1)

the algorithm takes the same amount of time no matter the data size

New cards

36

O (n)

linear time - the time taken is linear to the data size

New cards

37

O (n²)

polynomial time - algorithm performance is squared the data size

eg - bubble sort and insertion

New cards

38

O Log(n)

the time taken by the algorithm increases slowly as the data size increase

New cards

39

O (2^n)

Exponential time - time taken to execute will double with every additional item added.

eg - fibanacci sequence

brute force search

New cards

40

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

New cards

41

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

New cards

42

Merge sort

divide and conquer

splits list into individual lists and merges them together in order

time complexity - O n(Log(n))

New cards

43

Quick sort

divide and conquer

uses a pivot point

New cards

44

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

New cards

45

Stacks

FILO - first in last out

added from the top and removed from the top

maintain pointer to the top of the stack

New cards

46

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]

New cards

47

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.

New cards

48

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]

New cards

49

state the binary tree traversals

pre order

post order

in order

New cards

50

pre order

visit root node

traverse left subtree

traverse right subtree

visited sequence = 1,2,5,6,3

New cards

51

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

New cards

52

post order

traverse left subtree

traverse right subtree

visit node

visit sequence - 5,6,2,3,1

New cards

53

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.

New cards

54

types of linked list

Types: Single-linked, doubly-linked, and circular linked lists.

New cards

55

ad of linked list

Advantages: Dynamic memory allocation, efficient insertion/deletion, and serves as a foundation for other data structures.

New cards

56

Dijkstra's shortest path

New cards

57

A* algorithm

New cards