Scribd
Upload
17 views2 pages

Key Algorithm Concepts Explained

The document discusses several common algorithm concepts: 1. Greedy algorithms make locally optimal choices at each step in the hopes of finding a global optimum. Examples include making change with bills and shortest path algorithms. 2. Divide and conquer algorithms break problems into smaller subproblems, solve the subproblems recursively, and combine the solutions. Examples are sorting and tree traversal. 3. Dynamic programming improves on naive recursive solutions by storing results of subproblems to avoid recomputing them. Examples include matrix chain multiplication and longest common subsequence. 4. Backtracking algorithms use pruning to iteratively eliminate invalid partial solutions and find all valid ones, such as reconstructing a point set from distances.

Uploaded by

Ahmad Alhour
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views2 pages

Key Algorithm Concepts Explained

The document discusses several common algorithm concepts: 1. Greedy algorithms make locally optimal choices at each step in the hopes of finding a global optimum. Examples include making change with bills and shortest path algorithms. 2. Divide and conquer algorithms break problems into smaller subproblems, solve the subproblems recursively, and combine the solutions. Examples are sorting and tree traversal. 3. Dynamic programming improves on naive recursive solutions by storing results of subproblems to avoid recomputing them. Examples include matrix chain multiplication and longest common subsequence. 4. Backtracking algorithms use pruning to iteratively eliminate invalid partial solutions and find all valid ones, such as reconstructing a point set from distances.

Uploaded by

Ahmad Alhour
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

UsefulAlgorithmConcepts KaiserMd.

Nahiduzzaman Feb2010

#[Link] Somelocaloptimumischosen;whenthealgorithmterminates,wehopethatthelocaloptimumisequaltotheglobal optimum. ExamplesofPopularGreedyAlgorithms:Dijkstra,Prim,Kruskalalgorithm. ACMUvaExamples:10020,10340,10440 Reallifeexample: Tomakechangeincurrency,[Link] fiftydollarbill,atendollarbill,afivedollarbill,[Link],weareguranteedtominimizethe [Link],[Link] [Link]. #[Link] Divide:Smallerproblemsaresolvedrecursively(exceptthebasecases). Conquer:Solutiontotheoriginalproblemisformedfromthesolutionstothesubproblems. Thesubproblemsshouldbedisjoint(nonoverlapping). Examples:maximumsubsequencesumproblem,lineartimetreetraversalstrategies,mergesort,quicksort. RunningTime:T(N)=2T(N/2)+O(N) i.e O(NlogN) #[Link] Aproblemthatcanbemathematicallyexpressedrecursivelycanalsobeexpressedasarecursivealgorithm,yieldinga significantperformanceimprovementoveranaivesearch. Anyrecursivemathematicalformulacouldbedirectlytranslatedtoarecursivealgorithm,buttheunderlyingrealityis thatoftenthecompilerwillnotdojusticetotherecursivealgorithm,[Link] suspectthatthisislikelytobethecase,wemustprovidealittlemorehelptothecompiler,byrewritingtherecursive algorithm as anonrecursive algorithmthat systematicallyrecords theanswers tothesubproblems [Link] techniquethatmakesuseofthisapproachisknownasdynamicprogramming. Examples:Matrixmultiplication,allpairsshortestpath,optimalbinarysearchtree,longestcommonsubsequence ACMUvaExamples:10131,10069,10154,116,10003,10261,10271,10201 #[Link] It'[Link],alargegroupofpossiblitiesareeliminatedinone stepwhichisknownaspruning. Example: SupposewearegivenNpoints,[Link]'sxcoordinateis0andthe pointsaregivenfromlefttoright. Ifwearegivenasetofpoints,itiseasytoconstructthesetofdistancesbetweeneverypairofpoints. Buttheturnpikereconstructionproblemistoreconstructapointsetfromthedistances. SupposewearegiventhedistancesetD={1,2,2,2,3,3,3,4,5,5,5,6,7,8,10}. WeknowthatN=6.Thefirstnumberis0andthelast(6th)numberis10. Weremove10fromD.Nextthelargestremainingdistanceis8,whichmeansthateitherthesecondelementis2orthe [Link],wewillconcludethatone [Link]

togetthecorrectresult. ACMUvaExamples:861,10181,10128,10160,10032,10001,704,10270 #[Link]: IMPORTANTWEBSITES/FORACM/ICPCPROGRAMMERS: ACMonlinesite:[Link] and [Link] Helpingsite:[Link] Onlinebook:[Link] References [Link] [Link],[Link] [Link]

You might also like