Computer Science Paper 2

What is Dijkstra's algorithm used for?

Dijkstra's algorithm finds the shortest path between two nodes in a weighted graph.

How does Dijkstra's algorithm prioritize routes?

It uses a priority queue, storing the smallest distances at the front of the list.

What do nodes and edges represent in graphs used in Dijkstra's algorithm?

Nodes can represent devices, and edges represent network traffic.

How are distances represented initially in Dijkstra's algorithm?

Unreachable nodes are denoted by \infty.

What happens in step 2 of Dijkstra's algorithm?

The first node is removed from the queue, and distances to its neighbours are updated.

How does A* algorithm differ from Dijkstra's algorithm?

A* uses two cost functions: actual cost and heuristic cost.

What is a heuristic in the context of the A* algorithm?

A heuristic is an approximate cost to reach the final node from a given node.

In the A* algorithm, how is total cost calculated?

Total cost is calculated by adding the actual cost and the heuristic cost.

What is a key advantage of using the A* algorithm?

It can reduce the total time taken to find the shortest path by prioritizing nodes with lower total costs.

What requirement must edge weights meet for Dijkstra's algorithm to work optimally?

All edge weights must be non-negative (w \geq 0).

What is the initial distance value assigned to the starting node in Dijkstra's algorithm?

The starting node is assigned a distance of 0.

If the heuristic function in the A* algorithm is always 0, which algorithm does it become equivalent to?

It becomes equivalent to Dijkstra's algorithm.

In the A* cost formula f(n) = g(n) + h(n), what does g(n) represent?

g(n) represents the actual cost of the path from the starting node to node n.

What does it mean for a heuristic in A* to be 'admissible'?

An admissible heuristic never overestimates the actual cost to reach the goal, ensuring an optimal solution is found.

What is the purpose of searching algorithms?

Searching algorithms are used to find a specified element within a data structure.

What conditions must be met for the binary search algorithm to be applied?

The binary search algorithm can only be applied on sorted data.

What is the time complexity of the binary search algorithm?

The time complexity of binary search is O(\log n).

Describe the process of the binary search algorithm?

The binary search algorithm finds the middle element, discards one half of the data based on comparisons, and repeats this until the element is found or confirmed not to exist.

Give an example of finding an element using binary search. What happens if the element is not found?

In the example of finding 'Dylan', the algorithm iteratively narrows down the search; if 'Hattie' is not found, it returns 'Not found in data'.

How does linear search operate?

Linear search checks each element one by one until it finds the desired element or reaches the end of the list.

What is the time complexity of linear search?

The time complexity of linear search is O(n).

What advantage does linear search have compared to binary search?

Linear search can be applied to unsorted data unlike binary search.

What was the key observation made when comparing linear search and binary search using the first 20 letters of the alphabet?

Linear search is less efficient than binary search, particularly when the search value is towards the end of the data.

What is the best-case time complexity for both linear and binary search?

The best-case time complexity is O(1), which occurs when the target element is the first one inspected (the first element in linear search or the middle element in the first step of binary search).

What is the worst-case scenario for a linear search?

The worst-case occurs when the target element is the last item in the list or is not present at all, resulting in O(n) comparisons.

What is the space complexity of an iterative searching algorithm?

The space complexity is O(1) because the algorithm only requires a constant amount of extra space regardless of the size of the dataset n.

How is the middle index calculated in binary search to avoid potential integer overflow?

It is typically calculated as mid = low + (high - low) / 2 instead of (low + high) / 2.

In what scenario is linear search preferred over binary search?

Linear search is preferred when the dataset is small, unsorted, or when the data structure does not support random access (such as a standard linked list).

What are sorting algorithms designed to do?

They are designed to take a number of elements in any order and output them in a logical order, usually numerical or lexicographic.

Which sorting algorithms are mentioned in the lecture?

Bubble sort, Insertion sort, Merge sort, Quick sort.

What is bubble sort?

A sorting algorithm that compares and swaps adjacent pairs of elements until the largest element bubbles to the top of the array.

How does bubble sort determine when to terminate?

It can terminate early if a full pass is made without any swaps, indicating the array is sorted.

What is the time complexity of bubble sort?

O(n^2).

What does insertion sort do?

It places elements into a sorted sequence, building the sorted array one element at a time.

What is the time complexity of insertion sort?

O(n^2).

What is merge sort?

A 'divide and conquer' algorithm that recursively divides an input until it is reduced to single elements, and then merges them back in sorted order.

What is the time complexity of merge sort?

O(n \log n).

How does quick sort function?

It selects a pivot element and partitions the other elements into two lists, according to whether they are less than or greater than the pivot.

What is the time complexity of quick sort in the worst case?

O(n^2).

What is the average time complexity of quick sort?

The average time complexity is O(n \log n), which occurs when the pivot splits the array into relatively equal halves.

What is the space complexity of merge sort?

Merge sort has a space complexity of O(n) because it requires additional memory to store the temporary subarrays during the merge process.

What does it mean for a sorting algorithm to be 'in-place'?

An algorithm is 'in-place' if it requires a constant amount of extra space, or O(1) space, to sort the data (e.g., Bubble sort and Insertion sort).

What is a 'stable' sorting algorithm?

A sorting algorithm is stable if it preserves the relative order of records with equal keys.

What is the best-case time complexity for insertion sort?

The best-case time complexity is O(n), which happens when the array is already sorted.

How does the partitioning step work in quick sort?

Partitioning involves picking a pivot and moving all elements smaller than the pivot to its left and all elements larger to its right.

What type of data structure is a stack?

A stack is a first in, last out (FILO) data structure.

What does the top pointer in a stack indicate?

The top pointer indicates the position of the current top element of the stack.

How is the isEmpty function for stacks implemented?

It checks if the top pointer is less than 0.

What does the push operation do in a stack?

The push operation adds an element to the stack.

What operation removes the element from the top of the stack?

The pop operation removes the top element from the stack.

What type of data structure is a queue?

A queue is a first in, first out (FIFO) data structure.

How do you check if a queue is empty?

You check if the front pointer is equal to the back pointer.

What is the purpose of the enqueue operation?

The enqueue operation adds an element to the back of the queue.

What does the dequeue operation do?

The dequeue operation removes the front element from the queue.

What is the first element in a linked list referred to as?

The first element is referred to as the head.

What type of search is performed on a linked list?

A linear search is performed using sequential next operations.

What is the depth-first traversal approach?

Depth first goes as far down the tree as possible before backtracking.

What type of data structure is used in breadth-first traversal?

Breadth-first traversal uses a queue to track nodes at the current level.

What is the result of a depth-first traversal starting from the node labelled 5?

The order of output will be 2, 4, 3, 8, 5.

What algorithm is used for traversing trees in depth first (post-order)?

Depth-first search goes left until no more child nodes are available.

What is depth-first traversal's output method?

Output nodes as they are passed on the right.

What defines the tail of a linked list?

The tail refers to the last item in the linked list.

What is the peek operation in a stack?

The peek operation returns the value of the top element without removing it from the stack.

What is stack overflow?

Stack overflow occurs when an attempt is made to push an element onto a stack that has reached its maximum memory capacity.

What characterizes a doubly linked list?

A doubly linked list contains nodes that have a reference to both the next node and the previous node.

Why is a circular queue used?

It is used to reuse empty spaces at the front of the queue that occur after dequeue operations, maximizing memory efficiency.

How does pre-order tree traversal function?

It visits the root node first, then the left subtree, and finally the right subtree.

What is the time complexity of pushing an item onto a stack?

The time complexity is O(1), as it is a constant time operation.

What is a priority queue?

A specialized queue where each element has a priority, and elements with higher priorities are dequeued before those with lower priorities.

How does in-order traversal work in a Binary Search Tree (BST)?

It visits the nodes in ascending order by traversing the left subtree, the root, and then the right subtree.

What two pieces of information allow you to analyse an algorithm?

● Time Complexity.

● Space Complexity.

What is meant by the time complexity of an algorithm?

The amount of time required to solve a particular problem.

How do you measure of the time complexity?

Big-O Notation

What does the big-O notation show?

The effectiveness of an algorithm.

What is the Big-O notation good for?

It allows you to predict the amount of time taken to solve an algorithm given the number of items stored.

What does a linear time complexity mean?

The amount of time taken to complete an algorithm is independent from the number of elements inputted.

What does a constant time complexity mean?

The amount of time taken to complete an algorithm is independent to the number of inputted elements.

What does a polynomial time complexity mean?

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n.

What does an exponential time complexity mean?

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

What does a logarithmic time complexity mean?

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

What is a logarithm?

How many times a certain number (base) is multiplied together to reach another number.

What is space complexity?

The space complexity is the amount of storage space an algorithm takes up.

What is an algorithm?

An algorithm is a series of steps that complete a task.

How do you reduce the space complexity?

Try to complete all of the operations on the same data set.

How do you reduce the time complexity of an algorithm?

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer.

What is the Big-O notation of a linear

search algorithm?

O(n)

What is the Big-O notation of a binary search algorithm?

O(log(n))

What is the Big-O notation of a bubble sort algorithm?

O(n^2 )

What is meant by a computable problem?

A problem that can be solved using an algorithm.

Give three limiting factors to computable problems

Three from:

● Processing power

● Processor speed

● Computer memory

● Time

State two factors which may be considered during the Problem Definition phase

- Strengths and weaknesses of current solution.

- Volume/type/frequency/nature of.

- Inputs

- Outputs

- Stored data

What is the name given to the process in which problems are continually broken down until each subproblem can be represented as a subroutine?

Problem Decomposition

State two purposes of problem decomposition

Two from:

- Identify sections which can make use of pre-coded modules or libraries.

- Save timecoding.

- Simplify project management.

- Simplify testing and maintenance.

- Faster project delivery.

- Develop sections in parallel.

Describe how the Divide and Conquer technique works

The problem size is halved with every iteration. Each individual subproblem is then solved recursively. The solutions to the subproblems are then recombined to form the final solution to the problem.

Give two applications of divide and conquer

Two from:

- Merge sort

- Binary search

- Quick sort

Which programming construct do many problems solved using Divide and Conquer use?

Recursion

What is representational abstraction?

A computational technique in which excessive details are removed to simplify a problem.

What type of abstraction is used to group together sections of the problem based on their functionality?

Abstraction by generalisation.

State two problem solving techniques

Two from:

- Backtracking

- Data mining

- Abstraction

- Divide and conquer

- Visualisation

- Performance modelling

- Pipelining

- Visualisation

Describe how backtracking works.

The backtracking algorithm works by methodically visiting each path and building a solution based on the paths found to be correct. If a path is found to be invalid at any point, it backtracks to the previous stage and visits an alternate path.