| Document Type
|
:
|
BL
|
| Record Number
|
:
|
890642
|
| Main Entry
|
:
|
Soltys, Michael,1971-
|
| Title & Author
|
:
|
An introduction to the analysis of algorithms /\ Michael Soltys, California State University Channel Islands, USA.
|
| Edition Statement
|
:
|
3rd edition.
|
| Publication Statement
|
:
|
New Jersey :: World Scientific,, [2018]
|
| Page. NO
|
:
|
1 online resource
|
| ISBN
|
:
|
9789813235915
|
|
|
:
|
: 9813235918
|
|
|
:
|
9789813235908
|
|
|
:
|
981323590X
|
| Bibliographies/Indexes
|
:
|
Includes bibliographical references and index.
|
| Contents
|
:
|
Intro; Contents; Preface; 1. Preliminaries; 1.1 What is correctness?; 1.1.1 Complexity; 1.1.2 Division; 1.1.3 Euclid; 1.1.4 Palindromes; 1.1.5 Further examples; 1.2 Ranking algorithms; 1.2.1 PageRank; 1.2.2 A stable marriage; 1.2.3 Pairwise Comparisons; 1.3 Answers to selected problems; 1.4 Notes; 2. Greedy Algorithms; 2.1 Minimum cost spanning trees; 2.2 Jobs with deadlines and profits; 2.3 Further examples and problems; 2.3.1 Make-change; 2.3.2 Maximum weight matching; 2.3.3 Shortest path; 2.3.4 Huffman codes; 2.4 Answers to selected problems; 2.5 Notes; 3. Divide and Conquer; 3.1 Mergesort
|
|
|
:
|
3.2 Multiplying numbers in binary3.3 Savitchâ#x80;#x99;s algorithm; 3.4 Further examples and problems; 3.4.1 Extended Euclidâ#x80;#x99;s algorithm; 3.4.2 Quicksort; 3.4.3 Git bisect; 3.5 Answers to selected problems; 3.6 Notes; 4. Dynamic Programming; 4.1 Longest monotone subsequence problem; 4.2 All pairs shortest path problem; 4.2.1 Bellman-Ford algorithm; 4.3 Simple knapsack problem; 4.3.1 Dispersed knapsack problem; 4.3.2 General knapsack problem; 4.4 Activity selection problem; 4.5 Jobs with deadlines, durations and profits; 4.6 Further examples and problems; 4.6.1 Consecutive subsequence sum problem
|
|
|
:
|
4.6.2 Shuffle4.7 Answers to selected problems; 4.8 Notes; 5. Online Algorithms; 5.1 List accessing problem; 5.2 Paging; 5.2.1 Demand paging; 5.2.2 FIFO; 5.2.3 LRU; 5.2.4 Marking algorithms; 5.2.5 FWF; 5.2.6 LFD; 5.3 Answers to selected problems; 5.4 Notes; 6. Randomized Algorithms; 6.1 Perfect matching; 6.2 Pattern matching; 6.3 Primality testing; 6.4 Public key cryptography; 6.4.1 Diffie-Hellman key exchange; 6.4.2 ElGamal; 6.4.3 RSA; 6.5 Further problems; 6.6 Answers to selected problems; 6.7 Notes; 7. Algorithms in Linear Algebra; 7.1 Introduction; 7.2 Gaussian Elimination
|
|
|
:
|
7.2.1 Formal proofs of correctness over Z27.3 Gram-Schmidt; 7.4 Gaussian lattice reduction; 7.5 Computing the characteristic polynomial; 7.5.1 Csankyâ#x80;#x99;s algorithm; 7.5.2 Berkowitzâ#x80;#x99;s algorithm; 7.5.3 Proving properties of the characteristic polynomial; 7.6 Answers to selected problems; 7.7 Notes; 8. Computational Foundations; 8.1 Introduction; 8.2 Alphabets, strings and languages; 8.3 Regular languages; 8.3.1 Deterministic Finite Automaton; 8.3.2 Nondeterministic Finite Automata; 8.3.3 Regular Expressions; 8.3.3.1 Method 1; 8.3.3.2 Method 2; 8.3.4 Algebraic laws for Regular Expressions
|
|
|
:
|
8.3.5 Closure properties of regular languages8.3.6 Complexity of transformations and decisions; 8.3.7 Equivalence and minimization of automata; 8.3.8 Languages that are not regular; 8.3.8.1 Pumping Lemma; 8.3.8.2 Myhill-Nerode Theorem; 8.3.9 Automata on terms; 8.4 Context-free languages; 8.4.1 Context-free grammars; 8.4.2 Pushdown automata; 8.4.3 Chomsky Normal Form; 8.4.4 CYK algorithm; 8.4.5 Pumping Lemma for CFLs; 8.4.6 Further observations about CFL; 8.4.7 Other grammars; 8.5 Turing machines; 8.5.1 Nondeterministic TMs; 8.5.2 Encodings; 8.5.3 Decidability; 8.5.4 Church-Turing thesis
|
| Subject
|
:
|
Algorithms, Textbooks.
|
| Subject
|
:
|
Algorithms.
|
| Subject
|
:
|
MATHEMATICS-- Numerical Analysis.
|
| Dewey Classification
|
:
|
518/.1
|
| LC Classification
|
:
|
QA9.58.S63 2018
|