George Herriman's Krazy Kat is lounging under an umbrella.

Discrete Structures and Analysis of Algorithms

Math 4/5380-001

Homework for Fall 2016

Due Aug 25.
Get access to Python 3 somehow.
Due Aug 30.
Go to Non-Programmer's Tutorial for Python 3 and work through the following sections.
Your understanding of this material will be examined in class.
Due Sep 1.
Write a function that will take a list as input and print out the sorted list. Save this function to the file "hw0901_name.py" where name is your last name. Use this function to print out the sorted letters in your full name.
Submit your work via an email with two attachments:
- The above file "hw0901_name.py"
- A screenshot of your session that displayed the sorted letters of your name.
Due Sep 6.
Go to Non-Programmer's Tutorial for Python 3 and work through the following sections.
Your understanding of this material will be examined in class.
Due Sep 8.
1. Write python functions that implement Algorithm 3.1 (call this function BFS) and Algorithm 3.2 (call this function DFS) from the text. Assume that the input graph G will be represented as an adjacency list. The output D should be a list of distances, while the output T should be a directed edge list.
  Your functions should use the Stack and Queue classes found in the queue.py file.
  Send me an electronic version of the file containing your functions.
2. Represent the Petersen graph with an adjacency list, and apply both of your functions to this graph.
  Send me a screenshot of a session where you run your functions on the Petersen graph. In this session you should display the input and the outputs.
3. Do your results agree with those shown in Figure 3.9 of the text?
Due Sep 15.
This assignment concerns the implementation of Dijkstra's algorithm that was given to you in class.
1. Save that python code to a file named 'dijkstra.py'.
2. Make the following changes to this 'dijkstra.py' file.
  1. Change the line
```
    from random import random,randint
```
    (found near the top of the file) to the two lines
```
    from random import random,randint,seed
    import csv  
```
  2. Change the line at the end of the 'dijkstra' function from
```
        return D,P
```
    to
```
        return D,P,n,e,count
```
  3. Add the following code to the end of the file:
```
    def test_dijkstra(output_file='test.csv'):
        output_data = []
        for prob in range(6):
            prob *= .2
            prob = round(prob,1)
            for k in range(3,7):
                n = 2**k
                for i in range(10):
                    G = digraph(n,p=prob)
                    d,p,n,e,c = dijkstra(G,0)
                    output_data.append((prob,n,e,c))
        headers = ['probability','vertices','edges','count']
        output_data.insert(0,headers)
    
        csv_writer = csv.writer(open(output_file,'w'))
        csv_writer.writerows(output_data)
    
        return output_data 
```
3. Using IDLE, open and run this file, then from within the python console run the commands:
```
    seed('one')
    G=digraph(10)
    dijkstra(G,0)
```
  Save the results of running these commands in a file 'trial_run.txt'.
4. Now run the command
```
test_dijkstra()
```
  This should create a file 'test.csv' in the same folder as your 'dijkstra.py' file. (A large amount of text will scroll by when you execute the command. Ignore it, and please do NOT send it to me.)
5. Analyze the 'dijkstra' algorithm in the 'dijkstra.py' file and determine a bound for the worst case run time for this algorithm on a graph G in terms of the number of vertices and the number of edges of G. Try to make the bound as tight as possible.
6. Looking at the data in 'test.csv' (using excel or some other spreadsheet software) how close was your bound from problem (5) to the experimental data.
7. Send me the files 'dijkstra.py', 'trial_run.txt', and 'test.csv' along with your analysis from problems (5) and (6).
Due Sep 27.
Do the five problems on the first page of heap homework.
Due Oct 21.
Do the four problems on the sheet binary tree homework.

Back to syllabus or home page.