129x Filetype PDF File size 1.41 MB Source: www.csc.kth.se
Principles of Algorithmic Problem Solving JohanSannemo October24,2018 ii This version of the book is a preliminary draft. Expect to find typos and other mistakes. If you do, please report them to ❥♦❤❛♥✳s❛♥♥❡♠♦✰❜♦♦❦❅❣♠❛✐❧✳❝♦♠. Before report- ing a bug, please check whether it still exists in the lat- est version of this draft, available at ❤tt♣✿✴✴❝s❝✳❦t❤✳s❡✴ ⑦❥s❛♥♥❡♠♦✴s❧❛s❦✴♠❛✐♥✳♣❞❢. Contents Preface ix ReadingthisBook xi I Preliminaries 1 1 AlgorithmsandProblems 3 1.1 ComputationalProblems . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 ProgrammingLanguages . . . . . . . . . . . . . . . . . . . . . . 9 1.4 PseudoCode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 TheKattisOnlineJudge . . . . . . . . . . . . . . . . . . . . . . . 12 1.6 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.7 ChapterNotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 ProgramminginC++ 17 2.1 DevelopmentEnvironments . . . . . . . . . . . . . . . . . . . . . 18 2.1.1 Windows. . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1.2 Ubuntu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.3 macOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.4 Installing the C++ tools . . . . . . . . . . . . . . . . . . . 19 2.2 Hello World! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Variables and Types . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4 Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 iii iv CONTENTS 2.6 If Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.7 For Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.8 WhileLoops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.9 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.10 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.11 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.12 The Preprocessor . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.13 Template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.14 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.15 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3 TheC++StandardLibrary 51 3.1 ✈❡❝t♦r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.1.1 Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2 q✉❡✉❡ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3 st❛❝❦ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.4 ♣r✐♦r✐t②❴q✉❡✉❡ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.5 s❡tand♠❛♣ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.6 Math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.7 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.7.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.7.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.7.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.8 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.8.1 Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.9 Input/Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.9.1 Detecting End of File . . . . . . . . . . . . . . . . . . . . . 66 3.9.2 Input Line by Line . . . . . . . . . . . . . . . . . . . . . . 66 3.9.3 OutputDecimalPrecision . . . . . . . . . . . . . . . . . . 67 3.10 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.11 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4 ImplementationProblems 69 4.1 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.2 ChapterNotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5 TimeComplexity 87 5.1 TheComplexityofInsertionSort . . . . . . . . . . . . . . . . . . 87 5.2 AsymptoticNotation . . . . . . . . . . . . . . . . . . . . . . . . . 91
no reviews yet
Please Login to review.