This repository contains some of the problem assignments from the Advanced Algorithms and Complexity Course from the University of San Diego.

• Flows in Networks:
  • Evacuation: Applying an algorithm for finding maximum flow in a network to determine how fast people can be evacuated from the given city.
  • Airline Crew: Applying an algorithm for finding maximum matching in a bipartite graph to assign airline crews to flights in the most efficient way.
  • Stock Charts: Applying a flow algorithm approach to find the minimum Path Cover in a DAG to compute the maximum number of stock charts that do not intersect.
• Linear Programming:
  • Energy values: Applying Gaussian elimination to solve a problem where we have to tell the amount of nutrients that each ingredient has.
  • Diet: Applying Gaussian elimination to perform a brute force linear programming approach
• NP-Completeness:
  • GSM Network: encoding to SAT the 3-coloring problem to determine if we can make a GSM network work
  • Cleaning the apartment: encoding to SAT the Hamiltonian Path problem to find a a clever way to clean your apartment
• Coping with NP-completeness:
  • Integrated Circuit Design: solving 2-SAT by constructing a directed implications graph and looking for different strongly connected components to design part of an integrated circuit
  • Plan a Fun Party: computing maximum independent set of a tree to plan a fun party
• Streaming Algorithms:
  • Nice vs Naughty: implementing the count sketch algorithm to determine if a kid was nice or naughty to help Santa Claus.

Certificate: