Skip to content
CS Exit Ethiopia
Revision outline6 / 100 blueprint items

Design and Analysis of Algorithms

45 topics · 957 revision cues · 141 practice questions

0 / 45 topics reviewed
45 / 45 topics shown · Progress saved in this browser.
Revision approach
  • Algorithm design obligations
    • States and choices
    • Correctness argument
    • Work and peak storage
    • Independent subproblems
    • Subproblem reuse
    • Safe local choices
    • Feasibility pruning
    • Objective bounds
    • Strategy name alone insufficient
    👁 Full explanation
    Design an algorithm by specifying its states, choices and correctness argument, then count its work and peak storage. A familiar strategy name is not enough: independent subproblems, reuse, safe local choices, feasibility pruning and objective bounds lead to different methods.
  • Fix the cost model
    • Input size and input case
    • Primitive operation
    • Arithmetic model
    • Sum/recurrence before asymptotic choice
    👁 Full explanation
    For cost questions fix input size, case, primitive operation and arithmetic model. Write the sum or recurrence before selecting an asymptotic bound.
  • Design-technique practice
    • Small execution traces
    • Discarded alternatives: no better required answer
    • Justify elimination
    👁 Full explanation
    For each design technique practice a small trace and explain why its discarded alternatives cannot improve the required answer.
  • Essential analysis distinctions
    • Exact algorithm versus heuristic
    • Decision versus optimization
    • Tight bound versus valid upper bound
    👁 Full explanation
    Distinguish an exact algorithm from a heuristic, a decision problem from an optimization problem, and a tight bound from a merely valid upper bound.
Blueprint learning outcomes
  • DAA1 · Perform algorithm analysis using the different techniques
    DAA01, DAA02, DAA03, DAA04, DAA05, DAA06, DAA07, DAA08, DAA09, DAA10, DAA11, DAA13, DAA14, DAA29
  • DAA2 · Demonstrate the use of algorithm design techniques
    DAA12, DAA13, DAA14, DAA15, DAA17, DAA18, DAA19, DAA20, DAA21, DAA22, DAA23, DAA24, DAA25, DAA26, DAA27, DAA28, DAA29, DAA30, DAA31, DAA32, DAA33, DAA36, DAA37, DAA38, DAA39, DAA40, DAA41, DAA42, DAA43
  • DAA3 · Describe the basics of computational complexity
    DAA02, DAA03, DAA04, DAA05, DAA08, DAA11, DAA29, DAA33, DAA44