This repository contains all the (home)works done in the "Computer Algorithms" course offered at National Taiwan Normal University (NTNU) by Professor Mei-Chen Yeh (葉梅珍教授) in Spring 2020. Each piece of homework consists of a handwritten problem set which usually includes three problems (sometimes two), and two programming problems, pA and pB.
We used Cormen's Introduction to Algorithms (3rd ed.) as the principal learning material. We went through the following contents:
- Asymptotic notation; Recurrences
- Randomized algorithms; Divide-and-Conquer
- Sorting: Heapsort, quicksort, linear sorting
- Hashing and binary search
- Dynamic programming
- Greedy algorithms
- Graph algorithms
- Shortest paths
- Maximum flow
- NP-completeness
- Approximate algorithms
The following section describes each homework's main topic and provides the link to the corresponding homework set (in PDF).
- Homework 1: Asymptotic notation, complexity analysis, master theorem, recurrences (handwritten: Fibonacci, pA), divide-and-conquer (pA), two pointers (pB).
- Homework 2: Sorting: quicksort (handwritten), bubblesort properties (handwritten, pA), mergesort(pB).
- Homework 3: Dynamic Programming: knapsack problem (handwritten), games of stone (handwritten, pA), longest subsequence (pB), 2-dimensional dynamic programming (handwritten: bento, watermelon)
- Homework 4: Greedy Method (handwritten: square, lexicographical order, arithmetic, pA, pB), Graph: BFS, DFS (pA)
- Homework 5: Graph: maximum-spanning-tree (MST) (handwritten: turnip, pA), directed-acyclic-graph (DAG) (handwritten: lexicographical order), strongly-connected-component (SCC) (handwritten), flood-fill (pB)
- Homework 6: Graph: shortest-path algorithms (handwritten): Bellman-Ford, Dijkstra (pB), Floyd-Warshall (pA), Prim's
- Homework 7: Graph: Maximum flow: Ford-Fulkerson-Method