**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.

Topic | Suggested Reading |

Introductions | |

Proofs Review | Proofs++ |

Asymptotics | Chapter 3 – Characterizing Running Times |

Recursion | |

Divide and Conquer | Chapter 4 – Divide and Conquer |

Loop Invariants | Section 2.1 |

Basic Sorting | Chapter 8 |

Quick Sort | Chapter 7 |

Merge Sort | |

Sorting Limitations | Information Theoretic Approach |

Graphs | Chapter 20 |

Trees | Various Chapters, but 10 is a good place to start |

Reachability | |

Basic Searches | |

Topological Sort | |

Prim’s Algorithm | Chapter 21 |

Kruskal’s Algorithm | |

Dijkstra’s Algorithm | Section 22.3 |

Bellman-Ford | Section 22.1 |

Floyd-Warshall | Section 23.2 |

Dynamic Programming | Chapter 14 Chapter 15 |

Scheduling Problem | Section 15.1 |

Rod Cutting | Section 14.1 |

Edit Distance | Partially Section 14.4 |

Knapsack Problem | |

Subset Sum | |

Partition | |

Amortized Time | Chapter 16 |

Network Flows | Chapter 24 |

Linear Programming | Chapter 29 |

Compression | |

NP Completeness | Chapter 34 |

Approximation Algorithms | Chapter 35 |

Probabilistic Algorithms |

## Learning Outcomes

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

- Use the formal definitions of Big-O, little-o, Big-Omega, little-omega, and Big-Theta to

prove properties of these classes. - Write/develop a loop invariant alongside an iterative algorithm.
- Create an analogous recursive requirement for recursive algorithms.
- Prove the correctness of an algorithm.
- Solve problems using Divide & Conquer.
- Develop a recurrence relation, given an algorithm which uses Divide & Conquer.
- Solve a given recurrence relation using the work tree method.
- Implement a variety of sorting algorithms including MergeSort and QuickSort.
- Implement several famous graph algorithms such as DFS, BFS, and Bellman-Ford.
- Solve problems using dynamic programming strategies.
- Solve problems using a specialized greedy strategy.
- Implement algorithms for finding a Minimum Spanning Tree in a graph.
- Solve problems using Network Flows.
- Analyze the amortized runtimes of operations for specified data structures.
- Recognize famous NP-Complete problems like SAT, knapsack, vertex cover, etc.
- Reduce an NP-Complete problem to a specified problem.
- Justify algorithmic design choices made when solving problems.
- Implement an advanced data structure or algorithm, demonstrating good software design

practices including documentation and testing.