南京大学：《计算机问题求解》课程教学资源（课件讲稿）算法的效率 Efficiency（简版）

南京大学：《计算机问题求解》课程教学资源（课件讲稿）算法的效率 Efficiency

Number Theory 1. Six proofs of the infinity of primes …… 3. Binomial coefficients are (almost) never powers 4. Representing numbers as sums of two squares …… 8. Some irrational numbers 9. Three times π2/6 Geometry 10. Hilbert’s third problem: decomposing polyhedra63 11. Lines in the plane and decompositions of graphs …… 15. The Borromean rings don’t exist …… 17. Every large point set has an obtuse angle 18. Borsuk’s conjecture Analysis …… 21. The fundamental theorem of algebra …… 25. Cotangent and the Herglotz trick 26. Buffon’s needle problem Combinatorics 27. Pigeon-hole and double counting …… 32. Cayley’s formula for the number of trees 33. Identities versus bijections …… 36. The Dinitz problem247 37. Permanents and the power of entropy253 …… 41. Communicating without errors 42. The chromatic number of Kneser graphs …… 44. Probability makes counting (sometimes) easy

《计算机问题求解》课程参考书籍资料：《Mathematics for Computer Science》PDF电子书（revised Wednesday 6th June, 2018，Eric Lehman、F Thomson Leighton、Albert R Meyer）

CHAPTER ONE:ANALYSIS OF ALGORITHMS CHAPTER TWO:RECURRENCE RELATIONS CHAPTER THREE:GENERATING FUNCTIONS CHAPTER FOUR:ASYMPTOTIC APPROXIMATIONS CHAPTER FIVE:ANALYTIC COMBINATORICS CHAPTER SIX:TREES CHAPTER SEVEN:PERMUTATIONS CHAPTER EIGHT:STRINGS AND TRIES CHAPTER NINE:WORDS AND MAPPINGS

《计算机问题求解》课程教学资源（阅读材料）THE CLASSIC WORK EXTENDED AND REFINED《The Art of Computer Programming》Vol4A Combinatorial Algorithms Part 1（DONALD E.KNUTH）

Preface Part I: Preliminaries Column 1: Cracking the Oyster Column 2: Aha! Algorithms [Sketch] Column 4: Writing Correct Programs [Sketch] Column 5: A Small Matter of Programming [Sketch] Part II: Performance Column 7: The Back of the Envelope Column 8: Algorithm Design Techniques [Sketch] Part III: The Product Column 14: Heaps [Sketch] Column 15: Strings of Pearls Epilog to the First Edition Epilog to the Second Edition Appendix 2: An Estimation Quiz Appendix 3: Cost Models for Time and Space Appendix 4: Rules for Code Tuning Solutions for Column 1 Column 5 Column 7 Column 15 Index About The Book Why a Second Edition? To Readers of the First Edition About the First Edition Errata Supporting Material Source Code Web Sites Relevant to the Book Animation of Sorting Algorithms Tricks of the Trade Teaching Material

1 Recurrent Problems 2 Sums 3 Integer Functions 4 Number Theory 5 Binomial Coefficients 6 Special Numbers 7 Generating Functions 8 Discrete Probability 9 Asymptotics

《计算机问题求解》课程参考书籍教材：Abstract Data Types and Algorithms（Second Edition，Manoochehr Azmoodeh）

List of Theorems, Lemmas, and Corollaries xix Preface xxi CHAPTER 1 Counting 1 CHAPTER 2 Cryptography and Number Theory 59 CHAPTER 3 Reflections on Logic and Proof 117 CHAPTER 4 Induction, Recursion, and Recurrences 161 CHAPTER 5 Probability 249 CHAPTER 6 Graphs 359 APPENDIX A Derivation of the More General Master Theorem 449 APPENDIX B Answers and Hints to Selected Problems 461 Bibliography 477 Index 479