CS 577 - Intro to Algorithms

Overview

CS 577 was a great course about the algorithmic part of computer science. I learned topics such as Big Oh Notation, Greedy algos, Divide & Conquer algos, Dynamic Programming, Network Flow and Intractibility. The class focused on proving algorithm correctness and runtimes to ensure that the most efficient algorithms are used. I learned how to prove the different algorithms mentioned and the general outline of each.

Topics

Greedy Algos

These algos always take the best possible option at the current time without considering future consequences. Usually good for maximization or minimization problems.

Divide and Conquer

DC algos are special for breaking the problem into smaller parts and solving those, then combining the problem back together. Examples are mergesort and quicksort.

Dynamic Programming

DP utilizes memoization to remember previous solutions. This way the program does not have to repeat solving for something many times and instead can call upon a memoized value to solve.

Network Flow

Sometimes it is easier to visualize problems through a graph. With NF you can find the max flow, min cut and do reductions.

Intractibility

Deals with the problems that we don't know if they can be solved in polynomial time or not. Proving something is NP-Complete requires proving that it is in NP and that it is NP-Hard.