0. Problem Solving With Algorithms and Data Structures Using Python ...

Problem Solving with Algorithms and Data Structures using Python 6/11/17, —... 6:32 PM

Problem Solving with Algorithms and Data Structures using Python

By Brad Miller and David Ranum, Luther College  A ss ignments ignments (as s ignments ignments .html) .html) 1. Introduction ( Introduc tion/toctree.html) tion/toctree.html) 1.1. Objectives (Introduc (Introduc tion/Objectives tion/Objectives .html) .html) 1.2. Getting Getting Started (Introduc (Introduc tion/GettingStarted.htm tion/GettingStarted.html) l) 1.3. Wha t Is Computer omputer Science? (Introduction/WhatIsCom (Introduction/WhatIsComputerSc puterSc ience.html) ience.html) 1.4. What Is Programming? (Introduction/WhatIsProgramming.html) 1.5. Why Study Data Data Structures and Abs tract Data Types Types ? (Introduction/WhyStudyDataStructuresandAbstractDataTypes.html) 1.6. Why Study Algorithms? (Introduction/WhyStudyAlgorithms.html) 1.7. Review Review of Basic Python (Introduction/ (Introduction/R Review of BasicPython.htm BasicPython.html) l) 1.8. Getting Started w ith Data Data (Introduction/GettingStartedw ithData.htm ithData.html) l) 1.8.1. Built-in Built-in A tomic tomic Data Types (Introduc (Introduc tion/GettingStartedw tion/GettingStartedw ithData.htm ithData.html#bui l#built-i lt-innatomic-data-types) 1.8.2. Built-in Built-in Collection ollection Data Types ype s (Introduction/GettingStartedw (Introduction/GettingStartedw ithData.htm ithData.html#bui l#built-i lt-inncollection-data-types) 1.9. Input and Output (Introduc (Introduc tion/InputandOutput.htm tion/InputandOutput.html) l) 1.9.1. String Formatting Formatting (Introduc (Introduc tion/InputandOutput.htm tion/InputandOutput.html#string-f l#string-f ormatting) ormatting) 1.10. Control Structures (Introduction/ControlStructures.html) 1.11. Exception Handling (Introduction/ExceptionHandling.html) 1.12. Def ining ining Functions (Introduction/Def (Introduction/Def iningFunctions.html iningFunctions.html)) 1.13. Object-Oriented Programming in Python: Defining Classes (Introduction/ObjectOrientedProgramminginPythonDefiningClasses.html) 1.13.1. A Fraction  Class (Introduc (Introduc tion/ObjectOrientedP tion/ObjectOrientedProgra rogram mminginP inginPython ythonD Def iningCl iningClass ass es.html#a-f es.html#a-f rac tionclass) 1.13.2. Inheritance Inheritance : Logic Gates and Circ Circ uits (Introduction/ObjectOrientedProgramminginPythonDefiningClasses.html#inheritancelogic-gates-and-circuits) 1.14. Summary (Introduction/Summary.html) 1.15. Key Terms (Introduction/KeyTerms.html) 1.16. Discussion Questions (Introduction/DiscussionQuestions.html)

1 of 6

Problem Solving with Algorithms and Data Structures using Python 6/11/17, —... 6:32 PM

1.17. Programming Exer cises (Introduction/ProgrammingExer cises .html) 2. Analysis (AlgorithmAnalysis/toctree.html) 2.1. Objectives (AlgorithmAnalysis/Objectives.html) 2.2. What Is Algorithm Analysis? (AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html) 2.3. Big-O Notation (A lgorithmA nalysis/BigONotation.html) 2.4. A n A nagram Detection Example (A lgorithmAnalysis/A nA nagramDetectionExample.html) 2.4.1. Solution 1: Checking Of f  (AlgorithmAnalysis/AnAnagramDetectionExample.html#solution-1-checking-off) 2.4.2. Solution 2: Sort a nd Compare (AlgorithmAnalysis/AnAnagramDetectionExample.html#solution-2-sort-and-compare) 2.4.3. Solution 3: Brute Forc e (AlgorithmAnalysis/AnAnagramDetectionExample.html#solution-3-brute-force) 2.4.4. Solution 4: Count and Compare (AlgorithmAnalysis/AnAnagramDetectionExample.html#solution-4-count-andcompare) 2.5. Performance of Python Data Structures (AlgorithmAnalysis/PerformanceofPythonDataStructures.html) 2.6. Lists (AlgorithmAnalysis/Lists.html) 2.7. Dictionaries (A lgorithmAnalys is/Dictionaries.html) 2.8. Summary (A lgorithmAnalysis/Summary.html) 2.9. Key Terms (A lgorithmAnalysis/KeyTerms.html) 2.10. Discussion Questions (AlgorithmAnalysis/DiscussionQuestions.html) 2.11. Programming Exer cises (A lgorithmAnalysis/ProgrammingExer cises.html) 3. Basic Data Structures (BasicDS/toctree.html) 3.1. Objectives (BasicDS/Objectives .html) 3.2. What A re Linear Structures? (BasicDS/WhatAr eLinearStructures.html) 3.3. What is a Stack? ( BasicDS/WhatisaStac k.html) 3.4. The Stack Abstract Data Type (BasicDS/TheStackAbstractDataType.html) 3.5. Implementing a Stac k in Python (Bas icDS/ImplementingaStackinPython.html) 3.6. Simple Balanced Parenthes es (BasicDS/SimpleBalancedParenthes es.html) 3.7. Balanced Symbols (A General Case) (BasicDS/BalancedSymbols(AGeneralCase).html) 3.8. Converting Decimal Numbers to Binary Numbers (BasicDS/ConvertingDecimalNumberstoBinaryNumbers.html) 3.9. Infix, Prefix and Postfix Expressions (BasicDS/InfixPrefixandPostfixExpressions.html) 3.9.1. Conversion of Infix Expressions to Prefix and Postfix (BasicDS/Inf ixPref ixandPostf ixExpres sions.html#conversion-of -infix-expr ess ions-toprefix-and-postfix) 3.9.2. General Infix-to-Postfix Conversion (BasicDS/Inf ixPref ixandPostf ixExpres sions.html#general-inf ix-to-postf ix-conver sion) 3.9.3. Postfix Evaluation (BasicDS/InfixPrefixandPostfixExpressions.html#postfixevaluation) 3.10. What Is a Queue? (BasicDS/WhatIsaQueue.html) 3.11. The Queue A bstract Data Type (Bas icDS/TheQueueA bstr actDataType.html) 3.12. Implementing a Queue in Python (Bas icDS/ImplementingaQueueinPython.html) 3.13. Simulation: Hot Potato (Bas icDS/SimulationHotPotato.html) 3.14. Simulation: Printing Tasks (Bas icDS/SimulationPrintingTasks.html) 3.14.1. Main Simulation Steps (Bas icDS/SimulationPrintingTasks.html#main-s imulationsteps)

2 of 6

Problem Solving with Algorithms and Data Structures using Python 6/11/17, —... 6:32 PM

3.14.2. Python Implementation (BasicDS/SimulationPrintingTasks.html#pythonimplementation) 3.14.3. Discuss ion (BasicDS/SimulationPrintingTasks.html#disc uss ion) 3.15. What Is a Deque? (BasicDS/WhatIsaDeque.html) 3.16. The Deque Abs trac t Data Type (BasicDS/TheDequeA bstr actDataType.html) 3.17. Implementing a Deque in Python (Bas icDS/ImplementingaDequeinPython.html) 3.18. Palindrome-Checker (BasicDS/PalindromeChecker.html) 3.19. Lists (BasicDS/Lists.html) 3.20. The Unordered List Abstract Data Type (BasicDS/TheUnorderedListAbstractDataType.html) 3.21. Implementing an Unordered List: Linked Lists (BasicDS/ImplementinganUnorderedListLinkedLists.html) 3.21.1. The Node   Class (BasicDS/ImplementinganUnorderedListLinkedLists.html#thenode-class) 3.21.2. The Unordered List  Class (BasicDS/ImplementinganUnorderedListLinkedLists.html#the-unordered-list-class) 3.22. The Ordered List Abstract Data Type (BasicDS/TheOrderedListAbstractDataType.html) 3.23. Implementing an Ordered List (BasicDS/ImplementinganOrderedList.html) 3.23.1. A nalysis of Linked Lists (BasicDS/ImplementinganOrderedList.html#analys isof-linked-lists) 3.24. Summary (BasicDS/Summary.html) 3.25. Key Terms (BasicDS/KeyTerms.html) 3.26. Discussion Questions (BasicDS/DiscussionQuestions.html) 3.27. Programming Exercises (BasicDS/ProgrammingExercises.html) 4. Recursion (Recursion/toctree.html) 4.1. Objectives (Recursion/Objectives.html) 4.2. What Is Recur sion? (Recur sion/WhatIsRecur sion.html) 4.3. Calculating the Sum of a List of Numbers (Recursion/pythondsCalculatingtheSumofaListofNumbers.html) 4.4. The Three Law s of Recurs ion (Recursion/TheThreeLaw sof Recurs ion.html) 4.5. Converting an Integer to a String in Any Base (Recursion/pythondsConvertinganIntegertoaStringinAnyBase.html) 4.6. Stack Frames: Implementing Recursion (Recursion/StackFramesImplementingRecursion.html) 4.7. Introduction: Visualizing Recursion (Recursion/pythondsintroVisualizingRecursion.html) 4.8. Sierpinski Triangle (Recurs ion/pythonds SierpinskiTriangle.html) 4.9. Complex Recursive Problems (Recursion/ComplexRecursiveProblems.html) 4.10. Tow er of Hanoi (Recurs ion/Tow erof Hanoi.html) 4.11. Exploring a Maze (Recursion/ExploringaMaze.html) 4.12. Dynamic Programming (Recursion/DynamicProgramming.html) 4.13. Summary (Recursion/Summary.html) 4.14. Key Terms (Recursion/KeyTerms.html) 4.15. Discussion Questions (Recursion/DiscussionQuestions.html) 4.16. Glossary (Recursion/Glossary.html) 4.17. Programming Exercises (Recurs ion/pythonds ProgrammingExer cises.html) 5. Sorting and Searching (SortSearch/toctree.html)

3 of 6

Problem Solving with Algorithms and Data Structures using Python 6/11/17, —... 6:32 PM

5.1. Objectives (SortSearch/Objectives.html) 5.2. Searching (SortSearch/searching.html) 5.3. The Sequential Search ( SortSearc h/TheSequentialSearch.html) 5.3.1. Analysis of Sequential Search (SortSearch/TheSequentialSearch.html#analysis-of-sequential-search) 5.4. The Binary Search (SortSearch/TheBinarySearch.html) 5.4.1. Analysis of Binary Search ( SortSearch/TheBinarySearc h.html#analys is-of binary-search) 5.5. Hashing ( SortSearc h/Hashing.html) 5.5.1. Hash Functions (SortSearch/Hashing.html#hash-functions) 5.5.2. Collision Resolution (SortSearch/Hashing.html#collision-res olution) 5.5.3. Implementing the Map  A bstrac t Data Type (SortSearch/Hashing.html#implementing-the-map-abstract-data-type) 5.5.4. A nalys is of Hashing ( SortSearch/Hashing.html#analys is-of- hashing) 5.6. Sorting (SortSearch/sorting.html) 5.7. The Bubble Sort (SortSearch/TheBubbleSort.html) 5.8. The Selection Sort (SortSearch/TheSelectionSort.html) 5.9. The Insertion Sort (SortSear ch/TheInser tionSort.html) 5.10. The Shell Sort ( SortSearc h/TheShellSort.html) 5.11. The Merge Sort (SortSearch/TheMergeSort.html) 5.12. The Quick Sor t (SortSearc h/TheQuickSort.html) 5.13. Summary (SortSearch/Summary.html) 5.14. Key Terms (SortSearch/Key Terms.html) 5.15. Discussion Questions (SortSearch/DiscussionQuestions.html) 5.16. Programming Exerc ises (SortSearch/ProgrammingExer cises.html) 6. Trees and Tree A lgorithms (Trees/toc tree.html) 6.1. Objectives (Trees/Objectives.html) 6.2. Examples of Trees (Trees/Examplesof Trees .html) 6.3. Vocabulary and Definitions (Trees/VocabularyandDefinitions.html) 6.4. List of Lists Representation (Trees/ListofListsRepresentation.html) 6.5. Nodes and References (Trees/NodesandReferences.html) 6.6. Parse Tree (Trees/ParseTree.html) 6.7. Tree Traversals (Trees/TreeTrav ers als.html) 6.8. Priority Queues w ith Binary Heaps (Trees /PriorityQueues w ithBinary Heaps.html) 6.9. Binary Heap Operations (Trees/BinaryHeapOperations.html) 6.10. Binary Heap Implementation (Trees/BinaryHeapImplementation.html) 6.10.1. The Stru ctur e Property (Trees/BinaryHeapImplementation.html#the-structur eproperty) 6.10.2. The Heap Order Property (Trees/Binary HeapImplementation.html#the-heaporder-property) 6.10.3. Heap Operations (Trees/BinaryHeapImplementation.html#heap-operations ) 6.11. Binary Search Trees (Trees/BinarySearchTrees.html) 6.12. Search Tree Operations (Trees/SearchTreeOperations.html) 6.13. Search Tree Implementation (Trees/SearchTreeImplementation.html) 6.14. Search Tree Analysis (Trees/SearchTreeAnalysis.html) 6.15. Balanced Binary Search Trees (Trees/BalancedBinarySearchTrees.html) 6.16. AV L Tree Perfor mance (Trees/AV LTreePerformance.html) 6.17. AVL Tree Implementation (Trees/AVLTreeImplementation.html)

4 of 6

Problem Solving with Algorithms and Data Structures using Python 6/11/17, —... 6:32 PM

6.18. Summary of Map ADT Implementations (Trees/SummaryofMapADTImplementations.html) 6.19. Summary (Trees/Summary.html) 6.20. Key Terms (Trees/KeyTerms.html) 6.21. Discussion Questions (Trees/DiscussionQuestions.html) 6.22. Programming Exercises (Trees/ProgrammingExercises.html) 7. Graphs and Graph Algorithms (Graphs/toctree.html) 7.1. Objectives (Graphs/Objectives.html) 7.2. Vocabulary and Definitions (Graphs/VocabularyandDefinitions.html) 7.3. The Graph Abstract Data Type (Graphs/TheGraphAbstractDataType.html) 7.4. An A djacency Matrix (Graphs/A nAdjacency Matrix.html) 7.5. An A djacency List (Graphs/A nAdjacency List.html) 7.6. Implementation (Graphs /Implementation.html) 7.7. The Word Ladder Problem (Graphs /TheWordLadderProblem.html) 7.8. Building the Word La dder Graph (Graphs/BuildingtheWordLadde rGraph.html) 7.9. Implementing Breadth First Search (Graphs/ImplementingBreadthFirstSearch.html) 7.10. Breadth First Search Analys is (Graphs/BreadthFirstSearchAnalys is.html) 7.11. The Knight’s Tour Problem (Graphs/TheKnightsTourProblem.html) 7.12. Building the Knight’s Tour Graph (Graphs/BuildingtheKnightsTourGraph.html) 7.13. Implementing Knight’s Tour (Graphs /ImplementingKnightsTour.html) 7.14. Knight’s Tour Analysis (Graphs/KnightsTourAnalysis.html) 7.15. General Depth First Sear ch (Graphs /GeneralDepthFirs tSearch.html) 7.16. Depth First Search Analysis (Graphs/DepthFirstSearchAnalysis.html) 7.17. Topological Sorting (Graphs/TopologicalSorting.html) 7.18. Strongly Connec ted Components (Graphs /StronglyConnectedComponents .html) 7.19. Shortes t Path Problems (Graphs /ShortestPathProblems.html) 7.20. Dijkstra’s Algorithm (Graphs/DijkstrasAlgorithm.html) 7.21. Analysis of Dijkstra’s Algorithm (Graphs/AnalysisofDijkstrasAlgorithm.html) 7.22. Prim’s Spanning Tree Algorithm (Graphs/PrimsSpanningTreeAlgorithm.html) 7.23. Summary (Graphs/Summary.html) 7.24. Key Terms (Graphs/KeyTerms.html) 7.25. Discussion Questions (Graphs/DiscussionQuestions.html) 7.26. Programming Exer cises (Graphs /ProgrammingExer cises.html)

 Acknowledgements We are ver y gratef ul to Franklin Beedle Publishers f or allow ing us to make this interac tive textbook f reely av ailable. This online ver sion is dedicated to the memory of our f irst editor, Jim Leisy, w ho w anted us to “change the w orld.”

Indices and tables Index (genindex.html) Module Index (py-modindex.html) Search Page (search.html)

(http://creativecommons.org/licenses/by-nc-sa/4.0/)

5 of 6

Problem Solving with Algorithms and Data Structures using Python 6/11/17, —... 6:32 PM

Problem Solving w ith Algorithms and Data Structures using Python by Bradley N. Miller, David L. Ranum is licensed under a Creative Commons AttributionNonCommercial-ShareAlike 4.0 International License (http://creativecommons.org/licenses/by-nc-sa/4.0/).

6 of 6