Data Structures and Algorithms Reference Document

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 several weeks crowd-sourcing the development of a reference guide 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. Priority Queues - Previously Covered
5. Trees
• Binary Search Trees
• AVL Trees
• B Trees
• Red Black Trees
6. Heaps
7. Hash Tables (aka Hash Maps, Dictionaries)
8. Linked Lists
9. Graphs
• Adjacency Matrix
• Adjacency List
10. 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

Project #1 - Documenting what we  have studied so far

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

First Draft (Due to me by Friday, December 1st)

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 me a PDF, Word doc, or Google Doc link of your deliverable by NO LATER THAN the end of the day on Friday, December 1st.

Peer Review (Due to me by Friday, December 8th)

On the same day that you send ME your first draft I would like you to send a copy to your assigned peer review partner. About the same time, you should be getting their first draft for you to examine.

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 both me and your partner your feedback NO LATER THAN the end of the day on Friday, December 8th.

Final Version (Friday, December 15th)

You will receive feedback from your peer partner and possibly from me as well. You should consider that feedback carefully. If they 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 following document under the appropriate heading.  This should be done as a copy/paste from your original source document. NOTE: Do NOT use this linked document as a place to edit/build/write your deliverable.

• Data Structures and Algorithms Reference Document Project (Shared Google Document)

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.]

Project #2 - Topics we haven't studied yet

You will be assigned one of the data structures or algorithms that we have NOT already studied this semester. Repeat the process above for this new topic. This has identical deliverables and timelines as the previous project. You will actually be doing them in parallel. However, this one is likey going to be a bit more difficult because neither you, nor your partner, will know much about this other than what you research/write.

• First Draft - December 1st
• Peer Review - December 8th
• Final Version - December 15th