Advanced Data Structures & Algorithms with Python

Course Schedule

Course Dates: Monday, January 23 – Friday, March 3, 2017 (6 weeks)

Class Times: Monday, Wednesday, Friday 1–3pm (17 class sessions)

Class 1: Monday, January 23 – Exponents & Number Bases

Topics:

• review exponents, logarithms
• number bases slides: decimal, binary, hexadecimal
• negative integer representations: signed magnitude, ones' complement, two's complement

Challenges:

• practice number base conversions on worksheet
• implement base conversion functions for positive numbers using starter code and unit tests
• stretch: implement base conversion for negative numbers
• stretch: implement base conversion for fractional numbers

Class 2: Wednesday, January 25 – Recursion & Search Algorithms

Topics:

• compare iteration and recursion with factorial function
• searching algorithms: linear search and binary search
• review algorithm complexity analysis

Challenges:

• implement iterative factorial function using starter code and unit tests
• implement recursive linear and binary search algorithms using starter code and unit tests
• annotate functions with complexity analysis
• stretch: implement permutation and combination functions

Class 3: Friday, January 27 – String Algorithms

Topics:

• string searching, palindromes, anagrams

Challenges:

• implement string searching function (try multiple approaches)
• implement iterative and recursive palindrome checking functions using starter code and unit tests
• annotate functions with complexity analysis
• stretch: implement iterative and recursive anagram generating functions

Project:

• phone call routing: implement phone number prefix matching
• annotate functions with complexity analysis

Class 4: Monday, January 30 – List, Stack & Queue

Topics:

• compare abstract data types and concrete data structures
• abstract data types: list, stack, queue, deque
• concrete data structures: array, dynamic array (resizable array, vector), linked list

Resources:

• watch Make School's video lectures: linked list, stack and queue
• play with interactive visualizations: linked list, stack, queue, deque

Challenges:

• implement constant-time length function on linked list using starter code and unit tests
• implement stack with dynamic array and linked list using starter code and unit tests
• implement queue with dynamic array and linked list using starter code and unit tests
• annotate functions with complexity analysis
• stretch: implement deque with doubly linked list

Class 5: Wednesday, February 1 – Set, Map & Hash Table

Topics:

• abstract data types: set, multiset (bag), map (dictionary, associative array)
• concrete data structures: hash table
• bonus abstract data type: circular buffer

Resources:

• watch Make School's video lecture: hash table
• play with interactive visualizations: hash table

Challenges:

• implement set with hash table
• implement automatic resizing of hash table
• annotate functions with complexity analysis
• stretch: implement set operations union, intersection, difference, subset
• stretch: implement circular buffer with dynamic array and linked list

Class 6: Friday, February 3 – Trees

Topics:

• tree, binary search tree, operations

Resources:

• watch Make School's video lecture: tree
• play with interactive visualizations: binary search tree

Challenges:

• implement binary search tree with node objects
• implement search, insert, delete binary search tree operations
• annotate functions with complexity analysis
• stretch: implement binary search tree with singly linked list

Project:

• trees and mazes tutorial on Make School's Online Academy

Class 7: Monday, February 6 – Tree Traversals & Self-Balancing Trees

Topics:

• tree traversals: pre-order, post-order, in-order, level-order
• self-balancing trees with rotations: AVL tree, splay tree, red-black tree

Resources:

• watch Make School's video lecture: tree traversals

Challenges:

• implement iterative and recursive binary search tree traversals
• implement map (dictionary) with binary search tree
• annotate functions with complexity analysis
• stretch: implement AVL tree or splay tree with insert and search operations

Class 8: Wednesday, February 8 – More Self-Balancing Trees

Topics:

• n-ary tree
• self-balancing trees with multiple keys: 2-3 tree, B-tree
• space-partitioning trees: quadtree, octree, k-d tree

Challenges:

• implement 2-3 tree with insert and search operations
• annotate functions with complexity analysis
• stretch: implement n-ary search tree using dynamic array of siblings
• stretch: implement B-tree or k-d tree with insert and search operations

Class 9: Friday, February 10 – Iterative Sorting Algorithms

Topics:

• iterative comparison sorting: bubble, selection, insertion
• integer sorting: counting, bucket, radix

Resources:

• watch animations and this video of sorting algorithms to see patterns
• play with step-by-step interactive animations of sorting algorithms

Challenges:

• implement bubble, selection, and insertion sorts
• implement counting and bucket sorts
• annotate functions with complexity analysis
• stretch: implement insertion sort using binary search
• stretch: implement cocktail shaker or Shell sort

Project:

• sorting algorithms with real-world data on Make School's Online Academy

Class 10: Monday, February 13 – Divide-and-Conquer Recursion

Topics:

• divide-and-conquer recursion: divide, conquer, combine
• revisit binary search to see how it divides and conquers
• merge algorithm and merge sort

Challenges:

• implement merge sort with a separate merge algorithm
• implement tree sort with an appropriate search tree
• annotate functions with complexity analysis
• stretch: implement radix sort for integers and/or strings

Project:

• continue sorting algorithms with real-world data

Class 11: Wednesday, February 15 – Recursive Sorting Algorithms

Topics:

• recursive algorithm analysis with trees, recurrence relations, master theorem
• partition algorithm and quick sort
• stable sorting and adaptive sorting

Resources:

• watch these cute robot video animations: quick sort, merge sort vs. quick sort

Challenges:

• implement stable quick sort with a separate partition algorithm
• annotate functions with complexity analysis

Class 12: Friday, February 17 – Priority Queue & Heap

Topics:

• priority queue abstract data type
• heap data structure, binary heap representations
• heap sort, compare to insertion and selection sort

Resources:

• watch Make School's video lecture and review slides on heaps
• watch this cute robot video animation: heap and heap sort
• play with interactive visualizations: heap
• read about sorting algorithms implemented with priority queue

Challenges:

• implement binary min heap with dynamic array using starter code and unit tests
• implement heap sort with binary heap
• implement priority queue with binary heap
• implement priority queue with binary search tree
• annotate functions with complexity analysis
• stretch: implement stack with priority queue
• stretch: generalize binary heap with min or max initialization option

Class 13: Wednesday, February 22 – Graphs

Topics:

• graph abstract data type
• graph types: directed/undirected, weighted/unweighted, simple/multigraph
• graph applications: computer networking, social networking, airplane flight routing, map routing, search engines (PageRank), dependency planning, etc.
• graph representations: object references, edge list, incidence matrix, adjacency matrix, adjacency list, adjacency map

Resources:

• play with interactive visualizations: graph types and representations

Project:

• collect data set of social network, airplane routes, or your choice
• implement graph with appropriate representation for that data set

Class 14: Friday, February 24 – Graph Traversals & Spanning Trees

Topics:

• graph traversals: depth-first search, breadth-first search
• graph connectivity, connected components, strongly connected components
• graph spanning trees, minimum spanning trees:
  • Prim's algorithm
  • Kruskal's algorithm
• bonus data structure: trie (prefix/radix tree)

Resources:

• play with interactive visualizations: graph traversals, minimum spanning tree

Graph Project:

• implement graph traversals: depth-first search, breadth-first search
• implement an algorithm to find connected components on your graph data set
• implement an algorithm to find a minimum spanning tree on your graph data set
• annotate functions with complexity analysis

Trie Project:

• implement trie with insert and prefix search operations
• revisit phone call routing scenarios 3, 4, and 5 with trie
• annotate functions with complexity analysis

Class 15: Monday, February 27 – Graph Algorithms

Topics:

• shortest path problem:
  • A* search algorithm
  • Dijkstra's algorithm
  • Bellman–Ford algorithm
  • Floyd–Warshall algorithm
• maximum flow problem:
  • Ford–Fulkerson algorithm
  • Edmonds–Karp algorithm
  • max-flow min-cut theorem
• matching problem, assignment problem

Resources:

• play with interactive visualizations: shortest path, max flow, matching

Graph Project:

• implement an algorithm to find a shortest path or maximum flow on your graph data set
• annotate functions with complexity analysis

Class 16: Wednesday, March 1 – Optimization & Memoization

Topics:

• combinatorial optimization, greedy algorithms
• revisit recursion with memoization

Challenges:

• implement the following with plain recursion and with memoization using starter code and unit tests:
  • factorial function
  • fibonacci function
  • change-making problem – solve HackerRank's coin change problem
  • stretch: permutation function
  • stretch: combination function
• annotate functions with complexity analysis
• benchmark performance of plain recursion and memoized recursion
• stretch: implement @memoized decorator to memoize any recursive function

Resources:

• play with interactive visualizations: recursion and memoization
• read about greedy algorithms on WikiBooks

Class 17: Friday, March 3 – Dynamic Programming

Topics:

• revisit recursion with dynamic programming

Challenges:

• implement the following with dynamic programming using starter code and unit tests:
  • factorial function
  • fibonacci function
  • change-making problem – solve HackerRank's coin change problem
  • stretch: permutation function
  • stretch: combination function
• annotate functions with complexity analysis

Resources:

• play with interactive visualizations: recursion and dynamic programming
• read about dynamic programming on WikiBooks

Working with this GitHub repository

This repository (located at https://github.com/MakeSchool-18/Data-Structures) is the course's origin repository which will contain course materials including links, slides, and challenges. Note that you cannot commit or push to the origin repository. However, you can fork it to maintain your own version of it and push your code there. Here's an overview of what your repository setup should look like:

Follow these steps to set up your own course repository:

1. Clone this repository on your computer: git clone [email protected]:MakeSchool-18/Data-Structures.git

2. Fork this repository on GitHub to create your own version of this repo on your GitHub account, which should also be named Data-Structures

3. Add your GitHub repository as a remote to the local one on your computer (note: you need to give a name to the remote, e.g. your first name): git remote add <first-name> [email protected]:<github-user>/Data-Structures.git

4. Link the local repo to your remote GitHub repo: git push -u <first-name> master

5. When you want to access new course materials, just pull from the origin remote repo: git pull origin master

6. When you've completed a challenge and want to share it for code review, commit your work and push it to your own remote repo with: git push