forked from akuchling/50-examples
-
Notifications
You must be signed in to change notification settings - Fork 0
/
TODO
88 lines (76 loc) · 2.43 KB
/
TODO
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
Structure
---------
Each example is no more than 5-10 pages.
Aiming for 50 examples, or 30-60.
Uses Python3 and the turtle module for graphics throughout.
May use third-party libraries to avoid having re-implement basic
data structures from scratch.
Look through: the A.K. Dewdney books; Cormen-Leiserson-Rivest; Sedgewick.
To be written
-------------
* Introduction
* Glossary?
* (done) Background: Plotting with turtle graphics
* (done) Background: Algorithms
* (done) Background: Computational complexity
* Turtle graphics reference card
* Given N numbers, find the M smallest or largest.
* Minimax game trees: tic-tac-toe or Hnefatafl?
* Graphs: analyzing social networks
* Tree search: assemble a binary tree and then search it.
* Audio manipulation
*** Evening out the volume level.
*** Apply an FFT or filtering.
*** Music composition
*** References: Software Carpentry course: http://software-carpentry.org/4_0/media/audio/
* Markov chaining
* RSA encryption
* Calculate asset allocation of a portfolio
* Random numbers: calculating pi by random numbers
http://en.wikipedia.org/wiki/Pseudorandomness#Monte_Carlo_method_simulations
* Queuing: simulate a grocery store and a bank queue.
* Simplex programming
* Graphics
*** Rendering fractals
*** (done) Gravitational simulation
*** (done) Game of Life
*** Spline curves
*** Photo manipulation
***** Stretching/shrinking an image
***** Smart shrinking
***** Modify contrast/brightness.
Other tasks
-----------
* Standardize markup for functions/methods (e.g. see the turtle section for
problems.)
* Put copyright/license info in the template & all the files.
* Draw all of the diagrams needed.
* Prepare an epub version.
Vague ideas
-----------
* Simple neural network?
* Something with distributed computation?
* Divide-and-conquer?
* Playing poker?
* Modules to show: difflib; sqlite3
* Data structures: heaps, XXX
* Geometric data structures: XXX
*** Gerrymandering http://rangevoting.org/GerryExamples.html
* Graphs
* Graph concepts
* Different graph representations (Node objects, sets of arcs)
* Traversal
* Topological sorts
* Example: working out file dependencies
* Connected-components
* Spanning trees
* Shortest paths
Hard problems: NP-completeness
* P and NP
* NP-completeness
* Explanation
* Various examples of NP-complete problems
* Show that all NP-complete problems are equivalent
* Solving an NP-complete problem
* Exhaustive search
* Heuristics