This algorithmic essay template is for students of data structures and algorithms (DSA) courses. Throughout the template, there are links to relevant sections of our Writing and Coding Guide. Replace any text in italics by yours and delete this paragraph.

Your essay's title¶

Your (and any co-author's) name, current date

The introduction explains what the essay is about, the problem you are solving, and what you assume the reader to know. See our guidance on choosing a problem, writing the text and structuring the essay. This template follows the first structure in the guide. You don't need to change the following code cells.

In [ ]:

import os

if 'COLAB_GPU' in os.environ:  # if we are in Google Colab...
    !pip install algoesup --no-deps
    !pip install allowed ruff pytype

import os if 'COLAB_GPU' in os.environ: # if we are in Google Colab... !pip install algoesup --no-deps !pip install allowed ruff pytype

In [ ]:

from algoesup import test, time_cases, time_functions

from algoesup import test, time_cases, time_functions

For information on what the following commands do, see our guide's sections on type checking and linting and remove this paragraph.

In [ ]:

%load_ext algoesup.magics
# check the code's style
%ruff on
# check the data types
%pytype on
# optional: flag the Python constructs not taught in M269, our DSA course
%allowed on

%load_ext algoesup.magics # check the code's style %ruff on # check the data types %pytype on # optional: flag the Python constructs not taught in M269, our DSA course %allowed on

1 Tests¶

This section describes and defines the tests you will use to check your solutions. See the testing section of our guide.

In [ ]:

tests = [
    # Each line is a list or tuple of the form:
    # (description, input1, input2, ..., expected_output),
]

tests = [ # Each line is a list or tuple of the form: # (description, input1, input2, ..., expected_output), ]

2 Algorithms¶

This section outlines some algorithms that solve the problem. See the algorithms section of our guide.

2.1 First algorithm name¶

Describe your first strategy or approach.

Algorithm 1: Briefly describe your first algorithm.

Analyse at least the worst-case time complexity of your first algorithm.

2.2 Second algorithm name¶

Describe your second strategy or approach.

Algorithm 2: Briefly describe your second algorithm.

Analyse at least the worst-case time complexity of your second algorithm.

2.n nth algorithm name¶

Describe your nth strategy or approach.

Algorithm n: Briefly describe your nth algorithm.

Analyse at least the worst-case time complexity of your nth algorithm.

2.n+1 Summary¶

This section compares the previously outlined algorithms to inform implementation decisions.

3 Code¶

This section implements and tests only the most promising algorithms. See the code section of our guide.

In [ ]:

# Replace solution_one with a more descriptive name.
def solution_one():
    # Implement your solution here
    pass

test(solution_one, tests)

# Replace solution_one with a more descriptive name. def solution_one(): # Implement your solution here pass test(solution_one, tests)

In [ ]:

# Replace solution_two with a more descriptive name.
def solution_two():
    # Implement your solution here
    pass

test(solution_two, tests)

# Replace solution_two with a more descriptive name. def solution_two(): # Implement your solution here pass test(solution_two, tests)

In [ ]:

# Replace solution_n with a more descriptive name.
def solution_n():
    # Implement your solution here
    pass

test(solution_n, tests)

# Replace solution_n with a more descriptive name. def solution_n(): # Implement your solution here pass test(solution_n, tests)

4 Performance¶

This section measures and compares the run-times of your implementations, so that you can check them against your earlier complexity analysis.

4.1 Generating inputs¶

Briefly describe your strategy and reasoning for generating the inputs.

In [ ]:

def best_case(size: int) -> tuple[...]:
    # Implement your best-case input generator here.
    pass

def best_case(size: int) -> tuple[...]: # Implement your best-case input generator here. pass

In [ ]:

def worst_case(size: int) -> tuple[...]:
    # Implement your worst-case input generator here.
    pass

def worst_case(size: int) -> tuple[...]: # Implement your worst-case input generator here. pass

In [ ]:

def normal_case(size: int) -> tuple[...]:
    # Implement your normal-case input generator here.
    pass

def normal_case(size: int) -> tuple[...]: # Implement your normal-case input generator here. pass

4.2 Best, normal and worst run-times¶

State which solutions(s) will be timed with best-, normal- or worst-case inputs. See the comparing cases and charting run-times sections of our guide.

In [ ]:

cases = [best_case, normal_case, worst_case]
# Change solution_n to the name of your solution.
time_cases(solution_n, cases, start=10, double=4)

cases = [best_case, normal_case, worst_case] # Change solution_n to the name of your solution. time_cases(solution_n, cases, start=10, double=4)

Analyse the results. See the interpreting run-times section of our guide.

4.3 Fastest and slowest algorithm¶

Compare the run times of all your solutions for the same case. See the comparing functions and charting run-times sections of our guide.

In [ ]:

# Change solution_one, solution_two, and solution_n to the names of your solutions.
algorithms = [solution_one, solution_two, solution_n]
# Replace normal_case with best_case or worst_case, if you wish.
time_functions(algorithms, normal_case, 1000, 4, chart=True)

# Change solution_one, solution_two, and solution_n to the names of your solutions. algorithms = [solution_one, solution_two, solution_n] # Replace normal_case with best_case or worst_case, if you wish. time_functions(algorithms, normal_case, 1000, 4, chart=True)

Analyse the results. See the interpreting run-times section of our guide.

5 Concluding remarks¶

Summarise your findings and conclude which solution is best.

After completing a draft of your essay, do a final check and then see the feedback guide on how to ask for, give, and handle comments.

6 Acknowledgements¶

Credit those who helped you create the essay. See the crediting feedback section of our guide.