Menu
Home
Log in / Register
 
Home arrow Computer Science arrow Data Structures and Algorithms with Python
Next >
Data Structures and Algorithms with Python - Kent D. Lee




1 Python Programming 1011.1 Chapter Goals1.2 Creating Objects1.2.1 Literal Values1.2.2 Non-literal Object Creation1.3 Calling Methods on Objects1.4 Implementing a Class1.4.1 Creating Objects and Calling Methods1.4.2 The Dog Class1.5 Operator Overloading1.5.1 The Dog Class with Overloaded Addition1.6 Importing Modules1.7 Indentation in Python Programs1.8 The Main Function1.8.1 Python Program Structure1.9 Reading from a File1.9.1 A Text File with Single Line Records1.9.2 Reading and Processing Single Line Records1.9.3 Pattern for Reading Single Line Records from a File1.10 Reading Multi-line Records from a File1.10.1 A Text File with Multiple Line Records1.10.2 Reading and Processing Multi-line Records1.10.3 Pattern for Reading Multi-line Records from a File1.11 A Container Class1.12 Polymorphism1.12.1 Graphics Command Classes1.13 The Accumulator Pattern1.13.1 List of Squares1.13.2 A Graphics Program1.14 Implementing a GUI with Tkinter1.14.1 A GUI Drawing Application1.15 XML Files1.15.1 The Truck XML File1.15.2 The GoToCommand with XML Creation Code1.15.3 Writing Graphics Commands to an XML File1.16 Reading XML Files1.16.1 Using an XML Parser1.17 Chapter Summary1.18 Review Questions1.19 Programming Problems2 Computational Complexity2.1 Chapter Goals2.2 Computer Architecture2.2.1 Running a Program2.3 Accessing Elements in a Python List2.3.1 List Access Timing2.3.2 A Plot XML Sample2.4 Big-Oh Notation2.5 The PyList Append Operation2.5.1 Inefficient Append2.6 A Proof by Induction2.7 Making the PyList Append Efficient2.7.1 Efficient Append2.8 Commonly Occurring Computational Complexities2.9 More Asymptotic Notation2.9.1 Big-Oh Asymptotic Upper Bound2.9.2 Asymptotic Lower Bound2.9.3 Theta Asymptotic Tight Bound2.10 Amortized Complexity2.10.1 A PyList Class2.10.2 Proof of Append Complexity2.11 Chapter Summary2.12 Review Questions2.13 Programming Problems3 Recursion3.1 Chapter Goals3.2 Scope3.2.1 Local Scope3.2.2 Enclosing Scope3.2.3 Global Scope3.2.4 Built-In Scope3.2.5 LEGB3.3 The Run-Time Stack and the Heap3.4 Writing a Recursive Function3.4.1 Sum of Integers3.4.2 Recursive Sum of Integers3.4.3 No Else Needed3.5 Tracing the Execution of a Recursive Function3.6 Recursion in Computer Graphics3.6.1 Recursive Spiral3.7 Recursion on Lists and Strings3.7.1 List Recursion3.7.2 Reversing a List3.7.3 Reversing a String3.7.4 Another Version of Reverse3.8 Using Type Reflection3.8.1 Reflection Reverse3.9 Chapter Summary3.10 Review Questions3.11 Programming Problems4 Sequences4.1 Chapter Goals4.2 Lists4.2.1 The PyList Datatype4.2.2 The PyList Constructor4.2.3 PyList Get and Set4.2.4 PyList Concatenate4.2.5 PyList Append4.2.6 PyList Insert4.2.7 PyList Delete4.2.8 PyList Equality Test4.2.9 PyList Iteration4.2.10 PyList Length4.2.11 PyList Membership4.2.12 PyList String Conversion4.2.13 PyList String Representation4.3 Cloning Objects4.4 Item Ordering4.4.1 The Point Class4.4.2 Calling the Sort Method4.5 Selection Sort4.5.1 Selection Sort's Select Function4.5.2 The Selection Sort Code4.6 Merge Sort4.6.1 The Merge Sort Code4.7 Quicksort4.7.1 The Quicksort Code4.8 Two-Dimensional Sequences4.8.2 The X, O, and Dummy Classes4.9 The Minimax Algorithm4.8.1 The Board Class4.10 Linked Lists4.10.1 The Node Class4.10.2 The LinkedList Constructor4.10.3 LinkedList Get and Set4.10.4 LinkedList Concatenate4.10.5 LinkedList Append4.10.6 LinkedList Insert4.10.7 Other Linked List Operations4.11 Stacks and Queues4.11.1 The Stack Class Code4.11.2 Infix Expression Evaluation4.11.2.1 The Operate Procedure4.11.2.2 Example4.11.3 Radix Sort4.11.4 The CharAt Function4.11.4.1 Radix Sort Example4.12 Chapter Summary4.13 Review Questions4.14 Programming Problems5 Sets and Maps5.1 Chapter Goals5.2 Playing Sudoku5.3 Sets5.4 Hashing5.5 The HashSet Class5.5.1 The HashSet Constructor5.5.2 Storing an Item5.5.3 Collision Resolution5.5.4 HashSet Add Helper Function5.5.5 The Load Factor5.5.6 HashSet Add5.5.7 Deleting an Item5.5.8 HashSet Remove Helper Function5.5.9 HashSet Remove5.5.10 Finding an Item5.5.11 HashSet Membership5.5.12 Iterating Over a Set5.5.13 Other Set Operations5.5.14 HashSet Difference Update5.5.15 HashSet Difference5.6 Solving Sudoku5.6.1 The Sudoku Reduce Function5.7 Maps5.7.1 The HashMap Class5.7.2 HashSet Get Item5.7.3 The HashMap Class5.8 Memoization5.8.1 A Memoized Fibonacci Function5.9 Correlating Two Sources of Information5.10 Chapter Summary5.11 Review Questions5.12 Programming Problems6 Trees6.1 Chapter Goals6.2 Abstract Syntax Trees and Expressions6.2.1 Constructing ASTs6.3 Prefix and Postfix Expressions6.3.1 AST Tree Traversal6.4 Parsing Prefix Expressions6.4.1 The Prefix Expression Grammar6.4.2 A Prefix Expression Parser6.4.3 The Postfix Expression Grammar6.5 Binary Search Trees6.5.1 The BinarySearchTree Class6.6 Search Spaces6.6.1 Depth-First Search Algorithm6.6.2 Sudoku Depth-First Search6.6.3 Calling Sudoku's Solve Function6.7 Chapter Summary6.8 Review Questions6.9 Programming Problems7 Graphs7.1 Chapter Goals7.2 Graph Notation7.3 Searching a Graph7.3.1 Iterative Depth First Search of a Graph7.4 Kruskal's Algorithm7.4.1 Proof of Correctness7.4.2 Kruskal's Complexity Analysis7.4.3 The Partition Data Structure7.5 Dijkstra's Algorithm7.5.1 Dijkstra's Complexity Analysis7.6 Graph Representations7.6.1 A Graph XML File7.6.2 A Vertex Class7.6.3 An Edge Class7.7 Chapter Summary7.8 Review Questions7.9 Programming Problems8 Membership Structures8.1 Chapter Goals8.2 Bloom Filters8.2.1 The Hashing Functions8.2.2 The Bloom Filter Size8.2.3 Drawbacks of a Bloom Filter8.3 The Trie Datatype8.3.1 The Trie Class8.3.2 Inserting into a Trie8.3.3 Membership in a Trie8.3.4 Comparing Tries and Bloom Filters8.4 Chapter Summary8.5 Review Questions8.6 Programming Problems9 Heaps9.1 Chapter Goals9.2 Key Ideas9.3 Building a Heap9.3.1 The buildFrom Method9.4 The Heapsort Algorithm Version 19.4.1 The addToHeap Method9.5 Analysis of Version 1 Phase I9.6 Phase II9.6.1 The siftDownFromTo Method9.7 Analysis of Phase II9.8 The Heapsort Algorithm Version 29.9 Analysis of Heapsort Version 29.10 Comparison to Other Sorting Algorithms9.11 Chapter Summary9.12 Review Questions9.13 Programming Problems10 Balanced Binary Search Trees10.1 Chapter Goals10.2 Binary Search Trees10.2.1 Binary Search Tree Insert10.3 AVL Trees10.3.1 Definitions10.3.2 Implementation Alternatives10.3.3 AVLNode with Stored Balance10.3.4 AVL Tree Iterative Insert10.3.5 Rotations10.3.6 AVL Tree Recursive Insert10.3.7 The Recursive Insert AVL Tree Class Declaration10.3.8 Maintaining Balance Versus Height10.3.9 AVLNode with Stored Height10.3.10 Deleting an Item from an AVL Tree10.4 Splay Trees10.4.1 Splay Rotations10.5 Iterative Splaying10.6 Recursive Splaying10.7 Performance Analysis10.8 Chapter Summary10.9 Review Questions10.10 Programming Problems11 B-Trees11.1 Chapter Goals11.2 Relational Databases11.2.1 The Feed Table11.2.2 The FeedAttribType Table11.2.3 The FeedAttribute Table11.2.4 A Temporary Table11.2.5 Programming the Joining of Tables11.2.6 The readRecord Function11.2.7 Efficient Join11.3 B-Tree Organization11.4 The Advantages of B-Trees11.5 B-Tree Implementation11.6 B-Tree Insert11.7 B-Tree Delete11.8 Chapter Summary11.9 Review Questions11.10 Programming Problems12 Heuristic Search12.1 Chapter Goals12.2 Depth First Search12.2.1 Iterative Depth First Search of a Graph12.2.2 Maze Representation12.2.3 DFS Example12.3 Breadth First Search12.3.1 BFS Example12.4 Hill Climbing12.4.1 Hill Climbing Example12.4.2 Closed Knight's Tour12.4.3 The N-Queens Problem12.5 Best First Search12.5.1 Best First Example12.6 A* Search12.6.1 A* Example12.7 Minimax Revisited12.8 Chapter Summary12.9 Review Questions12.10 Programming Problems
 
Found a mistake? Please highlight the word and press Shift + Enter  
Next >
 
Subjects
Accounting
Business & Finance
Communication
Computer Science
Economics
Education
Engineering
Environment
Geography
Health
History
Language & Literature
Law
Management
Marketing
Philosophy
Political science
Psychology
Religion
Sociology
Travel