CSC 301 – Fall 2023

Instructor
Dawn Nye

Office Hours
MWF 11:50 – 12:50 and 1:50 – 2:50
Noyce 2811 or Noyce 3820 (to be determined by observation)

Mentor
Section 1: Anil Alper
Section 2: Michael O’Connor

Mentor Sessions
Section 1: to be determined
Section 2: to be determined

Meeting Times
Section 1: MWF 11:00-11:50 am at Noyce 3820
Section 2: MWF 1:00-1:50 pm at Noyce 3820

Textbook
Introduction to Algorithms 4th Edition (CLRS)

Everything is an algorithm. Want to stand upright? That requires a complex feedback loop to maintain balance. Want to find your way to the grocery store? That requires a path finding algorithm. Want to determine the best sets of clothes to pack into a suitcase? It turns out that problem is intractable, so you might as well just go with whatever feels good enough.

The study of algorithms is as important for determining how to calculate something as it is for determining how long calculating something will take. Indeed, some problems are outright impossible and can at best be approximated. Some problems will admit multiple solutions where no one answer is ‘best’. In these cases, a judgement call will need to be made in each situation as to which to use.

Where previous courses have familiarized you with how to write an algorithm, we will focus on how to break problems down into their base components and use algorithms to solve them. More than that, we will also focus on how to prove that our solutions are correct. However, a correct solution is not necessarily a good solution, so it will also become important to analyze their costs in time, space, or some more exotic resource requirement.


Order of Topics and Readings

Below are the (immediately) upcoming and previous topics we will cover in class. More will be added as the semester advances.

TopicSuggested Reading
Introductions
Proofs ReviewProofs++
AsymptoticsChapter 3 – Characterizing Running Times
Recursion
Divide and ConquerChapter 4 – Divide and Conquer
Loop InvariantsSection 2.1
Basic SortingChapter 8
Quick SortChapter 7
Merge Sort
Sorting LimitationsInformation Theoretic Approach
GraphsChapter 20
TreesVarious Chapters, but 10 is a good place to start
Reachability
Basic Searches
Topological Sort
Prim’s AlgorithmChapter 21
Kruskal’s Algorithm
Dijkstra’s AlgorithmSection 22.3
Bellman-FordSection 22.1
Floyd-WarshallSection 23.2
Dynamic ProgrammingChapter 14
Chapter 15
Scheduling ProblemSection 15.1
Rod CuttingSection 14.1
Edit DistancePartially Section 14.4
Knapsack Problem
Subset Sum
Partition
Amortized TimeChapter 16
Network FlowsChapter 24
Linear ProgrammingChapter 29
Compression
NP CompletenessChapter 34
Approximation AlgorithmsChapter 35
Probabilistic Algorithms

Learning Outcomes

Upon completion of the course, students will be able to:

  1. Use the formal definitions of Big-O, little-o, Big-Omega, little-omega, and Big-Theta to
    prove properties of these classes.
  2. Write/develop a loop invariant alongside an iterative algorithm.
  3. Create an analogous recursive requirement for recursive algorithms.
  4. Prove the correctness of an algorithm.
  5. Solve problems using Divide & Conquer.
  6. Develop a recurrence relation, given an algorithm which uses Divide & Conquer.
  7. Solve a given recurrence relation using the work tree method.
  8. Implement a variety of sorting algorithms including MergeSort and QuickSort.
  9. Implement several famous graph algorithms such as DFS, BFS, and Bellman-Ford.
  10. Solve problems using dynamic programming strategies.
  11. Solve problems using a specialized greedy strategy.
  12. Implement algorithms for finding a Minimum Spanning Tree in a graph.
  13. Solve problems using Network Flows.
  14. Analyze the amortized runtimes of operations for specified data structures.
  15. Recognize famous NP-Complete problems like SAT, knapsack, vertex cover, etc.
  16. Reduce an NP-Complete problem to a specified problem.
  17. Justify algorithmic design choices made when solving problems.
  18. Implement an advanced data structure or algorithm, demonstrating good software design
    practices including documentation and testing.