Sprint 3: More Data Structures

Roadmap:

• Teams
• Sprint Duration: Tuesday, March 22 - Thursday, April 12
• Quiz: Thursday, April 12
• Requirements due:
  • Problem sets: Beginning of class on Tuesday, April 10
  • Programming assignment: Tuesday, April 17

Rationale:

Algorithmic problems may look very different from the outset yet have very similar properties. For example, consider:

• Problem 1: Given a map of cities and landmarks in North Carolina with distances between them, find the shortest route between Elon and Charlotte.
• Problem 2: Given the exchange rates of European countries, find a way to exchange money in a certain sequence in order to make a profit.

It turns out that both these problems can be modeled with the same data structure - a graph. Once the graph is created, it is clear that the solutions to the two seemingly disparate problems is the same - finding the shortest route between vertices in the graph.

This is the power of data structures and algorithms. You will learn models for abstracting real-world problems, and the algorithms for finding efficient solutions to common problems with those models. In this way you can be presented with novel, real-world problems that have already well-known and well-studied solutions.

Responsibilities (What you need to know):

• Binary Search Trees
  • Definition: Tree property - all children on left smaller than root, and all children on right larger than root
  • Potential range of BST Height - from n to lgn
  • Algorithms:
    • Search, Insert, O(h)
    • Successor, leading to Delete O(h)
• Hash Tables
  • Goal: Insert, find, delete (key, value) pairs in O(1) time
  • Direct Addressing. Impractical.
  • Two main implementation schemes: open-address and chaining
    • Open-address: Tricky to delete. Collisions require a re-probing algorithm.
    • Chaining: Easier to implement, but can waste space and requires dynamic space allocation.
• Graphs
  • Definitions: Vertices, Edges, in-degree, out-degree, weighted vs non-weighted, sparse vs dense, directed vs non-directed, trees, source, sink
  • Note: all analyses are now in terms of V and E (number of vertices and number of edges)
  • Two main ways of implementing a graph: Adjacency list and adjacency matrix (Know pros and cons of each)
  • Basic graph traversal algorithms: Depth-first and Breadth-first (both O(E + V))
    • DFS: Useful for finding connectivity of graphs, cycles in graphs, and topological sorting
      • Know how to find pre and post numbers based on DFS
      • Know how to categorize edges as back, forward, tree, or cross
      • Know how to algorithmically compute topological sorts
    • BFS: Useful for finding shortest paths in unweighted graphs
      • Be able to hand-simulate BFS for any graph
  • Shortest-path algorithm: Dijkstra's
    • O((E+V)(lgV))
    • Useable only when edge weights are positive
    • Be able to hand-simulate Dijkstra's showing the priority queue and the parent hashmap.
    • Bellman-Ford - simple extension to work for negative-weight cycles as well

Requirements (What you need to do):

Individual Requirements:

• Understand the concepts on the Responsibilities list.
• Implement Dijkstra's Algorithm

Team Requirements:

• Complete the Problem Set on Binary Search Trees & Hash Tables
• Complete the Problem Set on Graphs

Individual Extra Credit:

• Research either a sort algorithm from last sprint that we did not cover, or a balanced tree implementation, and turn in a paper with the following information about the algorithm or data structure:
  • Name & when it was developed
  • Running time(s)
  • Overview of how the it works (pseudocode or few English sentences)
  • Detail example showing me step-by-step how it works
  • Analysis of the strengths and weaknesses (when would I use it?)

Resources: (Expert Request)

• Textbook readings:
  • Binary Search Trees
  • Hash tables
  • Graphs - Implementation and DFS
  • Paths in graphs (BFS & Dijkstra's)
• Practice:
  • Practice Problems on BSTs and Hashtables
  • Solutions to Practice on BSTs and Hashtables
  • Practice Problems on Graphs
  • Solutions to Practice on Graphs
  • Practice Quiz
  • Practice Quiz Solution
• Lecture Notes:
  • Binary Search Trees
  • Hash Tables
  • Basics of Graphs and Depth-first search
  • Paths in Graphs: Breadth-first and Dijkstra's
• Videos / Algorithm Visualizations:
  • Binary Search Trees
  • Hash Tables
  • Trees
  • Graphs (Here's the intro, then follow his playlist)
  • VisualAlgo has stuff on BSTs, Hash tables, and Graphs. (SS Shortest path = Dijkstra's)

Reality Check:

• Tuesday, March 27: Sprint Planning & overview of BSTs. For homework, read Chapter on Binary Search Trees & try problem set questions on Binary Search Trees.
• Thursday, March 29: Answer questions on BSTs, and do practice problems. Give overview of Hashtables. For homework, finish problem set on BSTs and Hashtables.
• Tuesday, April 3: Turn in problem set 1. Answer questions on Hashtables and give overview of Graphs. For homework, start problem set on Graphs.
• Thursday, April 5 (Convocation): Turn in problem set 2 (whatever you have). Go over path algorithms. For homework, work on programming project and finish up problem sets.
• Tuesday, April 10: Turn in both problem sets with corrections. Go over answers and review for the quiz. If time, work on programming project. For homework, practice & review for quiz.
• Thursday, April 12: Quiz. (Finish Dijkstra's for Tuesday.)