Algorithmic Strategies: One Mark Questions, Book Back Answers and Notes

About Algorithmic Strategies

Medium ~90 min study

An algorithm is a finite set of steps that solves a problem, written without depending on any particular programming language. Because it is language-independent, you can check whether it is correct and how fast it will be before writing a single line of code. A program is that algorithm written in a specific language.

Two questions run through the whole chapter: how much time does the algorithm take, and how much memory does it need? The chapter gives you the tools to answer them (complexity, asymptotic notation) and then applies them to real searching and sorting methods, so you can see why binary search beats linear search on a sorted list, and why one method may use more memory to save time.

In the exam you are often asked to trace an algorithm on a small list: find the mid value at each step of a binary search, or show the list after each pass of bubble sort. Practise these by hand on a list of 8 to 10 numbers. Also learn what each asymptotic notation stands for and what memoization means.

What you'll learn

• List the characteristics of an algorithm and tell an algorithm from a program.
• Explain time complexity, space complexity and the space-time tradeoff.
• State what Big O, Big Omega and Big Theta describe.
• Trace linear search and binary search on a given list, showing the mid value at each step.
• Show the list after each pass of bubble sort, selection sort and insertion sort.
• Explain dynamic programming and memoization using the Fibonacci series.

Before you start

• Variables, data types and conditional statements.
• Loops and simple collections such as lists and arrays.

Algorithmic Strategies explained

Algorithmic Strategies: Key Ideas from Unit 4

Characteristics of an Algorithm

An algorithm is a finite set of instructions to carry out a particular task. The textbook lists its characteristics: input, output, finiteness (it must end after a finite number of steps), definiteness (each step is clear and unambiguous), effectiveness, correctness, simplicity, feasibility, portability and independence from any programming language or operating system.

Complexity and Analysis

An algorithm is judged by the time and space it uses. Time complexity is the number of steps taken to complete the task. Space complexity is the memory needed, made up of a fixed part (for the code, simple variables and constants) and a variable part (which depends on the input). Analysis is done in two ways. A priori estimates are a theoretical analysis that assumes factors like processor speed are constant. A posteriori testing is measurement: the algorithm is run and actual statistics such as running time and memory used are collected.

The space-time tradeoff is a way of solving a problem in less time by using more memory, or in very little memory by spending a long time.

Asymptotic Notations

These notations describe how running time grows as the input size grows. Big O describes the worst case, the upper bound. Big Omega (Ω) is the reverse of Big O and describes the lower bound, the best case. Big Theta (Θ) is used when the lower bound and upper bound are the same: an algorithm that is both O(n log n) and Ω(n log n) is Θ(n log n), so its running time always grows like n log n in both the best and worst cases.

Searching

Linear search (sequential search) checks each element one by one until the value is found or the list ends. The list does not need to be sorted, and the worst case is O(n). Binary search (half-interval search) works only on a sorted array. It finds the middle element using mid = low + (high - low) / 2. If the target is larger than the middle value, it sets low = mid + 1; if smaller, high = mid - 1. Each step halves the search space, so it takes O(log n) comparisons. Binary search follows the divide and conquer approach.

Sorting

Bubble sort compares each pair of adjacent elements and swaps them if they are in the wrong order, repeating passes until no swaps are needed. Selection sort finds the smallest element in the unsorted part and swaps it with the first element of that part. Insertion sort builds a sorted part one element at a time, taking the next element and inserting it into its correct position.

Dynamic Programming

Dynamic programming is used when a problem can be broken into smaller subproblems that overlap, so the same subproblem would otherwise be solved many times. The result of each subproblem is stored and reused. This storing is called memoization: the results of expensive function calls are saved and returned directly when the same inputs occur again. The Fibonacci series is the textbook example, since fib(5) needs fib(3) more than once.

Common mistakes to avoid

• Swapping the meanings of the notations. Big O is the upper bound (worst case); Big Omega is the lower bound (best case).
• Calling Big Theta the average case. Big Theta means the upper and lower bounds are the same, so the growth rate is fixed in both best and worst cases.
• Running binary search on an unsorted list. Binary search only works if the array is sorted first; otherwise use linear search.
• Updating low or high to mid instead of mid + 1 or mid - 1 while tracing binary search. The middle element has already been checked, so it must be excluded.

Test yourself on these with the practice test, then check the worked reasoning in the solved MCQs.

Frequently asked questions

What is the difference between an algorithm and a program?

An algorithm is a step-by-step method for solving a problem, written independently of any programming language. A program is that algorithm written in a particular language, following its syntax so a computer can run it.

Why is binary search faster than linear search?

Linear search may check every element, so for n elements it takes up to n comparisons, O(n). Binary search halves a sorted array at every step, so a list of 1000 elements needs only about 10 comparisons, O(log n). The catch is that the array must be sorted.

What does space-time tradeoff mean?

It means choosing between time and memory. You can make an algorithm run faster by storing extra data in memory, as memoization does, or you can use very little memory and accept a longer running time.

What do the asymptotic notations tell us?

They describe how an algorithm's running time grows with input size. Big O gives the upper bound (worst case), Big Omega gives the lower bound (best case), and Big Theta is used when both bounds are the same, such as an algorithm that is both O(n log n) and Ω(n log n).

What is memoization?

Memoization is an optimisation technique that stores the results of expensive function calls. When the function is called again with the same inputs, the stored result is returned instead of being calculated again. It is what makes dynamic programming efficient.

How is dynamic programming different from divide and conquer?

Both split a problem into smaller subproblems. In divide and conquer, such as binary search, the subproblems are independent. In dynamic programming the subproblems overlap, so their results are stored and reused instead of being solved again, as in the Fibonacci series.