Computer Science paper 2

Abstraction

the process of removing unnecessary details of a problem to focus on the important features to implement in a solution

What is the difference between abstraction and reality?

Abstraction is a simplified version of reality

3 questions that need to be asked to be able to develop an abstract model?

What is the specific problem to be solved?
Can the problem be broken down into milestones?
What elements will impact the solution for each milestone?

What are inputs in an algorithm?

Data required for the algorithm to run (e.g., parameters passed to a subroutine).

What are outputs in an algorithm?

Data returned by the algorithm (e.g., results, messages, or device outputs).

Why is it important to explicitly define inputs and outputs?

To avoid errors by specifying type, size, and format (e.g., search algorithm needs sorted array).

What are preconditions in an algorithm?

Conditions that must be true for the algorithm to succeed (e.g., non-empty list, sorted data).

Give an example of a precondition for binary search.

The input list must be sorted; otherwise, the algorithm fails.

How can preconditions be implemented?

Through documentation (user checks) or code validation (automatic checks).

What is caching?

Storing frequently accessed data for faster retrieval.

What are the benefits of caching?

Faster access, reduced processing load.

What are the drawbacks of caching?

Risk of stale data (outdated info) and memory overhead.

Why are reusable program components important?

They promote efficiency, modularity, and reduce redundant code.

How can a subroutine be made reusable?

By clearly defining inputs, outputs, and preconditions (e.g., library functions).

For LinearSearch, what are the inputs?

A list of integers (e.g., my_list = [i1, i2, ...]).

For LinearSearch, what are the ouputs?

The index of the found element (integer).

What is a variable?

A changable memory location that holds data

What is data mining?

When large quantities of data are turned into useful information so that patterns can be found 

Benefits of Data Mining

Data mining can be used to identify patterns and trends that may not be immediately obvious to humans. 

It can help organisations make better future predictions.

Organisations can ensure demand is met during busy
periods to stay ahead of local competition. 

Drawbacks of data mining?

It requires very powerful computers with a lot of processing power.

Inaccurate data can produce inaccurate results.

Although it may spot patterns and trends, it may not explain the reasons why these exist. 

What is heuristics?

Making use of experience to find a solution to a problem quickly

Benefits of Heuristics?

Heuristics can usually find a solution close to the best solution available.

Heuristics save time as you may not to investigate every single possibility to get a definite answer.

Heuristics is very practical and can be easily implemented.

Drawbacks of Heuristics?

It will not guarantee that you will find the ‘best’ solution as it aims to find a solution quickly that is ‘good enough

There needs to be careful consideration to be made between accuracy and time.

The heuristic values may be incorrect which can lead to inaccurate solutions being found. 

What is a global variable?

a variable declared at the outermost level of a program.

Benefits of Global Variables?

The global variable only needs to be declared once.

You don’t need to keep passing parameters between the different modules.

Drawbacks of Global Variables?

The global variables are always stored in memory while the program is running which can use up memory.

Makes the program difficult to maintain as it’s difficult to understand where variables are changed in the program.

Makes it difficult to test a single block of code as the programmer will need run the entire program to setup the global variables.

What is a local variable?

A variable declared within a specific scope, such as a function or a code block

Benefits of Local Variables?

Local variables encapsulate data within a particular function or block, providing data hiding and preventing unintended access from other parts of the program.

Local variables enable you to use the same variable name in different functions or blocks without causing conflicts, as each local variable is confined to its own scope.

Local variables have a limited lifetime, and their memory is automatically reclaimed when the code block ends, making them memory efficient.

Drawbacks of Local Variables?

Repeatedly creating and destroying local variables within a loop or recursive function can incur unnecessary memory overhead.

Excessive use of local variables within deeply nested blocks can lead to code clutter and reduce code readability.

What is Nesting?

Putting one block of code inside another block of code of the same type

Best Time complexity of Linear search

O(1)

Average Best Time complexity of Linear search

O(n)

Worst Time complexity of Linear search

O(n)

Best Time complexity of Binary Array search

O(1)

Worst Time complexity of Binary Array search

O(logn)

Average Time complexity of Binary Array search

O(logn)

Best Time complexity of Binary Tree search

O(1)

Average Time complexity of Binary Tree search

O(logn)

Worst Time complexity of Binary Tree search

O(n)

Best Time complexity of Hashing search

O(1)

Average Time complexity of Hashing search

O(1)

Worst Time complexity of Hashing search

O(n)

Best Time complexity of Bredth/Depth first search

O(1)

Average Time complexity of Bredth/Depth first search

O(V+E) verticies + edges

Worst Time complexity of Bredth/Depth first search

O(V²)

Best time complexity of a bubble sort

O(n)

Average time complexity of a bubble sort

O(n²)

Worst time complexity of a bubble sort

O(n²)

Best time complexity of a insertion sort

O(n)

Average time complexity of a insertion sort

O(n²)

Worst time complexity of a insertion sort

O(n²)

Best time complexity of a merge sort

O(nlogn)

Average time complexity of a merge sort

O(nlogn)

Worst time complexity of a merge sort

O(nlogn)

Best time complexity of a quick sort

O(nlogn)

Average time complexity of a quick sort

O(nlogn)

Worst time complexity of a quick sort

O(n²)

Space complexity of Bubble Sort

O(1)

Space complexity of Insertion Sort

O(1)

Space complexity of Merge Sort

O(n)

Space complexity of Quick Sort

O(log n)