444,246 Members | 1,515 Online
Need help? Post your question and get tips & solutions from a community of 444,246 IT Pros & Developers. It's quick & easy.

# Questions on Using Python to Teach Data Structures and Algorithms

 P: n/a Hello, 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? If one writes a[n], then is the complexity Theta(n)? If this is O(1), then why was the name "list" chosen? If this is indeed Theta(n), then what alternative should be used? (array does not seem suited for teaching purposes.) 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? (Sorry, but any Google query involving "Python" and "HTML" (with any other additional terms) led to Python HTML processing libraries.) 3. Are there any useful links for Python/DSA education? 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. Python is such a cool language - I'm really hoping the students will enjoy it as much as I do. Once again, many thanks for helping out with this. Thanks, Efrat Sep 27 '06 #1
11 Replies

 P: n/a efrat: >1. What exactly is a Python list? A dynamic array that can grow geometrically on the right. >If one writes a[n], then is the complexity Theta(n)? If this is O(1),< It is O(1). >then why was the name "list" chosen? I'd too love to know why the wrong "list" name was chosen for them, instead of "array". (Maybe because "list" is shorter, or because ABC called them "lists"...) >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?< There are many programs that do this, I use a modified version of PySourceColor: http://bellsouthpwp.net/m/e/mefjr75/ Using Python to teach data structures and algorithms to electrical-engineers students: The following personal ideas may seem wrong, but if they are wrong, than I'd like to know why. I think Python is only partially fit for your purpose. If you want to teach how complex data structures work in general, and some smart algorithms on them, like teaching some interesting graph algorithms, then Python is fit, because implementing such algorithms is often simple, etc. But to manage simple data structures Python isn't good, because it's too much slow compared to the simple operations, and it uses too much memory. One of the basic data structures is the chained list, you can easly implement a chained list in Python, but the result is often useless and without meaning, maybe even for teaching purposes. Python is too much hi-level, while most of the basic data structures use pointers and they have a meaning if done closer to the 'metal'. With Python you can't have pointers (just names of objects) and some times if you use a "fast" data structure you end doing things slower than using the built-in data structures like dicts. So to teach some of the basic data structures to your electrical-engineers students I think Pascal is the best choice still :-) (Note: to teach DSA to CS students C can be fit too, and to teach a bit of DSA to younger people Python can be better.) Bye, bearophile Sep 28 '06 #2

 P: n/a efrat wrote: 1. What exactly is a Python list? If one writes a[n], then is the complexity Theta(n)? If this is O(1), then why was the name "list" chosen? If this is indeed Theta(n), then what alternative should be used? (array does not seem suited for teaching purposes.) Indexing for python lists is O[1]. Why shouldn't they be named lists ? 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? (Sorry, but any Google query involving "Python" and "HTML" (with any other additional terms) led to Python HTML processing libraries.) Check out MoinMoin, it colorizes python as well as other languages and text types: http://moinmoin.wikiwikiweb.de/HelpOnFormatting 3. Are there any useful links for Python/DSA education? 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. "Beginning Python - From Novice to Professional" is approachable and great as a textbook IMO. As a bonus, it covers up to python 2.4, which very few existing books do. George Sep 28 '06 #3

 P: n/a In <45******@news.bezeqint.net>, efrat wrote: 1. What exactly is a Python list? If one writes a[n], then is the complexity Theta(n)? If this is O(1), then why was the name "list" chosen? Why not? It has all the methods one expect from an abstract data type "list". It's not the O() behavior but the interface that defines abstract data types. If it's a (double) linked list or a dynamical array under the hood is an implementation detail. Ciao, Marc 'BlackJack' Rintsch Sep 28 '06 #4

 P: n/a efrat wrote: 1. What exactly is a Python list? If one writes a[n], then is the complexity Theta(n)? If this is O(1), then why was the name "list" chosen? If this is indeed Theta(n), then what alternative should be used? (array does not seem suited for teaching purposes.) A Python list is an array of object references that has some empty slots (or one empty slot?) for growing quickly to the right. If you want to make a chained structure, then perhaps you know LISP? This is what the basic machinery of LISP looks like in Python: def cons(a,b) return [a,b] def car(structure) return structure[0] def cdr(structure) return structure[1] Python lists are more powerful than you would think! You don't need classes or OOP to create linked lists or tree structures in Python. Remember that O(1) is not neccesarily faster than O(N)! Unless your linked list is very big, you will get something called a 'cache miss' inside your CPU. Thus it is usually more efficient to work with dynamic arrays. Further, you can create hybrid array-list structures (e.g. Java's ArrayList) that outperform lists and arrays with respect to adding new elements. But they will have to be tuned to your particular hardware architecture. Growing a linked list node by node is an excercise for fools (and DSA students?) It may look good in DSA textbooks, but it is extremely inefficient on real world computers. Python's lists are implemented as dynamic arrays internally to be efficient on the kind of data we normally work with. Not only do small dynamic arrays grow faster than small lists, they also index much faster. Why are they called "lists" then? Because Guido want you to look at them conceptually as lists. That is what they are. If you want real 'fixed size' arrays like Fortran and Matlab, then you should add 'NumPy' to your Python (http://www.scipy.org). Your science and engineering students will find NumPy, SciPy and Matplotlib (http://matplotlib.sourceforge.net) valuable, so direct them to those sources. Sep 28 '06 #5

 P: n/a be************@lycos.com wrote: efrat: [...] > >>then why was the name "list" chosen? I'd too love to know why the wrong "list" name was chosen for them, instead of "array". (Maybe because "list" is shorter, or because ABC called them "lists"...) I suspect it's because of their intrinsic one-dimensional nature. regards Steve -- Steve Holden +44 150 684 7255 +1 800 494 3119 Holden Web LLC/Ltd http://www.holdenweb.com Skype: holdenweb http://holdenweb.blogspot.com Recent Ramblings http://del.icio.us/steve.holden Sep 28 '06 #6

 P: n/a Going back to the original question, a related question: does anybody know why there are so few books on data structures and algorithms that use Python? I remember that, at least ~ 12 years ago there were many (and very good) books that used Pascal for this topic. So when I did my own search for one in Python (just for my own consumption and enlightnment) and could only find the same one as the original poster of this thread [1], I was very surprised. No publishers have felt the need to fill this gap? Best, R. [1] http://thread.gmane.org/gmane.comp.p...8/focus=486698 "Data Structures and Algorithms with Object Oriented Design Patterns" (http://www.brpreiss.com/books/opus7/html/book.html) and was surprised. -- Ramon Diaz-Uriarte Bioinformatics Unit Spanish National Cancer Centre (CNIO) http://ligarto.org/rdiaz Sep 28 '06 #7

 P: n/a Ramon Diaz-Uriarte wrote: Going back to the original question, a related question: does anybody know why there are so few books on data structures and algorithms that use Python? Probably because Python has "better than textbook" implementations of core structures, and "better than textbook" implementations of many core algorithms, so lots of things can be done more efficiently by combining existing structures and algorithms than by using "textbook" algorithms. Sep 28 '06 #8

 P: n/a sturlamolden wrote: Remember that O(1) is not neccesarily faster than O(N)! Unless your linked list is very big, you will get something called a 'cache miss' inside your CPU. Thus it is usually more efficient to work with dynamic arrays. This was a bit ackwardly formulated. What I was trying to say is that linked lists produces cache misses rather often, whereas small dynamic arrays do not. This is because linked lists are not contigous in memory, in contrast to dynamic arrays. Thus, adding an element to a dynamic array is in most cases faster, even tough you have to make a copy the whole array. The same is true when you try do delete some elements from a list. Small dynamic arrays are faster than linked lists, because they can be kept in cache. Creating a new array in cache is faster than tracing after pointers. It is only when dynamic arrays are to large to fit in cache that linked lists perform better. But in this case, something like Java's ArrayList is the preferred data structure. That is the reason only fools and DSA students use linked lists. They are a nice teoretical cobnstruct, but not friendly to real-world computer hardware. Perhaps they were the better option some time in the past, when CPUs had much less cache and could only accomodate very short arrays. Sep 28 '06 #9

 P: n/a On 9/28/06, Fredrik Lundh -- http://mail.python.org/mailman/listinfo/python-list -- Ramon Diaz-Uriarte Bioinformatics Unit Spanish National Cancer Centre (CNIO) http://ligarto.org/rdiaz Sep 28 '06 #10

 P: n/a efrat wrote: Hello, I'm planning to use Python in order to teach a DSA (data structures and algorithms) course ... Hello, Many thanks, repliers, for the informative and useful answers. Bye, Efrat Sep 29 '06 #11

 P: n/a At Thursday 28/9/2006 12:23, Ramon Diaz-Uriarte wrote: >Going back to the original question, a related question: does anybodyknow why there are so few books on data structures and algorithms thatuse Python?I remember that, at least ~ 12 years ago there were many (and verygood) books that used Pascal for this topic. So when I did my ownsearch for one in Python (just for my own consumption andenlightnment) and could only find the same one as the original posterof this thread [1], I was very surprised. No publishers have felt theneed to fill this gap? Maybe, because with Pascal you got *nothing* more than the bare language, and you had to implement most of the structures and algorithms yourself. (This was by design). Python, on the other hand, comes with "batteries included". What's the point in reimplementing another mapping/dictionary structure using Python, having the built-in dict type which is rather efficient? I would not use Python to teach *basic* data structures, instead, I'd use it as a second stage to teach more complex structures and how to design algorithms. Gabriel Genellina Softlab SRL __________________________________________________ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas Sep 29 '06 #12

### This discussion thread is closed

Replies have been disabled for this discussion.