The externals (quick reminder 2 * 3 credits each), are a DCAT (91909 project) and a 'proper' external exam (91908 Computer Science). My experience is that students can do this very successfully. The topic we are doing is Complexity and Tractability. The external that you do about your project is very straightforward - I will cover this in just one or two lessons before the DCAT.

DCAT - 91909 - week of 8 - 12 September 2025 External Exam 91908 Wednesday 12 November 2pm

The area we are looking at is a really interesting topic called complexity and tractability. I find it fascinating and I hope you do too.

Most of the work for this topic can be found in Chapter 11 of the CS field guide. https://www.csfieldguide.org.nz/en/chapters/complexity-and-tractability/ For this section read the following:

1. Read through and complete 11.1 of the CSFG - What's the big picture?
2. Read through and complete 11.2 of the CSFG - Algorithms, problems, and speed limits
3. Read through and complete 11.3 of the CSFG- Tractability
4. Read through and complete 11.4 of the CSFG - The Traveling Salesman Problem

For each of the chapters have a really good read and do any of the interactive activities. At the end of this you should have an idea why some problems can’t be solved precisely using an algorithm - ie we might have a good solution (determined using a heuristic algorithm) but we cannot be sure it is the correct solution (ie there might be a slightly better solution) - all because some problems scale very rapidly.

In computer science, complexity isn't just about how long a program takes to run—it's a measure of how its resource requirements, particularly time and space, grow as the size of the input increases. Think of it as a way to predict your algorithm's behavior. An algorithm might be fast for a small list of items, but will it completely grind to a halt when that list contains a million? This is where complexity analysis comes in. We use Big O notation to describe this scaling relationship, like O(n) or O(n²), which provides a standardized way to compare and evaluate the efficiency and scalability of different solutions to the same problem. Understanding complexity is fundamental because it's the difference between writing a program that works and writing one that performs well in the real world.

1. Read through the CSFG page on Complexity and complete any activities.

Jargon warning - this next part could be a little difficult and you may need to read it a few times

Know how many steps an algorithm takes to complete can give us an indication of how long it will take to complete. Even better than this, knowing if an algorithm is efficient with very large inputs helps us understand if an algorithm may be suitable for any particular use. Think about the Travelling Salesman Problem (TSP) - its OK to calculate with just 3 or 4 destinations, but once you get to 20, 5o or 100 destinations, knowing the correct answer is impossible because the number of combinations that need to be tested is impossible.

One way of comparing and describing how an alogorithm behaves as the number of inputs/sze of the problem increases is by using something called Big-O notation.

You will need to know and compare the Big-O notation for some common algorithms.

1. Watch this video on binary - understanding base number systems
2. Watch this video on logarithmic scales
3. Watch this video on Big-O notation in 6 minutes
4. Read through the CSFG page on Big-O notation

Common Big-O notations include (n is the size of the input):

1. O(1)
2. O(log n)
3. O(n log n)
4. O(n^2)
5. O(2^n)
6. O(n!)

The x-axis is the size of the input and the y-axis how long the algorithm takes to complete.

Big-O Notation	Example Algorithm	Notes
O(1)	Random access of an element in an array or list inserting at the beginning of a linked list	Constant time. When your calculation is not dependent on the input size, it is a constant time complexity (O(1)).
O(log n)	Binary search	Logarithmic time. When the input size is reduced by half, maybe when iterating, handling recursion, or whatsoever, it is a logarithmic time complexity (O(log n)). Binary search animation Another binary search animation Best case
O(n)	Looping through elements in a list	Linear time. When you have a single loop within your algorithm, it is linear time complexity (O(n)). Linear vs Binary Search
O(n log n)	Quicksort	Quasilinear time. When the growth rate doubles with each addition to the input, it is exponential time complexity (O2^n). Quicksort animation
O(n^2)	Bubblesort Selection sort	Quadratic time. When you have nested loops within your algorithm, meaning a loop in a loop, it is quadratic time complexity (O(n^2)). Bubble sort animation
O(2^n)	Recursive Fibonacci sequence	Exponential time. When the growth rate doubles with each addition to the input, it is exponential time complexity (O2^n). The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting with 0 and 1. The sequence begins as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The recursive Fibonacci sequence is generated by a function that calls itself to calculate the Fibonacci numbers. Each number in the sequence is the sum of the two preceding numbers, starting with 0 and 1, so the sequence begins as 0, 1, 1, 2, 3, 5, and so on.
O(n!)	Travelling salesman problem	Factorial time

Some common examples include:

Big O Notation	Common example
O(1)	determining if a number is odd or even
O(log n)	finding a word in the dictionary (using binary search)
O(n)	reading a book
O(n log n)	sorting a deck of playing cards (using merge sort)
O(n^2)	checking if you have everything on your shopping list in your trolley - one at a time)

The best case of an algorithm is the minimum number of steps required for completion.

The worst case is the maximum number of steps required for completion.

The average case is based on probability.

The worst case is often used to give an indication if the algorithm is suitable.

E.g. for O(n), best case is 1, worst case is n and average - if the elements are sorted would be n/2.

Computer scientists often draw a line between algorithms that require exponential time (that is, they are O(2n) or worse), and those that require polynomial time, which require times like O(n2), O(n3), O(n4) and so on including things like O(n) and O(logn). The latter ones are referred to as “polynomial time”, since the amount of time they take is proportional to a polynomial.

Those that are O(2n) or worse are sometimes loosely referred to as “non-polynomial”, although “exponential” or “superpolynomial” is probably a better descriptionBig O notations O(1), O(log n), O(n) , O(n^k), O(2^n), O(n!).

The word "exponential" is often used inaccurately in casual use, often to refer to something that grows quickly. But the real meaning of "exponential" is that it has n in the exponent, such as 2n, 3n, or even nn (which is similar to n!). This means that n2, or even n5 is not not exponential, since n is not in the exponent. They grow quite quickly as n increases, but they are nothing like as bad as 2n.

The video below gives an introduction to the P vs NP problem and why it is important. P vs. NP and the Computational Complexity Zoo Note that you only need to watch up to about 8:10. After then it gets really beyond NCEA Level 3!

Another video to help you understand P vs NP is this one Biggest Puzzle in Computer Science: P vs NP. Again the sections between 4:05 - 7:05 and after 15:33 are not that relevant - but if you have time do watch them.

Polynomial time algorithms are generally referred to as “tractable”, because chances are a powerful enough computer will be able to run them in a reasonable time, even if n is fairly big. Exponential (or non-polynomial) time algorithms are generally referred to as “intractable”, because even if the algorithm runs fast enough for a given value of n, it will probably be too slow if n increases by just a small amount. Of course, some polynomial time algorithms are also too slow to use, but it’s a simple distinction that usually provides a good warning if things are going to get out of hand.

1. Read through this detailed explainer of tractability

2. Read through this detailed explainer of how tractability relates to the travelling salesman problem

3. Read through this explainer of the bin packing problem and how it relates to tractability

NP-complete is a term for a huge set of problems that we just can’t seem to find tractable algorithms for, and yet if we find a solution for one of them, we know how to get a fast solution for all of them. Finding out if one of these solutions exists is considered one of the biggest questions in computer science, and there’s even a $1,000,000 prize for finding a solution (it’s one of the “Millenium Prize Problems”). Examples of these problems include TSP, bin-packing and the knapsack problem.

The “NP” in the name stands for “non-deterministic polynomial-time”, which means that it’s part of a class of problems that could be solved by a “non-deterministic” machine (these don’t exist in reality) in polynomial time (that is, a tractable amount of time). In reality, computer scientists have only found exponential time algorithms for them (which are loosely referred to as using non-polynomial time).

The “complete” in NP-complete mainly means that any algorithm for one NP-complete problem can be converted to another in polynomial time, so if a fast algorithm for one is discovered, then we have instantly found a polynomial time algorithm for all of them.

Heuristics and approximation algorithms

cause many of the NP-complete problems solve important real world problems (like reducing the amount of fuel used for deliveries, or loading aeroplanes optimally), we need to use heuristics or approximation algorithms that don’t necessarily find the best solution, but at least find a fairly good solution in a reasonable amount of time. For example, for the TSP, the “nearest neighbour” heuristic can work reasonably well - it just chooses the nearest unvisited location at each step. This typically gives a solution about 25% worse than the optimal one, but it runs in polynomial time. Another example is for bin-packing, where a heuristic “next-fit” algorithm just puts an item in the first bin that has space for it. It can run in O(n) time, but it might use up to about twice as many bins as an optimal algorithm.

While it seems unlikely, it is possible that someone will find a polynomial time algorithm for an NP-complete problem, in which case we’ll have one for all NP-complete problems! This might seem positive, since we can then optimal decisions about things like transport and timetabling, but one interesting social consequence of this is that it also means that cryptographic methods relying on the algorithms to take exponential time may now be useless. In fact, a solution to any NP-complete problem would be like the discovery of nuclear fission - it is both an incredible benefit, and a huge threat! There’s a thriller movie that imagines a group solving the TSP problem, and the consequences.

Have a look at these questions and exercises. Note - these are not practice questions -just some exercises to text your knowledge.

For this assessment you need three images - to be provided to your school beforehand:

• An image of your development process (Kanban board or github commits summary)
• An image of some sample code
• An image of you programme GUI (or output if non-gui based)

The past papers give a good guide to what is expected in the assessment. Some tips are below:

You will have made decisions during your project that affect both the outcome (your final'thing'),and the development process itself (how you went about managing your project). You also will have made decisions about the tools and techniques used as you made your outcome.

The development process includes:

• Planning with your stakeholder to find their needs
• Programming sprints
• Meeting with your stakeholder to get feedback
• Testing
• Improvements

Tools include:

• Github Kanban board
• Github code repository
• Replit
• Any other programme

Techniques include:

• Using csv file storage or serialization or hashmaps
• Making objects and classes
• Error correction
• Using the GUI editor

The questions have previously asked:

• For a brief description of your outcome and what it's purpose/function is
• How decisions you have made (referring to tools and techniques) have affected/are linked/can be seen in the final outcome.
• How decisions you have made (referring to tools and techniques) have affected/are linked/can be seen in the development process.
• What changes you made to any of these decisions as you developed your outcome, and why
• The contribution of stakeholder feedback to the outcome and the process.
• What you have learned during the process.
• What you would do differently - for both the development process and the outcome, if given the chance.
• How your outcome addressed relevant implications/end user considerations.

These questions may ask you to:

• Describe
• Explain (with reasons - I did this because)
• Evaluate/Analyse (positives and negatives, include some judgements - ie better worse)

• Read through the whole paper first - the questions are not long so this will not take too much time.
• Refer to specific examples of your work.
• Imagine you are explaining this to your Y7/8 homeroom teacher (i.e. smart enough to understand but knows very little about the subject)
• Use: because, this means that, so that - this is an easy step up from A to M

2023 DCAT A

2023 DCAT B

2022

2021

2020

2019

NZQA page including past reports and exemplars