50.500 Analysis of Algorithms

Course DescriptionThis course will cover the techniques for algorithm analysis, with examples from various sorting and search algorithms. Then the course will introduce advanced design and analysis techniques including dynamic programming, greedy algorithms, amortized analysis, B-trees and Fibonacci Heaps. Finally, some graph algorithms such as minimum spanning trees, shortest path algorithms will be discussed.The course will be based on instructors-lead lectures, student-lead discussions, quizzes in the form of mock technical interviews, midterm and final exam.Learning ObjectivesBy the end of the course, students will be able to: Perform rigorous program/algorithm analysis Understand and able to apply advanced data structure such as hash tables, red-black tree, skip list Understand and able to apply advanced algorithm design techniques such as divide and conquer, dynamic programing and greedy algorithms Understand and able to apply algorithms for trees and graphs such as minimal spanning tree, shortest-path algorithm, maximum flow. Measurable Outcomes Able to perform big 0 analysis for a given algorithm design Able to use data structures such as hash table, skip list, red-black tree, B-tree, augmented data structures Able to design algorithms with divide and conquer, dynamic programming, greedy algorithm and analyze their complexities. Able to process and design solutions related to graphs and use the standard algorithms such as minimal spanning tree and shortest path. 12 Credits ComponentsWeekly quizzes, midterm and final exam Image Credit