- 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
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:
Team Requirements:
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?)
- Textbook readings:
- Practice:
- Lecture Notes:
- Videos / Algorithm Visualizations:
- 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.)