473,551 Members | 2,797 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Questions on Using Python to Teach Data Structures and Algorithms

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 3743
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
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
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
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
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
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
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.

</F>

Sep 28 '06 #8

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
On 9/28/06, Fredrik Lundh <fr*****@python ware.comwrote:
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.
OK, point taken. But having that shown explicitly in a (variety of)
traditional-looking DSA textbooks would be great. (And for some of us,
it might provide a conforting: "oh man, see how easy it is now with
Python"). After all, I think DSA classes are standard in CS
curricula. And what does the budding Python programmer answer to his
Pascal friend when he says "look, here is my linked list"?

Best,

R.
>
</F>

--
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

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

54
17344
by: Spammay Blockay | last post by:
I've been tasked with doing technical interviews at my company, and I have generally ask a range of OO, Java, and "good programming technique" concepts. However, one of my favorite exercises I give interviewees seems to trip them up all the time, and I wonder if I'm being too much of a hardass... it seems easy enough to ME, but these guys,...
226
12327
by: Stephen C. Waterbury | last post by:
This seems like it ought to work, according to the description of reduce(), but it doesn't. Is this a bug, or am I missing something? Python 2.3.2 (#1, Oct 20 2003, 01:04:35) on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> d1 = {'a':1} >>> d2 = {'b':2} >>> d3 = {'c':3}
137
6982
by: Philippe C. Martin | last post by:
I apologize in advance for launching this post but I might get enlightment somehow (PS: I am _very_ agnostic ;-). - 1) I do not consider my intelligence/education above average - 2) I am very pragmatic - 3) I usually move forward when I get the gut feeling I am correct - 4) Most likely because of 1), I usually do not manage to fully explain...
71
5839
by: cj | last post by:
Dear friends, I have one more questions for everyone in the newsgroup: I am preparing for an interview on UNIX/C++. Could you please identify some of the most important questions which might be asked, so that I could best prepare for it? Thank you, C++J
53
4309
by: Michael Tobis | last post by:
Someone asked me to write a brief essay regarding the value-add proposition for Python in the Fortran community. Slightly modified to remove a few climatology-related specifics, here it is. I would welcome comments and corrections, and would be happy to contribute some version of this to the Python website if it is of interest. ===
29
16467
by: 63q2o4i02 | last post by:
Hi, I'm interested in using python to start writing a CAD program for electrical design. I just got done reading Steven Rubin's book, I've used "real" EDA tools, and I have an MSEE, so I know what I *want* at the end of this; I just have never taken on a programming task of this magnitude. I've seen that some are using python as a utility...
2
454
by: efrat | last post by:
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, then is the complexity Theta(n)? If this is O(1), then why was the name "list" chosen? If...
6
3466
by: Bob Palank | last post by:
I'm considering using VJ# in a first programming course in addition to or in place of JBuilder and the J2SE. Given install problems other students have had, VJ# seems like a nice alternative. I expect criticism. But: 1. Most of my students are using WinXP. 2. VJ#.Net Express is free and has an outstanding GUI. 3. Code written in VJ#, via...
0
239
by: David | last post by:
You're welcome. executemany is probably a good idea here. If memory becomes a problem at some point (eg: millions of lines) you'll probably want to use an on-disk database (I suggest postgresql), and read in batches of say 1000, which you save to the database with a single executemany. It sounds like your Python code has some serious...
0
7565
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7492
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7768
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
1
7522
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
1
5406
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5130
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3520
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
1981
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
0
804
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.