In addition to ensuring that the programs they implement are correct and maintainable, algorithm engineers must confirm that their code is efficient. The focus of this course — called “algorithmology” for fun! — is the study of algorithms, with a concentration on both their correctness and efficiency. The process of algorithmology requires the completion of tasks that leverage knowledge and skills in both engineering and science. For instance, an algorithm engineer needs to design, implement, and test data structures and algorithms and then correctly integrate them into a working software system. However, an algorithm engineer must also employ the scientific method to analyze the efficiency of both a software system’s components and the system as a whole. This course introduces learners to both empirical and analytical approaches to studying the efficiency of algorithms, data structures, and the software systems that contain them.
Course Overview
With the goal of enabling the growth of algorithm engineers, this web site features a sixteen-week schedule filled with activities that support the development of your professional and technical capacities in the field of algorithm analysis. Although this site is best used by an on-campus learner in the Department of Computer and information Science at Allegheny College, the resources and projects are all publicly available. For instance, this course leverages and extends the open-access course textbook called A First Course on Data Structures in Python. You can access all of the source code and technical content for this book by checking out its GitHub repository and following along with the schedule and the slides for this course, as found on this site.
Wow, Python Source Code … and its Output!
As you browse the technical resources on this site you will notice that they often contain both Python source code and the output from running code. For instance, here is the source code for a duplicates function that uses a double-nested for loop to determine whether or not the input_list contains a duplicate int value. This source code segments shows that both print(duplicates([1,2,6,3,4,5,6,7,8])) and print(not duplicates([1,2,3,4])) yield True as their output! Pretty cool, huh?
from typing import Listdef duplicates(input_list: List[int]) ->bool:"""Determine whether or not the input list contains a duplicate value.""" n =len(input_list)for i inrange(n):for j inrange(n):if i != j and input_list[i] == input_list[j]:returnTruereturnFalse# use assertions to confirm that duplicates# works as expected; note that assert only# produces output if the condition is Falseassert(duplicates([1,2,6,3,4,5,6,7,8]))assert(not duplicates([1,2,3,4]))# display the output of the functions calls# to show that the output appears inlineprint(duplicates([1,2,6,3,4,5,6,7,8]))print(not duplicates([1,2,3,4]))
True
True
Throughout this site, the source code that appears in the top-most region of a page is available for use in later sections of the same page. For instance, the following code defines a new timetrials function that can be used to time the duplicates function in a doubling experiment. Wow, check it out! The output from running the following function will produce a data table that reveals that the likely worst-case time complexity of duplicates is \(O(n^2)\). Are you wondering how the data shows that duplicate is \(O(n^2)\)? Well, you can use the data in the table to compute 0.23 / 0.05 = 4.6, which suggests that as the input size doubles, the time more than quadruples. To learn more about this topic, you can use the technical content in the course to learn how to analyze the time complexity of algorithms — so check out the schedule and the slides for more details!
from typing import Callable, Listimport timedef timetrials(function: Callable, n: int, trials: int=10) ->float:"""Time a function with an input of size n for trials number of times.""" totaltime =0for _ inrange(trials): start = time.time() function(list(range(n))) totaltime += time.time() - startprint("Average time =%10.7f (s) for n = %d"% (totaltime/trials, n))return totaltime/trials# conduct a doubling experiment for a provided functiontimings = []for n in [50, 100, 200, 400, 800, 1600, 3200]: timings.append(timetrials(duplicates, n))
Average time = 0.0001487 (s) for n = 50
Average time = 0.0005753 (s) for n = 100
Average time = 0.0023825 (s) for n = 200
Average time = 0.0090230 (s) for n = 400
Average time = 0.0358378 (s) for n = 800
Average time = 0.1396165 (s) for n = 1600
Average time = 0.5623716 (s) for n = 3200
Resources for an Adventure in Algorithmology
Interested in getting started on a developer development adventure? Begin here:
The sixteen-week course schedule offers detailed insights into each step that learners should take to help them to emerge as algorithm engineers, including a list of reading assignments and descriptions of various algorithm engineering projects.
The course syllabus introduces the course and its learning objectives and explains how on-campus learners will be assessed by the course instructor.
The algorithm all-hands reports includes articles written by learners as they explore the engineering and scientific knowledge and skills in the field of algorithmology. While some of these articles report on the results from running experiments, others explain how to implement and use the Python programs that supports performance evaluation. Read these reports to learn more about the algorithmology!
