Data Structures and Algorithms Encyclopedia Project

You may recall that one of the stated goals of this course is that you become aware of a wide variety of data structures and algorithms.  It was not our goal that you memorize every common data structure or "classic" algorithm.  But, we do think it is important that you have an idea that they exist and have experience with many of them.  We also think it is important that you are able to research a new topic and digest the materials you find into something meaningful for you, your students, and, in this situation, your peers.

In order to give you something that you can take away from this course and actually use in the future, we are going to spend parts of the last few weeks crowd-sourcing the development of a reference guide/encyclopedia for many of the following common data structures and algorithms.

Common Data Structures

1. Arrays - Previously Covered
2. Stacks - Previously Covered
3. Queues - Previously Covered
4. Deques - Previously Covered
5. Priority Queues - Previously Covered
6. Trees
• Binary Search Trees
• AVL Trees
• B Trees
• Red Black Trees
7. Heaps
8. Hash Tables (aka Hash Maps, Dictionaries)
9. Linked Lists
10. Graphs
• Adjacency Matrix
• Adjacency List
11. Tries (a variation of trees worth calling out separately)

Common Algorithms

1. Searching and Sorting
• Linear Search - Previously Covered
• Binary Search - Previously Covered
• Insertion Sort - Previously Covered
• Selection Sort - Previously Covered
• Bubble Sort - Previously Covered
• Quick Sort - Previously Covered
• Merge Sort - Previously Covered
2. Graph Search Algorithms
• Breadth First Search - Previously Covered
• Depth First Search - Previously Covered
• A* Search (Informed Search) - Previously Covered
• Dijkstra's Algorithm (Shortest Path from source to all vertices)
• Floyd Warshall (Shortest Path from every vertex to every other vertex)
• Prim's Algorithm (Minimum Spanning Tree)
• Kruskal's Algorithm (Minimum Spanning Tree)
3. Dynamic Programming
• MiniMax Algorithm
• Longest Common Subsequence
• Longest Increasing Subsequence
• Set Partition
• 0-1 Knapsack Problem

Since we have such a large group this semester, we are going to divide into three different reference guides. Right now you will only have access to your guide. But when the project is over you will get access to all three guides.

• Guide #1 (Members of Central Rivers)
• Guide #2 (Members of Grant Wood)
• Guide #3 (Northwest AEA and the remaining teams)

You have all been assigned a partner (or in a few cases, groups of three) and everyone has a team code.

Using this information, you will complete the project by performing the following steps on the following schedule.

Project #1 - Documenting what we  have studied so far

Each team will be assigned one (or more) of the data structures/algorithms that we have already studied this semester.  Those assignments are as follows:

* NOTE: Teams in Bold are groups of three that have an extra assignment this round.

First Draft (Due by Wednesday, November 27th, 11:59 PM)

You should research your assigned topic. This includes:

• re-study your topic from the course materials
• Google your topic and see what else you can find
• identify resources you think are well written and help you (and by extension, your peers and your/their students) understand the topic
• find examples of how your topic is applied/used
• look for illustrations/simulations/animations that help you understand what is going on.

Once you have completed some thorough research you should produce a document that you feel summarizes the things you have learned/found.  This document likely includes, but is not limited to, the following topics:

1. A written description/summary of the topic. 
• How and why it "works"
• Where it often used in computer science
• Comparisons to other topics that might be in this document
2. At least one code representation of the topic (it may be helpful to have BOTH):
   • Pseudocode of the topic
   • Standalone python implementation
3. At least two classroom appropriate examples/applications with the underlying code and data
• The idea here is that someone can use your code and immediately start fiddling with examples
4. A bibliography of helpful references/links

You want to think about this assignment less like a "classroom essay" and more like a "book chapter" or "study document"  The actual format and content will likely swing fairly widely for this first part of the document depending on what your topic really is.  But the goal is that you take the time to produce something HELPFUL for your peers and, collectively, your students.

For this deliverable I would like you to email a PDF, Word doc, or share a Google Doc link of your deliverable by NO LATER THAN the end of the day on Wednesday, November 27th with:

• me
• your peers who were assigned to conduct your peer review
  • For example, if you look at this small snip from the table above, Bridget and Dalton(who are G1-T6) would write their article about Stacks, and by November 27th they would email this to me, as well as Ann, Kimberly, and Sherri (who are G1-TB)

  • Topic	Guide 1
    	Authors	Peer Review
    Stacks	G1-T6	G1-TB

Peer Review (Due by Wednesday, December 4th, 11:59 PM)

By Wednesday, November 27th you should receive a copy of a draft article from another group (see above).

Go through their writeup carefully. Make detailed notes that you can share with the author to help them improve their document. Some of these notes could include:

• Spelling or punctuation errors
• Notes about incomplete sentences or thoughts
• Things that confused you
• Assigned sections that you feel that they haven't covered yet or adequately
• Ideas you have about their topic based on their write-up that you feel they might include or take into consideration

In other words, as a fellow teacher, how can you help them improve this write up.

For this deliverable I would like you to email the original authors your feedback (or leave using the commenting tool in Google Docs) NO LATER THAN the end of the day on Friday, December 4th.

Final Version(Due by Wednesday, December 11th, 11:59 PM)

You will receive feedback from your peers, and possibly from me as well. You should consider that feedback carefully. If we have something to say that you agree improves your deliverable, you should revise your write-up. It is NOT necessary that you make every change/improvement that they suggest. But you should make such decisions very carefully and deliberately.

When you feel your work is completed you should add your final version to the appropriate document and under the appropriate heading.  This should be done as a copy/paste from your original source document. NOTE: Do NOT use the large group's document as a place to edit/build/write your deliverable. Please be careful not to delete anyone else's work.  [One of the reasons I am having you only cut and paste at the end is that I want to be able to easily "retrieve" work that gets accidentally destroyed by others.]

• Guide #1 (Members of Central Rivers)
• Guide #2 (Members of Grant Wood)
• Guide #3 (Northwest AEA and the remaining teams)

Project #2 - Topics we haven't studied yet

Once that you have gotten the hang of this process with a data structure or algorithm that was somewhat familiar to you, we will be working on a second topic which is new to you. Repeat the process above for this new topic. This has identical deliverables and expectations as the previous part of the project. You will actually be doing them in parallel. However, this one is likely going to be a bit more difficult because neither you, nor your partner, will know much about this other than what you research/write.

* NOTE: Teams in Bold are groups of three that have an extra assignment this round.

• First Draft - Due by Wednesday, December 4th, 11:59 PM
• Peer Review - Due by Wednesday, December 11th, 11:59 PM
• Final Version - Due by Wednesday, December 18th, 11:59 PM