Schedule

Outlined below is the schedule for the course, including lecture topics and assignment due dates. All assignments are due at 11:59PM on the date specified. The specific dates of different topics are subject to change based on the pace at which we go through the course.

The assigned textbook for the course covers most of the topics we will go over in the class, but I will sometimes add external links to other resources if I feel the textbook is lacking in a particular area, or if there is a fun application for you to play with beyond what's offered in the textbook.



Lecture
Date
Lectures (click for notes)Readings/LinksAssignments/Deliverables

Intro To Python, Abstract Data Types, And Empirical Complexity

In this unit we will warm up to algorithms and data structures by learning the basics of Python, which is a language whose syntax is only a short step away from pseuodocode one might write to describe algorithms and data structures. In the process of learning python syntax, we will introduce the notion of an Abstract Data Type (ADT), which is akin to an interface in Java or a header file in C++. In other words, an ADT is an API for a data structure, which makes it usable to an algorithm. But the implementation of the data structure is left unspecified. In this unit, we will actually jump to the end of the book to look at our first ADT, the Disjoint Set ADT, and we will examine an efficient implementation known as Union Find. The unit will culuminate in an application of disjoint sets to finding individual cells in images of plant cells.

1Wed 1/20/2021Course Sneak Preview / Meet & MinglePre-Class Module 0 Due
2Fri 1/22/2021Python/numpy basicsModule 1: Python Basics Due Before Class
3Mon 1/25/2021Python Classes And Objects, Abstract Data TypesModule 2: Numpy, Matplotlib, Python Classes Due Before class
4Wed 1/27/2021Disjoint Sets And Union FindModule 3: Disjoint Set Data Structures Due Before class
5Fri 1/29/2021Unit Tests And TimeItAssignment 1: Plant Cell Segmentation out

Searching And Analytical Complexity Analysis

We have a bunch of objects, and we want to find them quickly. Operations: Find, Add/Remove First, Add/Remove Last, Add/Remove Middle

6Mon 2/1/2021Big-O, Little-o, Big-ThetaModule 4: Analytical Time Complexity And Big O Due before class
7Wed 2/3/2021Linked Lists / Doubly-linked listsModule 5: Little-o And Python Linked Lists Due before class
8Fri 2/5/2021The list ADT and Data StructureModule 6: The List Data Structure And Amortized Cost Due Before Class
9Mon 2/8/2021Sorted List Data Structure And Binary SearchModule 7: Amortized Cost Proof, Binary Search Due Before Class
Tue 2/9/2021Assignment 1: Plant Cell Segmentation Due
10Wed 2/10/2021Hash Tables AlgorithmModule 8: Binary Search Implementation, Sets/Maps Due Before Class
11Fri 2/12/2021Hash Tables Analysis / Applications
Sun 2/14/2021Assignment 2: Complexity Proofs / Autocomplete Out

Recursion And Dynamic Programming

12Mon 2/15/2021Recursive function review, evaluating recursive functions
13Wed 2/17/2021Memoization, Recursive Drawing
14Fri 2/19/2021Stacks, Queues, And Towers of HanoiModule 9: Sierpinski Triangle, Stacks/Queues Review, Towers of Hanoi due before class
15Mon 2/22/2021Proofs by Induction, Dynamic Programming, String Edit DistanceModule 10: Proofs by Induction, Memoization, String Edit Distance due before class
16Wed 2/24/2021Optimal Solution Backtracking, Change Making
Thu 2/25/2021Assignment 2 Due
17Fri 2/26/2021Seam CarvingModule 11: String Edit Distance Backtracing Solutions, Making Change Due
18Mon 3/1/2021Seam Carving Q&AModule 12: Seam Carving Due before class
--Wed 3/3/2021Break DayNo CS 371 Class. Enjoy the break!
19Fri 3/5/2021Dynamic Time WarpingAssignment 3: Audio Alignment Out
20Mon 3/8/2021Longest Common Subsequence, Knapsack Problem

Sorting, Selection, And Shuffling

21Wed 3/10/2021Insertion Sort, Bubble Sort, Kendall Tau DistanceModule 13: Longest Common Subsequence Due before class
22Fri 3/12/2021Merge Sort
23Mon 3/15/2021Quick Sort, Stability of SortsModule 14: Intro To Sorting Due Before Class
24Wed 3/17/2021Parallel Algorithms And Bitonic Sort
25Fri 3/19/2021Radix Sort: Breaking the O(NlogN) barrierModule 15: Recursive Sorts And Sorting Theory Due Before Class
26Mon 3/22/2021Fisher-Yates ShufflingAssignment 3: Audio Alignment Due
27Wed 3/24/2021Erin Taylor Q&A, Linear Time SelectionModule 16: Radix Sort, Fisher-Yates Shuffling due before class

Tree Data Structures And Algorithms

28Fri 3/26/2021Binary Trees: Preorder, Inorder, Postorder / Drawing Binary TreesModule 17: Intro To Binary Trees, Preorder/Inorder/Postorder due before class
Assignment 4: Fair Elections of Superheros 0ut
29Mon 3/29/2021Binary search trees: Search/Addition/RemovalFinal Project Proposals Due
--Wed 3/31/2021Break DayNo CS 371 Class. Enjoy the break!
30Fri 4/2/2021Tree RotationsModule 18: Binary Search Trees: Contains/Addition/Removal due before class
31Mon 4/5/2021Balanced Binary Search Trees
Tue 4/6/2021Assignment 4 Due
32Wed 4/7/2021Q&A Session, Tree Rotations Review
33Fri 4/9/2021Huffman Trees / Huffman Encoding
34Mon 4/12/2021Priority Queues / Binary Heaps
Tue 4/13/2021Assignment 5: Phylogenetic Trees Out
35Wed 4/14/2021Tries

Graph Data Structures And Algorithms

36Fri 4/16/2021Graph Data Structures, Minimum Spanning TreesModule : Huffman Trees due
37Mon 4/19/2021Complexity of Minimium Spanning Trees, Automatic MazesModule 21: Minimum Spanning Trees due before class
38Wed 4/21/2021Breadth-First Search, Depth-First Search, Euclidean Traveling Salesperson
39Fri 4/23/2021Dijkstra's Algorithm, Prim's AlgorithmFinal Project Check-In
40Mon 4/26/2021Complexity of Dijkstra's Algorithm, Fibonacci HeapsModule 20: Heaps And Dijkstra's due before class
41Wed 4/28/2021Floyd-Warshall, Bellman-FordAssignment 5 Due
--Fri 4/30/2021Designated Tuesday ClassNo CS 371 Class
42Mon 5/3/2021Directed Acyclic Graphs / Topological SortAssignment 6: Rush Hour Out
--Fri 5/7/2021 - Thu 5/13/2021Coding Interviews
--Thu 5/13/2021Final Project Due
Assignment 6: Rush Hour Due