Algorithms from Class

Example Algorithms Expressed in Python

These are program examples we have covered in class or are relevant to topics we covered in class. They all use Python to express the algorithm so that they not only explain the algorithm but actually will run. Many algorithms come in more than one form because educational points were being made. Compare algorithms of similar function. All the algorithms together can be found in this compressed tar file: algorithms.tar or this zip file: algorithms.zip. Here the algorithms are presented roughly in the order in which they appeared in class:

Simple Libraries

• glib.py relink(), array(), and some test graphs
• lib.py stacks, queues, 1D array creations
• graphexamples.py

Algorithms

• unique.py are all the elements in the list unique?
• linearIsIn.py look for element in list
• matrixMultiply.py do matrix multiply
• maxelem.py find the largest element

  ---

• euclid-basic.py Euclid's algorithms
• euclid-brute.py
• euclid-m-fail.py
• euclid-m-minus-noswap-fail.py
• euclid-min.py
• euclid-minus-noswap-fail.py
• euclid-minus-swap.py
• euclid-norecurse.py
• euclid-norecurse2.py
• euclid-norecurse3.py

  ---

• numtobin.py number to binary representation in a string
• numtobin2.py
• numtobinFix.py number to binary representation in a string of fixed output size
• numtobinFix2.py
• numtobinFix3.py
• numtobinFix4.py
• numtobinFixCount2.py
• numtobinFixCount3.py

  ---

• sieve-0.py prime number sieve
• sieve-a.py
• sieve-b.py

  ---

• sortbubble.py bubble sort
• sortselect.py selection sort
• sortselect02.py selection sort with

  ---

• strmatchbrute.py string match with length
• strmatchbrute02.py string match using a sentinel

  ---

• closestpoints.py two ways of finding closest pair of points in 2D

  ---

• hanoi.py towers of Hanoi showing number of disks
• hanoi01.py towers of Hanoi showing a list of disks
• hanoi02.py basic towers of Hanoi

  ---

• pow.py linear version of raising to a power
• pow02.py log(n) version of raising to a power

  ---

• graphrepresentations.py some ways to represent graphs
• graphconnected.py is the graph connected
• graphcount.py
• dfs.py depth first search
• bfs.py breadth first search
• bfsdfscompare.py compare bfs and dfs
• graphistree.py is it a tree?
• graphmaketree.py find a spanning tree
• graphrelink.py
• topological.py do a topological sort
• dag.py test if digraph is acyclic

  ---

• partition.py simple partitioning for sorting
• partition2.py better partitioning for sorting
• sortquick.py basic quick sort
• sortquick2.py
• sortquick3.py
• sortquick4.py

  ---

• sortinsert.py insertion sorting
• sortinsert2.py
• sortshell.py Shell sorting
• sortshell2.py
• sortmerge.py merge sorting

  ---

• counting.py brute force counting
• graycode.py using gray code to do minimum change ordered counting

  ---

• countinggray.py least change counting
• countinggraylist.py
• countinglist.py
• countingperm.py least change permutations by counting
• countingperm2.py

  ---

• permlex.py lexigraphic order permuation generation
• permjt.py least change permutation generation

  ---

• traverse.py classic tree traversals

  ---

• heap.py basic heap operations
• sortheap.py heap sort

  ---

• fib.py fibonacci as a very simple dynamic programming example
• coinrow1.py the coin subset problem from the book
• coinrow2.py
• coinrow3.py
• coinchange.py making change with the minimum number of coins
• coinchange2.py

  ---

• symtab.py simple symbol table is available as a dictionary in Python
• symtab2.py
• symtab3.py
• symtab4.py
• symtab5.py
• symtabhash.py a symbol table done using a hash function
• symtabhash2.py

  ---