donsheehy / datastructures Goto Github PK

A Literate Program about Data Structures and Object-Oriented Programming

License: MIT License

Python 95.52% Makefile 1.53% Batchfile 0.90% TeX 2.06%

datastructures's Introduction

A Book and a Library

This repository hosts both the book, A First Course on Data Structures in Python and the python package ds2 that is extracted from that book.

The book covers fundamentals of data structures in Python and the library contains fully-tested implementations of the data structures in the book.

The book is a literate program. The code is woven into the text. As such, there are few inline comments. The comments are the book. Moreover, the code files are automatically generated from the markdown files that define the book.

A First Course on Data Structures in Python

by Don Sheehy

Overview

This book is designed to cover a lot of ground quickly, without taking shortcuts.

What does that mean? It means that concepts are motivated and start with simple examples. The ideas follow the problems. The abstractions follow the concrete instances.

What does it not mean? The book is not meant to be comprehensive, covering all of data structures, nor is it a complete introduction to all the details of python. Introducing the minimum necessary knowledge to make interesting programs and learn useful concepts is not taking shortcuts, it's just being directed.

There are many books that will teach idiomatic python programming, and many others that will teach problem solving, data structures, or algorithms. There are many books for learning design patterns, testing, and many of the other important practices of software engineering. The aim of this book is cover many of these topics as part of an integrated course.

Towards that aim, the organization is both simple and complex. The simple part is that the overall sequencing of the main topics is motivated by the data structuring problems, as is evident from the chapter titles. The complex part is that many other concepts including problem solving strategies, more advanced python, object-oriented design principles, and testing methodologies are introduced bit by bit throughout the text in a logical, incremental way.

As a result, the book is not meant to be a reference. It is meant to be worked through from beginning to end. Many topics dear to my heart were left out to make it possible to work through the whole book in a single semester course.

The full book as a pdf can be found here.

datastructures's People

Contributors

Stargazers

Watchers

datastructures's Issues

Question about a design pattern in Chapter 18

Maybe not the best forum to ask this, but I have a question about this part in the AVL tree section:

def put(self, key, value):
    newroot = BalancedBSTNode.put(self, key, value)
    update(newroot)
    return newroot.rebalance()

I've never seen this design pattern before... is this called something? Like "recursive inheritance"? I think it's awesome and also a little mind bending. I would have never thought about extending recursive methods like this...

Taking PR's for fixing typos?

I noticed a typo in 02_oop.md where diner should be dunder

DisjointSetsPathCompression possible bug

This line of code:

item, self._parent[item] = parent, self._parent[parent]

The problem is this:

parents = [1, 2, 2]
item = 0
parent = parents[item]
item, parents[item] = parent, parents[parent]
print(parents)

prints [1, 2, 2]

But 0's parent should be 2 now.

If you separate them out and do:

parents = [1, 2, 2]
item = 0
parent = parents[item]
parents[item] = parents[parent]
item = parent
print(parents)

This correctly prints [2, 2, 2].

This seems like some complex order of operations issue with multiple assignment in python. I'm using 3.8.8.

issue in chapter 17 binary search trees

as it is mentioned in the book that "the line in the put method that updates the root." and "As methods may rearrange the tree structure, such methods return the node that ought to be the new root of the subtree." but there is no return statement in the put method in the BSTNode class, so every even time when the put method is called it is updating the root which looses the references of the nodes inserted before. to solve that i tried removing the update statement instead just call the put method this solved the issue for me.

secondsmallest() in 11_selection.md is broken

For example:

>>> def secondsmallest(L):
...     a, b = None, None
...     for item in L:
...         if a is None or item <= b:
...             a, b = item, a
...         elif b is None or item <= a:
...             b = item
...     return b
>>> secondsmallest([4, 5, 1, 2, 3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in secondsmallest
TypeError: '<=' not supported between instances of 'int' and 'NoneType'

secondsmallest() does not account for when the second element in L is larger than the first element.

donsheehy / datastructures Goto Github PK

datastructures's Introduction

A Book and a Library

A First Course on Data Structures in Python

by Don Sheehy

Overview

The full book as a pdf can be found here.

datastructures's People

Contributors

Stargazers

Watchers

Forkers

datastructures's Issues

Question about a design pattern in Chapter 18

Taking PR's for fixing typos?

DisjointSetsPathCompression possible bug

issue in chapter 17 binary search trees

secondsmallest() in 11_selection.md is broken

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent