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