DAA
Design and Analysis of Algorithms
Design and Analysis of Algorithms
This course presents fundamental techniques for designing efficient computer algorithms and analyzing their running times. Topics include asymptotics, solving summations and recurrences, sorting and selection, graph algorithms (depth-first and breadth-first search, minimum spanning trees, and shortest paths), algorithm design techniques (divide-and-conquer, dynamic programming, and greedy algorithms), and an introduction to NP-completeness.
Textbook(s): Introduction to Algorithms, 4rd ed., 2022, by T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. MIT Press, ISBN-13: 978-0262046305. Not required, but a classic: The Design and Analysis of Computer Algorithms, by A.V. Aho, J.E. Hopcroft, J.D. Ullman.
Learning objectives (from MIT 6.046J/18.401J): This course introduces students to the analysis and design of computer algorithms. Upon completion of this course, students will be able to do the following:
Analyze the asymptotic performance of algorithms.
Demonstrate a familiarity with major algorithms and data structures.
Apply important algorithmic design paradigms and methods of analysis.
Synthesize efficient algorithms in common engineering design situations.
Learning outcomes (based on MIT 6.046J/18.401J): Students who complete the course will have demonstrated the ability to do the following:
Argue the correctness of algorithms using inductive proofs and loop invariants.
Analyze worst-case running times of algorithms using asymptotic analysis.
Analyze average-case running times of algorithms whose running time is probabilistic.
Explain the basic properties of randomized algorithms and methods for analyzing them.
Analyze algorithms using amortized analysis, when appropriate.
Describe the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it.
Describe the dynamic-programming paradigm and explain when an algorithmic design situation calls for it.
Describe the greedy paradigm and explain when an algorithmic design situation calls for it.
Explain the major algorithms for sorting.
Explain the major elementary data structures for implementing dynamic sets and the analyses of operations performed on them.
Explain the major graph algorithms and their analyses.
Demonstrate a familiarity with applied algorithmic settings by reciting several algorithms of importance to different fields.
Prerequisite: A course in Data Structures, or permission of instructor.
Major topics/schedule
intro, first sorts
asymptotic analysis, C++ sans objects, mergesort
growth, recurrences, Strassen
recurrences cont'd. (induction, recurrence/recursion tree, Master method)
randomized
TSP
selection problem; quicksort
counting sort, radix sort
greedy (interval scheduling, fractional knapsack
greedy cont'd. (Huffman coding)
dynamic programming (DP), longest common subsequence
DP cont'd. (matrix chain multiplication)
DP cont'd. (0-1 knapsack)
elementary graph (BFS, DFS, topological sort)
DFS application (articulation points)
MSTs, Kruskal's, Prim's
shortest paths (including Dijkstra's)
all-pairs shortest paths, Floyd-Warshall
NP-completeness
Fourier transform & FFT
Software: C/C++ (on any platform of your choosing). (Testing will occur on a platform of my choosing.) You are required to use the following code formatting standard: Google C++ Style Guide. https://google.github.io/styleguide/cppguide.html#Formatting. Points will be subtracted for improper formatting and/or lack of comments. Note that they actually provide a program to check the formatting of C/C++ code.
second sorts (asymptotic analysis)
C++ sans objects (MS Visual Studio C++ guide; Clion C++ guide )
DNC part a recurrences
DNC part b Strassen
DNC part c induction, recurrence/recursion tree, Master method
sorting in linear time (counting and radix sorts)
Huffman codes (example of greedy)