8 Learners
The analysis of algorithms is the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm.
Course Outline
17mExample: Air Travel
9mExample: Xerox shop
6mExample: Document similarity
9mIntroduction and motivation
18mInput size, worst case, average case
10mQuantifying efficiency: O( ), Omega( ), Theta( )
18mExamples: Analysis of iterative and recursive algorithms
17mInsertion sort
13mSelection Sort
13mSearching in an array
13mArrays and lists
13mSorting - Concluding remarks
8mQuicksort - analysis
8mQuicksort
8mMerge sort - analysis
8mMerge sort
8mRepresenting graphs
13mIntroduction to graphs
13mDirected acylic graphs: longest paths
14mDirected acylic graphs: topological sort
14mApplications of BFS and DFS
14mDepth first search (DFS)
14mBreadth first search (BFS)
14mKruskals algorithm
14mPrims Algorithm
14mMinimum Cost Spanning Trees
14mAll pairs shortest paths
14mNegative edge weights: Bellman-Ford algorithm
14mDijkstras algorithm: analysis
14mSingle source shortest paths: Dijkstras algorithm
14mClosest pair of points
16mCounting inversions
16mHeaps: Updating values, sorting
16mHeaps
16mPriority queues
16mUnion-Find using pointers
16mUnion-Find using arrays
16mHuffman codes
29mScheduling with deadlines: minimizing lateness
29mInterval scheduling
29mBalanced search trees
29mBinary Search Trees
29mMatrix multiplication
15mEdit distance
15mCommon subwords and subsequences
15mGrid Paths
15mMemoization
15mIntroduction to dynamic programming
15mP and NP
20mChecking Algorithms
20mReductions
20mNetwork Flows
20mLP modelling: Bandwidth allocation
20mLP modelling: Production Planning
20mLinear Programming
20m