The word algorithm is derived from the name of the Persian mathematician Mohammed al-Khowarizmi, who lived during the 9th century, and who is credited with providing thestep-by-step rules for adding, subtracting, multiplying, anddividing ordinary decimal numbers. When written in Latin, thename became Algorismus, from which algorithm is but a small step.
Science is what we understand well enough to explain to a computer; art is everything else. — Donald Ervin Knuth
Simple definition: A step-by-step procedure to accomplish a specific (computational) problem.
In this course we touch the surface of this field of science by introducing some famous strategies to solve problems. The main strategies that we cover are
(16,18/11)
Introduction
Algorithm Description, Correctness Analysis
(23,25/11)
Complexity Analysis
Orders of Growth
(30/11,2/12)
Steps of D&C, Finding the peak, The maxima set
Master Theorem, Maximum Subarray
(7,9/12)
Finding the closest pair, Merge sort
Quick sort, Miscellaneous on sorting
(14,16/12)
Steps of DP, Coin-row
Coin change, Coin collection
(21,23/12)
Memoization, Knapsack
Matrix chain mul.,
Optimum Binary Search Tree (BST)
(20,22/1)
Shortest path
Traveling Sale Person (TSP)
(27,29/1)
Steps of Greedy, Activity selection
Change making, Fractional knapsack
(3,5/2)
Minimum Spanning Tree (MST)
Shortest path (Dijkstra), Huffman code
Stable Matching
Definition of P/NP/NPC, Cook's Theorem
Midterm
Reductionm
Approximation Algorithms, TSP
(24,26/2)
Vector Cover, Set Cover
Backtrack, N-Queens
(31/2, 2/3)
Subset sum, Graph Coloring, Hamiltonian Circuit
Integer Linear Programming
Quiz3
For each homework, late submission (before TA sessions) is accepted but with a penalty of 5% per day.
However, you need to solve many problems, and many good books are availbale to *challenge yourself* with their examples and problems