Algorithm Analysis Review for Final Exam: Topics Covered, Study Tips, and More
Prepare for your algorithm analysis final exam with this comprehensive review covering topics like graph algorithms, dynamic programming, sorting algorithms, and more. Get study tips and information on the exam coverage to help you succeed.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CS 3343: Analysis of Algorithms Review for final 4/13/2025 1
Final Exam Closed book exam Coverage: the whole semester Cheat sheet: you are allowed one letter- size sheet, both sides May 4 (sec 1) and 7(sec 2), 12:30 3:00pm Basic calculator (no graphing) allowed No cell phones! 4/13/2025 2
Final Exam: Study Tips Study tips: Study each lecture Study the homework and homework solutions Study the midterm exams Re-make your previous cheat sheets 4/13/2025 3
Topics covered (1) By reversed chronological order: Other topics Graph search & topological sort String matching P & NP Graph algorithms Representations MST (Prim s, Kruskal s) Shortest path (Dijkstra s) Running time analysis with different implementations Greedy algorithm Uniform-profit restaurant location problem Fractional knapsack problem How to show that certain greedy choices are optimal Color key: Red: Absolutely need to know Blue: Ideally, you should know Grey: Possible extra credit question 4/13/2025 4
Topics covered (2) Dynamic programming LCS Restaurant location problem Shortest path problem on a grid Other problems Knapsack, event scheduling, coin changing, etc. How to define recurrence solution, and use dynamic programming to solve it Binary heap and priority queue Heapify, buildheap, insert, exatractMax, changeKey Running time and analysis 4/13/2025 5
Topics covered (3) Order statistics Rand-Select Worst-case Linear-time selection Running time Running time analysis using substitution method Expected running time analysis of probabilistic algorithm Sorting algorithms Insertion sort Merge sort Quick sort Heap sort Linear time sorting: counting sort, radix sort Stability of sorting algorithms Worst-case and expected running time Memory requirement of sorting algorithms Running time analysis of quick sort using substitution method 4/13/2025 6
Topics covered (4) Analysis Compare order of growth Prove asymptotic notation using basic definition Worst case and average case analysis Analyzing non-recursive algorithms Sum of arithmetic series Sum of geometric series Analyzing recursive algorithms Defining recurrence Solving recurrence Master theorem Recursion tree (iteration) method Substitution method 4/13/2025 7
