ESO207A - Data Structure & Algorithm

Order Analysis: Objectives of time analysis of algorithms; Bigoh and Theta notations, Data Structures: Arrays, Linked lists, Stacks (example: expression evaluation), Binary search trees, Red Black trees, Hash tables, Sorting and Divide and Conquer Strategy: Merge sort; DandC with Matrix Multiplication as another example, Quick sort with average case analysis, Heaps and heap sort, Lower bound on comparison based sorting and Counting sort, Radix sort, Btrees, Dynamic Programming: methodology and examples (Fibonacci numbers, matrix sequence, multiplication, longest common subsequence, convex polygon triangulation), Greedy Method: Methodology, examples (lecture scheduling, process scheduling) and comparison with DP (more examples to come later in graph algorithms), Graph Algorithms: Basics of graphs and their representations, BFS, DFS, Topological sorting, Minimum spanning trees (Kruskal and Prims algorithms and brief discussions of disjoint set and Fibonacci heap data structures), Shortest Paths (Dijkstra, Bellman Ford, Floyd Warshall).