TODO List¶
No Category
source: ListADT
Todo
tag: | Exercise |
---|
This exercise ought to get expanded to a much richer set of variations on the question.
source: ExchangeSort
Todo
tag: | Revision |
---|
Rewrite along these lines: Here are two measures of "out of order": inversions and min-swaps. Selection sort (especially w/ optimization) meets min-swaps, but that's not a useful measure in general. Insertion sort tracks inversions, it is I + n. Now, if we had an exchange sort, what would cost be? Go on to the proof.
source: SortOpt
Todo
tag: | Revision |
---|
Rewrite along these lines: A classic form of code tuning is "test to save work". For each of our three sorting algorithms, we have a potential "test to save work" "optimization". The question is: When is the cost of test worth the work saved? Let's look at each of the three.
AV
source: AnalIntro
Todo
type: | AV |
---|
To make students more engaged in the GrowthRates exercise, we may need a tool that allows students to input two growth rate functions. Then the tool should plot the graph of both functions and mark their crossing point. The student also should be allowed to play with the constant values for both functions and see that this only changes the crossing point but doesn't change which function grows faster than the other.
source: HashCImproved
Todo
type: | AV |
---|
Fix and return hashAV.html to here.
The following visualization lets you test out different combinations of hash function and collision resolution, on your own input data.
source: GraphTopsort
Todo
type: | AV |
---|
Provide a unified AV that can allow the user to pick which topsort
(DFS or Queue), with or without cycles in the graph. The start of
this is in AV/Development/topSortAV*
(for just random DFS),
AV/Development/qTopSortAV.*
(for just random queue-based
topsort), and AV/Development/topsortAVs*
(tries to unify).
source: GraphShortest
Todo
type: | AV |
---|
Provide an AV that runs on a random graph. An initial version is in
AV/Development/dijkstraAV.*
.
source: GraphShortest
Todo
type: | AV |
---|
AV here to demonstrate the minVertex implementation.
source: KDtree
Todo
type: | AV |
---|
Add version where you can click to get the node inserted.
source: PerfectHash
Todo
type: | AV |
---|
Make a proper visualization for perfect hashing, that lets the user specify a set of input keys, computes the hash function, then lets the user input keys to the table. A proper explanation for the process should be part of the visualization.
source: FFT
Todo
type: | AV |
---|
Practice fft algorithm. Maybe only practice the final for loop since the rest of the algorithm is recursivly dividing the polynomial and performing fft on the smaller polynomials.
BlockPy
source: Iteration
Todo
type: | BlockPy |
---|
Put first BlockPy exercise here.
source: Iteration
Todo
type: | BlockPy |
---|
Put second BlockPy exercise here.
source: Iteration
Todo
type: | BlockPy |
---|
Put third BlockPy exercise here.
Code
source: GraphShortest
Todo
type: | Code |
---|
Why does the code look for an unvisited value first? Is there an easier way?
Drawing
source: DFA
Todo
type: | Drawing |
---|
Show the minimal form of the next drawing without trap state, etc.
Equation cross-reference
source: Recurrence
Todo
type: | Equation cross-reference |
---|
Throughout this module, there are references to equations, both on this page and in the Summations module. These should be made into proper cross-references rather than hard-coded equation numbers.
Exercise
source: ListDouble
Todo
type: | Exercise |
---|
Need exercises for inserting to and deleting from doubly linked lists.
source: HuffProof
Todo
type: | Exercise |
---|
Battery of MCQs for content.
source: Quicksort
Todo
type: | Exercise |
---|
Consider the Quicksort implementation for this module, where the pivot is selected as the middle value of the partition. Give a permutation for the values 0 through 7 that will cause Quicksort to have its worst-case behavior.
There are a number of possible correct answers. To assess the answer, will need to run Quicksort over student's partition, and verify that at each step it will generate new partitions of size 6, 5, 4, 3, 2, then 1.
source: IndexingSumm
Todo
type: | Exercise |
---|
This is a good question, but its not nearly enough for a chapter summary.
source: GraphImpl
Todo
type: | Exercise |
---|
Add a battery of questions to test knowledge of the implementations.
source: GraphTraversal
Todo
type: | Exercise |
---|
Summary exercise for graph traversals.
source: GraphShortest
Todo
type: | Exercise |
---|
Summary battery of questions for Dijkstra's algorithm
source: MCST
Todo
type: | Exercise |
---|
Proficiency exercise for Prim's algorithm.
source: Kruskal
Todo
type: | Exercise Summary battery of questions for Prim's and Kruskal's algorithms. |
---|
source: Impossible
Todo
type: | Exercise |
---|
Need an exercise to study lower bound on Colletz function
Explanation
source: LinearIndexing
Todo
type: | Explanation |
---|
The slideshow should subsume the next paragraph and the caption.
Figure
source: Garbage
Todo
type: | Figure |
---|
Replace this figure with an applet that demonstrates the use of handles.
source: DPDA
Todo
type: | Figure |
---|
Show figure
Proficiency Exercise
source: GraphTopsort
Todo
type: | Proficiency Exercise |
---|
Provide a proficiency exercise that randomly alternates between
proficiency for DFS-based and queue-based Topsort.
The bare beginnings of an exercise can be found in
AV/Development/topSortDFSPE.*
Question
source: FLConcepts
Todo
type: | Question |
---|
Is this really correct? In this example, x is a single non-terminal. In general, we can't have just a terminal on the left side, can we? Later, more complicated grammars might have a series of things on the left side with suitable restrictions. Do we want to bring that up here?
Slideshow
source: AnalProgram
Todo
type: | Slideshow |
---|
We need to think about a technique for visualizing the running time of some loop constructs. This can be very similar to how we visualize reaching the closed form solution of summations.
source: StackRecur
Todo
type: | Slideshow |
---|
The figure above and the following text should all be rolled into a slideshow.
source: SortNotation
Todo
type: | Slideshow |
---|
The preceding paragraph could be turned into a slideshow.
source: Garbage
Todo
type: | Slideshow |
---|
Replace this figure with a slideshow that demonstrates the use of reference counts (including the problem with cycles).
source: Garbage
Todo
type: | Slideshow |
---|
Put here a visualization that demonstrates the use of reference counts.
source: Garbage
Todo
type: | Slideshow |
---|
Replace this figure with an AV that demonstrates DSW.
source: GraphTopsort
Todo
type: | Slideshow |
---|
Replace the above figure with a slideshow that incorporates the following paragraph.
source: GraphTopsort
Todo
type: | Slideshow |
---|
Replace the following paragraph with a slideshow.
source: GraphTopsort
Todo
type: | Slideshow |
---|
Incorporate the following into a slideshow.
source: GraphShortest
Todo
type: | Slideshow |
---|
Incorporate the following paragraph into a slideshow with the figure below it.
source: GraphShortest
Todo
type: | Slideshow |
---|
Provide a slideshow to demonstrate the following example.
source: GraphShortest
Todo
type: | Slideshow |
---|
This slideshow illustrates Dijkstra's algorithm using the heap. The start vertex is A. All vertices except A have an initial value of \(\infty\). After processing Vertex A, its neighbors have their D estimates updated to be the direct distance from A. After processing C (the closest vertex to A), Vertices B and E are updated to reflect the shortest path through C. The remaining vertices are processed in order B, D, and E. Changes in the D array should be shown along with this.
source: GraphShortest
Todo
type: | Slideshow |
---|
Slideshow to demonstrate the relative costs of the two algorithms.
source: MCST
Todo
type: | Slideshow |
---|
Replace the previous diagram with a slideshow illustrating the concept of MCST.
source: MCST
Todo
type: | Slideshow |
---|
Implement a slideshow demonstrating the Priority Queue version of Prim's algorithm
source: Kary
Todo
type: | Slideshow |
---|
Slideshow of Book Figure 6.16: shows full and complete Karytrees for K=3. In practice, most applications of Karytrees limit them to be either full or complete.
Full and complete 3-ary trees. (a)~This tree is full (but not complete). (b)~This tree is complete (but not full).}{ThreeTree}
source: NFA
Todo
type: | Slideshow |
---|
Replace the images above with a slideshow that presents first the NFA, and then shows, step-by-step, the process of building the DFA.
source: Minimization
Todo
type: | Slideshow |
---|
Replace the images above with a slideshow that presents, step-by-step, the process of minimizing the DFA.
Summary Questions
source: GraphTopsort
Todo
type: | Summary Questions |
---|
Provide a summary battery of questions.
Text
source: HashAnal
Todo
type: | Text |
---|
Where did that last claim about the linear probing cost come from?
exercise
source: KDtree
Todo
type: | exercise |
---|
We need a proficiency exercise.
text
source: AnalTuning
Todo
type: | text |
---|
Give an example of this type of representational change.
source: PerfectHash
Todo
type: | text |
---|
Explain how Perfect Hashing works.