Think Data Structures - Algorithms and Information Retrieval in Java

by Allen B. Downey

Read here Read at LibreTextsPDF

This book is intended for college students in computer science and related fields, as well as professional software engineers, people training in software engineering, and people preparing for technical interviews.

Description from LibreTexts.

Publisher
Olin College
Subjects
Engineering, Computer Science
Licence
CC BY-NC-SA 3.0, as LibreTexts states it. Non-commercial use only.
Who can read
Tweens profiles and older, judged from its title and subjects

Contents

LibreTexts writes equations in TeX, and here they show as TeX; the PDF has them typeset.

  1. Front Matter
  2. TitlePage
  3. InfoPage
  4. Table of Contents
  5. Licensing
  6. Preface
  7. Prerequisites
  8. 1: Interfaces
  9. 1.1: Why are there two kinds of List?
  10. 1.2: Interfaces in Java
  11. 1.3: The List Interface
  12. 1.4: Exercise 1
  13. 2: Analysis of Algorithms
  14. 2.1: Selection Sort
  15. 2.2: Big O notation
  16. 2.3: Exercise 2
  17. 3: ArrayList
  18. 3.1: Classifying MyArrayList methods
  19. 3.2: Classifying add
  20. 3.3: Problem Size
  21. 3.4: Linked Data Structures
  22. 3.5: Exercise 3
  23. 3.6: A note on garbage collection
  24. 4: LinkedList
  25. 4.1: Classifying MyLinkedList methods
  26. 4.2: Comparing MyArrayList and MyLinkedList
  27. 4.3: Profiling
  28. 4.4: Interpreting results
  29. 4.5: Exercise 4
  30. 5: Doubly-linked list
  31. 5.1: Performance profiling results
  32. 5.2: Profiling LinkedList methods
  33. 5.3: Adding to the end of a LinkedList
  34. 5.4: Doubly-linked list
  35. 5.5: Choosing a Structure
  36. 6: Tree traversal
  37. 6.1: Search engines
  38. 6.2: Parsing HTML
  39. 6.3: Using jsoup
  40. 6.4: Iterating through the DOM
  41. 6.5: Depth-first search
  42. 6.6: Stacks in Java
  43. 6.7: Iterative DFS
  44. 7: Getting to Philosophy
  45. 7.1: Getting started
  46. 7.2: Iterables and Iterators
  47. 7.3: WikiFetcher
  48. 7.4: Exercise 5
  49. 8: Indexer
  50. 8.1: Data structure selection
  51. 8.2: TermCounter
  52. 8.3: Exercise 6
  53. 9: The Map interface
  54. 9.1: Implementing MyLinearMap
  55. 9.2: Exercise 7
  56. 9.3: Analyzing MyLinearMap
  57. 10: Hashing
  58. 10.1: Hashing
  59. 10.2: How does hashing work?
  60. 10.3: Hashing and mutation
  61. 10.4: Exercise 8
  62. 11: HashMap
  63. 11.1: Exercise 9
  64. 11.2: Analyzing MyHashMap
  65. 11.3: The tradeoffs
  66. 11.4: Profiling MyHashMap
  67. 11.5: Fixing MyHashMap
  68. 11.6: UML class diagrams
  69. 12: TreeMap
  70. 12.1: What’s wrong with hashing?
  71. 12.2: Binary search tree
  72. 12.3: Exercise 10
  73. 12.4: Implementing a TreeMap
  74. 13: Binary search tree
  75. 13.1: A simple MyTreeMap
  76. 13.2: Searching for values
  77. 13.3: Implementing put
  78. 13.4: In-order traversal
  79. 13.5: The logarithmic methods
  80. 13.6: Self-balancing trees
  81. 13.7: One more exercise
  82. 14: Persistence
  83. 14.1: Redis
  84. 14.2: Redis clients and servers
  85. 14.3: Making a Redis-backed index
  86. 14.4: Redis data types
  87. 14.5: Exercise 11
  88. 14.6: More suggestions if you want them
  89. 14.7: A few design hints
  90. 15: Crawling Wikipedia
  91. 15.1: The Redis-backed indexer
  92. 15.2: Analysis of lookup
  93. 15.3: Analysis of indexing
  94. 15.4: Graph traversal
  95. 15.5: Exercise 12
  96. 16: Boolean search
  97. 16.1: Crawler solution
  98. 16.2: Information retrieval
  99. 16.3: Boolean search
  100. 16.4: Exercise 13
  101. 16.5: Comparable and Comparator
  102. 16.6: Extensions
  103. 17: Sorting
  104. 17.1: Insertion sort
  105. 17.2: Exercise 14
  106. 17.3: Analysis of merge sort
  107. 17.4: Radix sort
  108. 17.5: Heap sort
  109. 17.6: Bounded heap
  110. 17.7: Space complexity
  111. Back Matter
  112. Index
  113. Glossary
  114. Detailed Licensing