Efnisyfirlit

• Title Page
• Copyright Page
• Preface
• Contents
• 1 Python Primer
  • 1.1 Python Overview
    • 1.1.1 The Python Interpreter
    • 1.1.2 Preview of a Python Program
  • 1.2 Objects in Python
    • 1.2.1 Identifiers, Objects, and the Assignment Statement
    • 1.2.2 Creating and Using Objects
    • 1.2.3 Python’s Built-In Classes
  • 1.3 Expressions, Operators, and Precedence
    • 1.3.1 Compound Expressions and Operator Precedence
  • 1.4 Control Flow
    • 1.4.1 Conditionals
    • 1.4.2 Loops
  • 1.5 Functions
    • 1.5.1 Information Passing
    • 1.5.2 Python’s Built-In Functions
  • 1.6 Simple Input and Output
    • 1.6.1 Console Input and Output
    • 1.6.2 Files
  • 1.7 Exception Handling
    • 1.7.1 Raising an Exception
    • 1.7.2 Catching an Exception
  • 1.8 Iterators and Generators
  • 1.9 Additional Python Conveniences
    • 1.9.1 Conditional Expressions
    • 1.9.2 Comprehension Syntax
    • 1.9.3 Packing and Unpacking of Sequences
  • 1.10 Scopes and Namespaces
  • 1.11 Modules and the Import Statement
    • 1.11.1 Existing Modules
  • 1.12 Exercises
• 2 Object-Oriented Programming
  • 2.1 Goals, Principles, and Patterns
    • 2.1.1 Object-Oriented Design Goals
    • 2.1.2 Object-Oriented Design Principles
    • 2.1.3 Design Patterns
  • 2.2 Software Development
    • 2.2.1 Design
    • 2.2.2 Pseudo-Code
    • 2.2.3 Coding Style and Documentation
    • 2.2.4 Testing and Debugging
  • 2.3 Class Definitions
    • 2.3.1 Example: CreditCard Class
    • 2.3.2 Operator Overloading and Python’s Special Methods
    • 2.3.3 Example: Multidimensional Vector Class
    • 2.3.4 Iterators
    • 2.3.5 Example: Range Class
  • 2.4 Inheritance
    • 2.4.1 Extending the CreditCard Class
    • 2.4.2 Hierarchy of Numeric Progressions
    • 2.4.3 Abstract Base Classes
  • 2.5 Namespaces and Object-Orientation
    • 2.5.1 Instance and Class Namespaces
    • 2.5.2 Name Resolution and Dynamic Dispatch
  • 2.6 Shallow and Deep Copying
  • 2.7 Exercises
• 3 Algorithm Analysis
  • 3.1 Experimental Studies
    • 3.1.1 Moving Beyond Experimental Analysis
  • 3.2 The Seven Functions Used in This Book
    • 3.2.1 Comparing Growth Rates
  • 3.3 Asymptotic Analysis
    • 3.3.1 The “Big-Oh” Notation
    • 3.3.2 Comparative Analysis
    • 3.3.3 Examples of Algorithm Analysis
  • 3.4 Simple Justification Techniques
    • 3.4.1 By Example
    • 3.4.2 The “Contra” Attack
    • 3.4.3 Induction and Loop Invariants
  • 3.5 Exercises
• 4 Recursion
  • 4.1 Illustrative Examples
    • 4.1.1 The Factorial Function
    • 4.1.2 Drawing an English Ruler
    • 4.1.3 Binary Search
    • 4.1.4 File Systems
  • 4.2 Analyzing Recursive Algorithms
  • 4.3 Recursion Run Amok
    • 4.3.1 Maximum Recursive Depth in Python
  • 4.4 Further Examples of Recursion
    • 4.4.1 Linear Recursion
    • 4.4.2 Binary Recursion
    • 4.4.3 Multiple Recursion
  • 4.5 Designing Recursive Algorithms
  • 4.6 Eliminating Tail Recursion
  • 4.7 Exercises
• 5 Array-Based Sequences
  • 5.1 Python’s Sequence Types
  • 5.2 Low-Level Arrays
    • 5.2.1 Referential Arrays
    • 5.2.2 Compact Arrays in Python
  • 5.3 Dynamic Arrays and Amortization
    • 5.3.1 Implementing a Dynamic Array
    • 5.3.2 Amortized Analysis of Dynamic Arrays
    • 5.3.3 Python’s List Class
  • 5.4 Efficiency of Python’s Sequence Types
    • 5.4.1 Python’s List and Tuple Classes
    • 5.4.2 Python’s String Class
  • 5.5 Using Array-Based Sequences
    • 5.5.1 Storing High Scores for a Game
    • 5.5.2 Sorting a Sequence
    • 5.5.3 Simple Cryptography
  • 5.6 Multidimensional Data Sets
  • 5.7 Exercises
• 6 Stacks, Queues, and Deques
  • 6.1 Stacks
    • 6.1.1 The Stack Abstract Data Type
    • 6.1.2 Simple Array-Based Stack Implementation
    • 6.1.3 Reversing Data Using a Stack
    • 6.1.4 Matching Parentheses and HTML Tags
  • 6.2 Queues
    • 6.2.1 The Queue Abstract Data Type
    • 6.2.2 Array-Based Queue Implementation
  • 6.3 Double-Ended Queues
    • 6.3.1 The Deque Abstract Data Type
    • 6.3.2 Implementing a Deque with a Circular Array
    • 6.3.3 Deques in the Python Collections Module
  • 6.4 Exercises
• 7 Linked Lists
  • 7.1 Singly Linked Lists
    • 7.1.1 Implementing a Stack with a Singly Linked List
    • 7.1.2 Implementing a Queue with a Singly Linked List
  • 7.2 Circularly Linked Lists
    • 7.2.1 Round-Robin Schedulers
    • 7.2.2 Implementing a Queue with a Circularly Linked List
  • 7.3 Doubly Linked Lists
    • 7.3.1 Basic Implementation of a Doubly Linked List
    • 7.3.2 Implementing a Deque with a Doubly Linked List
  • 7.4 The Positional List ADT
    • 7.4.1 The Positional List Abstract Data Type
    • 7.4.2 Doubly Linked List Implementation
  • 7.5 Sorting a Positional List
  • 7.6 Case Study: Maintaining Access Frequencies
    • 7.6.1 Using a Sorted List
    • 7.6.2 Using a List with the Move-to-Front Heuristic
  • 7.7 Link-Based vs. Array-Based Sequences
  • 7.8 Exercises
• 8 Trees
  • 8.1 General Trees
    • 8.1.1 Tree Definitions and Properties
    • 8.1.2 The Tree Abstract Data Type
    • 8.1.3 Computing Depth and Height
  • 8.2 Binary Trees
    • 8.2.1 The Binary Tree Abstract Data Type
    • 8.2.2 Properties of Binary Trees
  • 8.3 Implementing Trees
    • 8.3.1 Linked Structure for Binary Trees
    • 8.3.2 Array-Based Representation of a Binary Tree
    • 8.3.3 Linked Structure for General Trees
  • 8.4 Tree Traversal Algorithms
    • 8.4.1 Preorder and Postorder Traversals of General Trees
    • 8.4.2 Breadth-First Tree Traversal
    • 8.4.3 Inorder Traversal of a Binary Tree
    • 8.4.4 Implementing Tree Traversals in Python
    • 8.4.5 Applications of Tree Traversals
    • 8.4.6 Euler Tours and the Template Method Pattern
  • 8.5 Case Study: An Expression Tree
  • 8.6 Exercises
• 9 Priority Queues
  • 9.1 The Priority Queue Abstract Data Type
    • 9.1.1 Priorities
    • 9.1.2 The Priority Queue ADT
  • 9.2 Implementing a Priority Queue
    • 9.2.1 The Composition Design Pattern
    • 9.2.2 Implementation with an Unsorted List
    • 9.2.3 Implementation with a Sorted List
  • 9.3 Heaps
    • 9.3.1 The Heap Data Structure
    • 9.3.2 Implementing a Priority Queue with a Heap
    • 9.3.3 Array-Based Representation of a Complete Binary Tree
    • 9.3.4 Python Heap Implementation
    • 9.3.5 Analysis of a Heap-Based Priority Queue
    • 9.3.6 Bottom-Up Heap Construction
    • 9.3.7 Python’s heapq Module
  • 9.4 Sorting with a Priority Queue
    • 9.4.1 Selection-Sort and Insertion-Sort
    • 9.4.2 Heap-Sort
  • 9.5 Adaptable Priority Queues
    • 9.5.1 Locators
    • 9.5.2 Implementing an Adaptable Priority Queue
  • 9.6 Exercises
• 10 Maps, Hash Tables, and Skip Lists
  • 10.1 Maps and Dictionaries
    • 10.1.1 The Map ADT
    • 10.1.2 Application: Counting Word Frequencies
    • 10.1.3 Python’s MutableMapping Abstract Base Class
    • 10.1.4 Our MapBase Class
    • 10.1.5 Simple Unsorted Map Implementation
  • 10.2 Hash Tables
    • 10.2.1 Hash Functions
    • 10.2.2 Collision-Handling Schemes
    • 10.2.3 Load Factors, Rehashing, and Efficiency
    • 10.2.4 Python Hash Table Implementation
  • 10.3 Sorted Maps
    • 10.3.1 Sorted Search Tables
    • 10.3.2 Two Applications of Sorted Maps
  • 10.4 Skip Lists
    • 10.4.1 Search and Update Operations in a Skip List
    • 10.4.2 Probabilistic Analysis of Skip Lists
  • 10.5 Sets, Multisets, and Multimaps
    • 10.5.1 The Set ADT
    • 10.5.2 Python’s MutableSet Abstract Base Class
    • 10.5.3 Implementing Sets, Multisets, and Multimaps
  • 10.6 Exercises
• 11 Search Trees
  • 11.1 Binary Search Trees
    • 11.1.1 Navigating a Binary Search Tree
    • 11.1.2 Searches
    • 11.1.3 Insertions and Deletions
    • 11.1.4 Python Implementation
    • 11.1.5 Performance of a Binary Search Tree
  • 11.2 Balanced Search Trees
    • 11.2.1 Python Framework for Balancing Search Trees
  • 11.3 AVL Trees
    • 11.3.1 Update Operations
  • 11.3.2 Python Implementation
  • 11.4 Splay Trees
    • 11.4.1 Splaying
    • 11.4.2 When to Splay
    • 11.4.3 Python Implementation
    • 11.4.4 Amortized Analysis of Splaying
  • 11.5 (2,4) Trees
    • 11.5.1 Multiway Search Trees
    • 11.5.2 (2,4)-Tree Operations
  • 11.6 Red-Black Trees
    • 11.6.1 Red-Black Tree Operations
    • 11.6.2 Python Implementation
  • 11.7 Exercises
• 12 Sorting and Selection
  • 12.1 Why Study Sorting Algorithms?
  • 12.2 Merge-Sort
    • 12.2.1 Divide-and-Conquer
    • 12.2.2 Array-Based Implementation of Merge-Sort
    • 12.2.3 The Running Time of Merge-Sort
    • 12.2.4 Merge-Sort and Recurrence Equations
    • 12.2.5 Alternative Implementations of Merge-Sort
  • 12.3 Quick-Sort
    • 12.3.1 Randomized Quick-Sort
    • 12.3.2 Additional Optimizations for Quick-Sort
  • 12.4 Studying Sorting through an Algorithmic Lens
    • 12.4.1 Lower Bound for Sorting
    • 12.4.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort
  • 12.5 Comparing Sorting Algorithms
  • 12.6 Python’s Built-In Sorting Functions
    • 12.6.1 Sorting According to a Key Function
  • 12.7 Selection
    • 12.7.1 Prune-and-Search
    • 12.7.2 Randomized Quick-Select
    • 12.7.3 Analyzing Randomized Quick-Select
  • 12.8 Exercises
• 13 Text Processing
  • 13.1 Abundance of Digitized Text
    • 13.1.1 Notations for Strings and the Python str Class
  • 13.2 Pattern-Matching Algorithms
    • 13.2.1 Brute Force
    • 13.2.2 The Boyer-Moore Algorithm
    • 13.2.3 The Knuth-Morris-Pratt Algorithm
  • 13.3 Dynamic Programming
    • 13.3.1 Matrix Chain-Product
    • 13.3.2 DNA and Text Sequence Alignment
  • 13.4 Text Compression and the Greedy Method
    • 13.4.1 The Huffman Coding Algorithm
    • 13.4.2 The Greedy Method
  • 13.5 Tries
    • 13.5.1 Standard Tries
    • 13.5.2 Compressed Tries
    • 13.5.3 Suffix Tries
    • 13.5.4 Search Engine Indexing
  • 13.6 Exercises
• 14 Graph Algorithms
  • 14.1 Graphs
    • 14.1.1 The Graph ADT
  • 14.2 Data Structures for Graphs
    • 14.2.1 Edge List Structure
    • 14.2.2 Adjacency List Structure
    • 14.2.3 Adjacency Map Structure
    • 14.2.4 Adjacency Matrix Structure
    • 14.2.5 Python Implementation
  • 14.3 Graph Traversals
    • 14.3.1 Depth-First Search
    • 14.3.2 DFS Implementation and Extensions
    • 14.3.3 Breadth-First Search
  • 14.4 Transitive Closure
  • 14.5 Directed Acyclic Graphs
    • 14.5.1 Topological Ordering
  • 14.6 Shortest Paths
    • 14.6.1 Weighted Graphs
    • 14.6.2 Dijkstra’s Algorithm
  • 14.7 Minimum Spanning Trees
    • 14.7.1 Prim-Jarník Algorithm
    • 14.7.2 Kruskal’s Algorithm
    • 14.7.3 Disjoint Partitions and Union-Find Structures
  • 14.8 Exercises
• 15 Memory Management and B-Trees
  • 15.1 Memory Management
    • 15.1.1 Memory Allocation
    • 15.1.2 Garbage Collection
    • 15.1.3 Additional Memory Used by the Python Interpreter
  • 15.2 Memory Hierarchies and Caching
    • 15.2.1 Memory Systems
    • 15.2.2 Caching Strategies
  • 15.3 External Searching and B-Trees
    • 15.3.1 (a,b) Trees
    • 15.3.2 B-Trees
  • 15.4 External-Memory Sorting
    • 15.4.1 Multiway Merging
  • 15.5 Exercises
• A Character Strings in Python
• B Useful Mathematical Facts
• Bibliography
• Index

UM RAFBÆKUR Á HEIMKAUP.IS

Bókahillan þín er þitt svæði og þar eru bækurnar þínar geymdar. Þú kemst í bókahilluna þína hvar og hvenær sem er í tölvu eða snjalltæki. Einfalt og þægilegt!

Rafbók til eignar
Rafbók til eignar þarf að hlaða niður á þau tæki sem þú vilt nota innan eins árs frá því bókin er keypt.

Þú kemst í bækurnar hvar sem er
Þú getur nálgast allar raf(skóla)bækurnar þínar á einu augabragði, hvar og hvenær sem er í bókahillunni þinni. Engin taska, enginn kyndill og ekkert vesen (hvað þá yfirvigt).

Auðvelt að fletta og leita
Þú getur flakkað milli síðna og kafla eins og þér hentar best og farið beint í ákveðna kafla úr efnisyfirlitinu. Í leitinni finnur þú orð, kafla eða síður í einum smelli.

Glósur og yfirstrikanir
Þú getur auðkennt textabrot með mismunandi litum og skrifað glósur að vild í rafbókina. Þú getur jafnvel séð glósur og yfirstrikanir hjá bekkjarsystkinum og kennara ef þeir leyfa það. Allt á einum stað.

Hvað viltu sjá? / Þú ræður hvernig síðan lítur út
Þú lagar síðuna að þínum þörfum. Stækkaðu eða minnkaðu myndir og texta með multi-level zoom til að sjá síðuna eins og þér hentar best í þínu námi.



Fleiri góðir kostir
- Þú getur prentað síður úr bókinni (innan þeirra marka sem útgefandinn setur)
- Möguleiki á tengingu við annað stafrænt og gagnvirkt efni, svo sem myndbönd eða spurningar úr efninu
- Auðvelt að afrita og líma efni/texta fyrir t.d. heimaverkefni eða ritgerðir
- Styður tækni sem hjálpar nemendum með sjón- eða heyrnarskerðingu