COSE214_Algorithms

Assignment source codes for Korea University COSE214 Algorithms (Prof. Soon-Yeong Jeong)

• Assignment 1 : Maximum Subarray Problem
• Assignment 3 : Heap Sort
• Assignment 4 : Huffman Coding
• Assignment 5 : Dijkstra's Algorithm

In this course, I learned...

• Definition of the algorithm
• Basic sorting algorithm : Insertion Sort
• Asymptotic notation of an algorithm
• Divide & Conquer Designing : Merge Sort, Maximum Subarray Problem
• Probabilitic Analysis of algorithm and Randomized Algorithm : Hiring Problem
• Binary Heap and Priority Queue : Heap Sort
• Quick Sort, Randomized Quick Sort
• Hash Table and its analysis
• DP (Dynamic Programming) : Rod-Cutting Problem, MCM (Matrix Chain Multiplication) Problem
• Greedy method : Activity-Selection Problem, 0-1/Binary Knapsack Problem, Huffman Coding
• MST (Minimum Spanning Tree) : Kruskal's Algorithm and Disjoint Sets, Prim's Algorithm
• Single-Source Shortest Paths : Dijkstra's Algorithm, Bellman-Ford Algorithm
• All Pair Shortest Paths : DP-based brute-force algorithm and Floyd-Warshall Algorithm
• Basic Concepts of P-NP and NP-completeness : How to prove the NP-Completeness of the problem?
• Approximation Algorithms for some NPC problems : Vertex-cover problem, TSP(Traveling Salesman Problem), Set-covering Problem, Subset-sum problem