Learning assessments, outcomes, and such
These Learning outcomes were formed by Nicole Eikmeier, Peter-Michael Osera, and Anya Vostinar with the help of Vanessa Preast in Spring-Summer 2020. They were adapted and edited by Samuel A. Rebelsky in Summer 2021.
List of topics
a. Program/Algorithm correctness/verification by construction
b. Loop Invariants
c. Formal proof of asymptotic classes: Little oh, big Omega, Big Theta
d. Solving recurrence relations
e. Using the Master Theorem
f. Comparison Based Sorts are lower bounded by nlog(n)
g. Bucket Sort & Radix Sort
h. Topological Sort
i. Algorithm Design Strategies:
* Exhaustive Search
* Divide & Conquer
* Greedy Algorithms
* Dynamic Programming
j. Network flow
k. Bipartite graphs/matching
l. Tries
m. Union find/Disjoint sets
n. Something from the primary literature
o. Balanced trees
Learning outcomes
- Given a problem statement, students can write/develop a loop invariant alongside an algorithm, and can prove the correctness of their algorithm via a loop-invariant technique.
- Students can recite the formal definition of Big-Oh, little-oh, Big-Omega and Big-Theta, and formally prove properties of these classes.
- Students can prove asymptotic bounds on iterative algorithms with non-trivial nesting.
- Students can explain why comparison-based sorts take order nlogn in the worst case.
- Students can reproduce Radix, Bucket, and Topological Sorts, and explain the context in which these sorting algorithms are useful.
- Given an algorithm which uses Divide-and-Conquer, students can develop a recurrence relation for that algorithm.
- Given a recurrence relation, students can solve the relation using the Master Theorem and other techniques.
- Students can consider different algorithmic design strategies when solving problems.
- Students can solve problems using each of divide and conquer, greedy, and dynamic techniques.
- Students can adapt network flow algorithms to solve appropriate network problems.
- Students can implement an advanced data structure or algorithm, demonstrating good software design practices including documentation and testing.
- Students can explain the tradeoffs between different data structures when they are used for similar problems.
- Students can implement a balanced tree.
- Students can read and understand a primary source from the literature of algorithms.
- Students can explain how structural racism or other unexpected consequences can manifest in algorithm design.
Types of writing
This course employs a variety of genres of writing typically used in the discipline. In particular, students will write,
- Proofs in mathematical English.
- Program code in a variety of languages (including Scheme, C, and Java)
- Documentation that explains the goals and expectations of functions, data structures, and compositions of functions and data structures, such as in objects/classes or full programs.
- Unit tests that help verify the correctness of code.
- Claim-based essays in English.