000 09464nam a2200481 i 4500
005 20250919002821.0
008 150324t20152015maua bi 001 0 eng
020 _a9781284049190 (paperback)
_cRM577.96
020 _a1284049191 (paperback)
039 9 _a201506100901
_blan
_c201506050859
_dlan
_c201506050858
_dlan
_c201506050858
_dlan
_y03-24-2015
_zhamudah
040 _aDLC
_beng
_erda
_cDLC
_dYDX
_dYDXCP
_dINU
_dOCLCF
_dNLGGC
_dCDX
_dUKM
_erda
090 _aQA9.58.N433 2015
090 _aQA9.58
_b.N433 2015
100 1 _aNeapolitan, Richard E.,
_eauthor.
245 1 0 _aFoundations of algorithms /
_cRichard E. Neapolitan, PhD, Northwestern University.
250 _aFifth edition.
264 1 _aBurlington, MA :
_bJones & Bartlett Learning,
_c[2015].
264 4 _c© 2015.
300 _axvii, 676 pages :
_billustrations ;
_c24 cm.
336 _atext
_2rdacontent
337 _aunmediated
_2rdamedia
338 _avolume
_2rdacarrier
504 _aIncludes bibliographical references (pages 653-658) and index.
505 0 _gMachine generated contents note:
_g1.
_tAlgorithms: Efficiency, Analysis, and Order --
_g1.1.
_tAlgorithms --
_g1.2.
_tThe Importance of Developing Efficient Algorithms --
_g1.2.1.
_tSequential Search Versus Binary Search --
_g1.2.2.
_tThe Fibonacci Sequence --
_g1.3.
_tAnalysis of Algorithms --
_g1.3.1.
_tComplexity Analysis --
_g1.3.2.
_tApplying the Theory --
_g1.3.3.
_tAnalysis of Correctness --
_g1.4.
_tOrder --
_g1.4.1.
_tAn Intuitive Introduction to Order --
_g1.4.2.
_tA Rigorous Introduction to Order --
_g1.4.3.
_tUsing a Limit to Determine Order --
_g1.5.
_tOutline of This Book --
_tExercises --
_g2.
_tDivide-and-Conquer --
_g2.1.
_tBinary Search --
_g2.2.
_tMergesort --
_g2.3.
_tThe Divide-and-Conquer Approach --
_g2.4.
_tQuicksort (Partition Exchange Sort) --
_g2.5.
_tStrassen's Matrix Multiplication Algorithm --
_g2.6.
_tArithmetic with Large Integers --
_g2.6.1.
_tRepresentation of Large Integers: Addition and Other Linear-Time Operations.
505 0 _g2.6.2.
_tMultiplication of Large Integers --
_g2.7.
_tDetermining Thresholds --
_g2.8.
_tWhen Not to Use Divide-and-Conquer --
_tExercises --
_g3.
_tDynamic Programming --
_g3.1.
_tThe Binomial Coefficient --
_g3.2.
_tFloyd's Algorithm for Shortest Paths --
_g3.3.
_tDynamic Programming and Optimization Problems --
_g3.4.
_tChained Matrix Multiplication --
_g3.5.
_tOptimal Binary Search Trees --
_g3.6.
_tThe Traveling Salesperson Problem --
_g3.7.
_tSequence Alignment --
_tExercises --
_g4.
_tThe Greedy Approach --
_g4.1.
_tMinimum Spanning Trees --
_g4.1.1.
_tPrim's Algorithm --
_g4.1.2.
_tKruskal's Algorithm --
_g4.1.3.
_tComparing Prim's Algorithm with Kruskal's Algorithm --
_g4.1.4.
_tFinal Discussion --
_g4.2.
_tDijkstra's Algorithm for Single-Source Shortest Paths --
_g4.3.
_tScheduling --
_g4.3.1.
_tMinimizing Total Time in the System --
_g4.3.2.
_tScheduling with Deadlines --
_g4.4.
_tHuffman Code --
_g4.4.1.
_tPrefix Codes --
_g4.4.2.
_tHuffman's Algorithm --
_g4.5.
_tThe Greedy Approach versus Dynamic Programming: The Knapsack Problem.
505 0 _g4.5.1.
_tA Greedy Approach to the 0-1 Knapsack Problem --
_g4.5.2.
_tA Greedy Approach to the Fractional Knapsack Problem --
_g4.5.3.
_tA Dynamic Programming Approach to the 0-1 Knapsack Problem --
_g4.5.4.
_tA Refinement of the Dynamic Programming Algorithm for the 0-1 Knapsack Problem --
_tExercises --
_g5.
_tBacktracking --
_g5.1.
_tThe Backtracking Technique --
_g5.2.
_tThe n-Queens Problem --
_g5.3.
_tUsing a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm --
_g5.4.
_tThe Sum-of-Subsets Problem --
_g5.5.
_tGraph Coloring --
_g5.6.
_tThe Hamiltonian Circuits Problem --
_g5.7.
_tThe 0-1 Knapsack Problem --
_g5.7.1.
_tA Backtracking Algorithm for the 0-1 Knapsack Problem --
_g5.7.2.
_tComparing the Dynamic Programming Algorithm and the Backtracking Algorithm for the 0-1 Knapsack Problem --
_tExercises --
_g6.
_tBranch-and-Bound --
_g6.1.
_tIllustrating Branch-and-Bound with the 0-1 Knapsack Problem --
_g6.1.1.
_tBreadth-First Search with Branch-and-Bound Pruning --
_g6.1.2.
_tBest-First Search with Branch-and-Bound Pruning.
505 0 _g6.2.
_tThe Traveling Salesperson Problem --
_g6.3.
_tAbductive Inference (Diagnosis) --
_tExercises --
_g7.
_tIntroduction to Computational Complexity: The Sorting Problem --
_g7.1.
_tComputational Complexity --
_g7.2.
_tInsertion Sort and Selection Sort --
_g7.3.
_tLower Bounds for Algorithms that Remove at Most One Inversion per Comparison --
_g7.4.
_tMergesort Revisited --
_g7.5.
_tQuicksort Revisited --
_g7.6.
_tHeapsort --
_g7.6.1.
_tHeaps and Basic Heap Routines --
_g7.6.2.
_tAn Implementation of Heapsort --
_g7.7.
_tComparison of Mergesort, Quicksort, and Heapsort --
_g7.8.
_tLower Bounds for Sorting Only by Comparison of Keys --
_g7.8.1.
_tDecision Trees for Sorting Algorithms --
_g7.8.2.
_tLower Bounds for Worst-Case Behavior --
_g7.8.3.
_tLower Bounds for Average-Case Behavior --
_g7.9.
_tSorting by Distribution (Radix Sort) --
_tExercises --
_g8.
_tMore Computational Complexity: The Searching Problem --
_g8.1.
_tLower Bounds for Searching Only by Comparisons of Keys --
_g8.1.1.
_tLower Bounds for Worst-Case Behavior.
505 0 _g8.1.2.
_tLower Bounds for Average-Case Behavior --
_g8.2.
_tInterpolation Search --
_g8.3.
_tSearching in Trees --
_g8.3.1.
_tBinary Search Trees --
_g8.3.2.
_tB-Trees --
_g8.4.
_tHashing --
_g8.5.
_tThe Selection Problem: Introduction to Adversary Arguments --
_g8.5.1.
_tFinding the Largest Key --
_g8.5.2.
_tFinding Both the Smallest and Largest Keys --
_g8.5.3.
_tFinding the Second-Largest Key --
_g8.5.4.
_tFinding the kth-Smallest Key --
_g8.5.5.
_tA Probabilistic Algorithm for the Selection Problem --
_tExercises --
_g9.
_tComputational Complexity and Intractability: An Introduction to the Theory of NP --
_g9.1.
_tIntractability --
_g9.2.
_tInput Size Revisited --
_g9.3.
_tThe Three General Problem Categories --
_g9.3.1.
_tProblems for Which Polynomial-Time Algorithms Have Been Found --
_g9.3.2.
_tProblems That Have Been Proven to Be Intractable --
_g9.3.3.
_tProblems That Have Not Been Proven to Be Intractable but for Which Polynomial-Time Algorithms Have Never Been Found --
_g9.4.
_tThe Theory of NP
505 0 _g9.4.1.
_tThe Sets P and NP --
_g9.4.2.
_tNP-Complete Problems --
_g9.4.3.
_tNP-Hard, NP-Easy, and NP-Equivalent Problems --
_g9.5.
_tHandling NP-Hard Problems --
_g9.5.1.
_tAn Approximation Algorithm for the Traveling Salesperson Problem --
_g9.5.2.
_tAn Approximation Algorithm for the Bin-Packing Problem --
_tExercises --
_g10.
_tGenetic Algorithms and Genetic Programming --
_g10.1.
_tGenetics Review --
_g10.2.
_tGenetic Algorithms --
_g10.2.1.
_tAlgorithm --
_g10.2.2.
_tIllustrative Example --
_g10.2.3.
_tThe Traveling Salesperson Problem --
_g10.3.
_tGenetic Programming --
_g10.3.1.
_tIllustrative Example --
_g10.3.2.
_tArtificial Ant --
_g10.3.3.
_tApplication to Financial Trading --
_g10.4.
_tDiscussion and Further Reading --
_tExercises --
_g11.
_tNumber-Theoretic Algorithms --
_g11.1.
_tNumber Theory Review --
_g11.1.1.
_tComposite and Prime Numbers --
_g11.1.2.
_tGreatest Common Divisor --
_g11.1.3.
_tPrime Factorization --
_g11.1.4.
_tLeast Common Multiple --
_g11.2.
_tComputing the Greatest Common Divisor.
505 0 _g11.2.1.
_tEuclid's Algorithm --
_g11.2.2.
_tAn Extension to Euclid's Algorithm --
_g11.3.
_tModular Arithmetic Review --
_g11.3.1.
_tGroup Theory --
_g11.3.2.
_tCongruency Modulo n --
_g11.3.3.
_tSubgroups --
_g11.4.
_tSolving Modular Linear Equations --
_g11.5.
_tComputing Modular Powers --
_g11.6.
_tFinding Large Prime Numbers --
_g11.6.1.
_tSearching for a Large Prime --
_g11.6.2.
_tChecking if a Number Is Prime --
_g11.7.
_tThe RSA Public-Key Cryptosystem --
_g11.7.1.
_tPublic-Key Cryptosystems --
_g11.7.2.
_tThe RSA Cryptosystem --
_tExercises --
_g12.
_tIntroduction to Parallel Algorithms --
_g12.1.
_tParallel Architectures --
_g12.1.1.
_tControl Mechanism --
_g12.1.2.
_tAddress-Space Organization --
_g12.1.3.
_tInterconnection Networks --
_g12.2.
_tThe PRAM Model --
_g12.2.1.
_tDesigning Algorithms for the CREW PRAM Model --
_g12.2.2.
_tDesigning Algorithms for the CRCW PRAM Model --
_tExercises --
_gAppendix A
_tReview of Necessary Mathematics --
_gA.1.
_tNotation --
_gA.2.
_tFunctions --
_gA.3.
_tMathematical Induction.
505 0 _gA.4.
_tTheorems and Lemmas --
_gA.5.
_tLogarithms --
_gA.5.1.
_tDefinition and Properties of Logarithms --
_gA.5.2.
_tThe Natural Logarithm --
_gA.6.
_tSets --
_gA.7.
_tPermutations and Combinations --
_gA.8.
_tProbability --
_gA.8.1.
_tRandomness --
_gA.8.2.
_tThe Expected Value --
_tExercises --
_gAppendix B
_tSolving Recurrence Equations: With Applications to Analysis of Recursive Algorithms --
_gB.1.
_tSolving Recurrences Using Induction --
_gB.2.
_tSolving Recurrences Using the Characteristic Equation --
_gB.2.1.
_tHomogeneous Linear Recurrences --
_gB.2.2.
_tNonhomogeneous Linear Recurrences --
_gB.2.3.
_tChange of Variables (Domain Transformations) --
_gB.3.
_tSolving Recurrences by Substitution --
_gB.4.
_tExtending Results for n, a Power of a Positive Constant b, to n in General --
_gB.5.
_tProofs of Theorems --
_tExercises --
_gAppendix C
_tData Structures for Disjoint Sets.
650 0 _aAlgorithms.
650 0 _aConstructive mathematics.
650 0 _aComputational complexity.
907 _a.b16104183
_b2019-11-12
_c2019-11-12
942 _c01
_n0
_kQA9.58.N433 2015
914 _avtls003581935
990 _arab
991 _aFakulti Sains dan Teknologi
998 _at
_b2015-11-03
_cm
_da
_feng
_gmau
_y0
_z.b16104183
999 _c589466
_d589466