This repository serves as a collection of homework assigned in CS411 Analysis of Algorithms at the University of Alaska Fairbanks.
- HW1 focuses on time complexity and algorithm recurrences.
- HW2 uses a brute force algorithm to find the maximum toll vector of bridges can achieve by connecting east cities to west cities without any cities sharing more than one bridge or any bridge crossing another.
- HW3 consists of two seperate algorithms.
- The greatest contiguous sum (GCS) algorithm uses a Divide-and-Conquer strategy to find a contiguous subsequence in a list with greatest sum.
- The inversions algorithm also uses a Divide-and-Conquer strategy in conjunction with Merge Sort. The algorithm returns the number of inversions in a list. An inversion being the number of items that an item x has skipped over when being moved to a different place in the sequence.
- HW4 describes solutions to several different problems and algorithms from the book Introduction to The Design and Analysis of Algorithms by Anany Levitin.
- HW5 revisits the bridges problem from HW2, but instead of using a Brute Force algorithm, it uses Dynamic Programming to find the solution. Specifically top down (memoization).
- HW6 uses Huffman Coding to encode a string of letters into 1's and 0's as well as taking a string of 1's and 0's and decoding it to it's corresponding letters.
- HW7 is a modified implementation of Dijkstra's algorithm. Rather than calculating the single source shortest path, the function takes a source and a destination and calculates the shortest path between them.