forked from Algorithmology/www.algorithmology.org
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.qmd
138 lines (117 loc) · 6.36 KB
/
index.qmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
---
title: Algorithmology
layout: full
toc: false
---
{fig-align="center"}
## Welcome to an Adventure in Algorithm Analysis!
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](https://www.cs.allegheny.edu/) at [Allegheny
College](https://www.allegheny.edu/), 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](https://github.com/donsheehy/datastructures). 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](schedule/index.qmd) and the
[slides](slides/index.qmd) 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?
```{python}
from typing import List
def duplicates(input_list: List[int]) -> bool:
"""Determine whether or not the input list contains a duplicate value."""
n = len(input_list)
for i in range(n):
for j in range(n):
if i != j and input_list[i] == input_list[j]:
return True
return False
# use assertions to confirm that duplicates
# works as expected; note that assert only
# produces output if the condition is False
assert(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 inline
print(duplicates([1,2,6,3,4,5,6,7,8]))
print(not duplicates([1,2,3,4]))
```
Thought this site, the source code that appears in an 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](schedule/index.qmd) and the [slides](slides/index.qmd) for more
details!
```{python}
from typing import Callable
import time
def timetrials(function: Callable, n: int, trials: int = 10) -> List[float]:
"""Time a function with an input of size n for trials number of times."""
totaltime = 0
for _ in range(trials):
start = time.time()
function(list(range(n)))
totaltime += time.time() - start
print("Average time =%10.7f (s) for n = %d" % (totaltime/trials, n))
return totaltime/trials
# conduct a doubling experiment for a provided function
timings = []
for n in [50, 100, 200, 400, 800, 1600, 3200]:
timings.append(timetrials(duplicates, n))
```
## Resources for an Adventure in Algorithmology
Interested in getting started on a developer development adventure? Begin here:
- The [sixteen-week course schedule](./schedule/index.qmd) 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](./syllabus/index.qmd) 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](./allhands/index.qmd) 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!
::: {.callout-note appearance="minimal" title="Algorithmology Community Resources"}
Interested in connecting with other like-minded algorithm engineers? Please join
the [Algorithmology Discord Server](https://discord.gg/phSQfB8bZx) and join the
conversation! If you are an on-campus learning at Allegheny College, you may
also join the [Allegheny College Computer Science Discord
Server](https://discord.gg/CS2h9kXzX6). Finally, if you are an on-campus
learner, then you may schedule a meeting with the course instructor during
office hours by visiting the [Course Instructor's Appointment
Scheduler](https://www.gregorykapfhammer.com/schedule/).
:::