Questions on Using Python to Teach Data Structures and Algorithms

[Bryan Olson]

efrat wrote:
>   I'm planning to use Python in order to teach a DSA (data structures 
> and algorithms) course in an academic institute. If you could help out 
> with the following questions, I'd sure appreciate it:
> 1. What exactly is a Python list?

It's almost exactly what the doc says (and exactly what the code
implements).

> If one writes a[n], then is the complexity Theta(n)?

No; as others have pointed out, it's O(1).

> If this is O(1), then why was the name "list" chosen?

Because it *is* a list: an ordered collection in which an
element might appear multiple times. It's also an extensible
array, but that's so more verbose.

> If this is indeed Theta(n), then what alternative should be 
> used? (array does not seem suited for teaching purposes.)

It's not Theta(n), and the array classes are fine for teaching.

> 2. Suppose I have some file example.py, and I'd like to incorporate it 
> **into** part of an HTML page with nice syntax highlighting and all the 
> shebang. Is there an easy way to do so?

Yes. In fact its probably easier, or at least no harder, than
making sense of what you mean there.

> (Sorry, but any Google query involving "Python" and "HTML" (with any 
> other additional terms) led to Python HTML processing libraries.)

Don't be sorry about about getting the info you need (whether
or not you realize it is the info you need).

> 3. Are there any useful links for Python/DSA education?

Yes, many. Python is fine for teaching data structures and algorithms.
Python's loosely-defined "duck typing" makes it pedagogically
inappropriate for some topics, but as far as you have described your
course, Python should work well.

> I found "Data 
> Structures and Algorithms with Object Oriented Design Patterns" 
> (http://www.brpreiss.com/books/opus7/html/book.html). It is a fine book, 
> but it is unsuitable: my students are electrical-engineers, and barely 
> know how to program; teaching them DSA, python, **and** stuff like the 
> visitor pattern seems impossible.

When I taught algorithms, I observed that my students arrived lacking
much of the background knowledge I would expect, but they more than
compensated by being so bright. The engineers did about as well as
comp-sci students. We all got blown away by a couple scary-smart math
majors.

You don't need to teach, or know, the visitor pattern. Deal with the
the fundamentals. There are two ways we describe specific computational
problems: output as a function of input, and abstract data type. Python
is great for both.


-- 
--Bryan