CSIS 430 · Assignments

CSIS 430 Assignments

Assignments are due on the specified date 5 minutes before midnight.

Generally, work will be submitted electronically by:

GitLab

For each assignment, you will have a corresponding repository in your GitLab account. Add your code or report to the repository. Generally for programming assignments, there should be at least one empty file to add your code to. The README.MD in the repository may provide additional instructions.

To turn in your assignment, create an issue on the repository. The title of the issue must be set to the game given by the assignment. Next, apply the Submit label to the issue and assign the issue to yourself. Make sure to check the box for a confidential issue.

Around midnight, my automatic grading system will pull your code and test it. If your program passes all the tests, both for design and functionality, your program will be marked with a Passed label. If so, you are done with the assignment. If not, you will have to resubmit your assignment by making changes to fix the problem(s) and then reapply the Submit label. You will have one attempt per day at passing each assignment. Finally, you are expected to make at least one reasonable attempt before the "due" date.

New assignments are added as the semester progresses. Check back often.

Weekly

Engineering Your Soul (EYS)
Read the assigned reading and participate as directed on the course syllabus page.

Due 1/23

Analysis 1: Set
Complete the Set class in Go by finding an efficient data structure to use to construct it. You will need to finish the following methods:

NewSet
Equal
UnEqual
Len
Add
Extend
Delete
Remove
ToArray
Contains
Intersect
Union
Difference
Subsets

The starter code has comments that describe how each method should behave. The Subsets method is a bit more complicated, so I have provided pseudocode for it. Make sure to not alter the method signatures. Also answer the question in the repository's README.md file. You will want to make your own test file, an example is in the repository.

Submit your assignment with the issue label set.

Due 1/30

Analysis 2: Find Minimum
Create an algorithm in Go that finds and returns the minimum value in an unsorted array of int using a Divide and Conquer strategy. Note, you may not simply call merge sort then pick the first value.

Express the time complexity of the algorithm you created as a recurrence equation. Using the Master Theorem give the closed-form solution for the complexity.

Submit your assignment with the issue label min.

Due 2/6

Analysis 3: Sorting & Benchmark
Implement and test the following three sorting algorithms :

Recursive version of Quicksort
Non-recursive version of Quicksort
Iterative version of Insertion Sort

Write a test harness (i.e., main() or a Go unit test to benchmark the three sorting algorithms and the built-in Go sorting algorithm. Go's sorting algorithm is in a method named sort.Ints. It is also a variation of MergeSort. Compare the four algorithms by creating random arrays of increasing size and plot the results. You will need to determine reasonable sizes for the arrays. Also, note that you may need to run the experiments multiple times and average the sort times to get reasonable results.
In your analysis include two graphs of your testing results - one containing all four methods and another that omits insertionSort (be careful with your axis). Discuss of whether the results match your expectations. Do the algorithms reflect their purported average-case complexity? How did your implementations compare to Go's built-in implementation? Your discussion should be several paragraphs in length. Commit your graphs to your repository and make sure to include them in your README.md by using markdown.

Submit your assignment with the issue label sort.

Due 2/11

Program 1: Graph
Implement the Graph class. Note add comments and documentation to your Graph class see more here. Also make sure to commit your code to the graph branch of the graph repository.

Submit your assignment with the issue label graph.

Due 2/20

Program 2: Dijkstra
Implement Dijkstra's Algorithm. Also make sure to commit your code to the dijkstra branch of the graph repository.

Submit your assignment with the issue label dijkstra.

Due 2/27

Analysis 4: Scaling

Suppose you have a computer that requires 1 minute to solve problem instances of size n=1000. Suppose your new computer runs 1000 times faster. What instance sizes can be run in 1 minute, assuming the following time complexities T(n) for the problem? (hint: represent 1000 in the same way as the right hand side of the equation)
1. T(n) = n
2. T(n) = n³
3. T(n) = 10ⁿ
What is the major implication of the results of the previous question? That is, are faster computers a solution to the problem of algorithmic complexity? Explain.

Submit your assignment with the issue label scaling.

Due 2/27

Analysis 5: Dijkstra's Limit & NP-Completeness

Suppose we have a directed, weighted graph given by the following list of edges:
[ (A, B, 1), (A, D, 9), (B, C, 1), (D, B, -20) ]
Give a step-by-step description of how Dijkstra's algorithm proceeds (and fails!) on this graph to find shortest paths from A.
Prove/justify why the longest path problem cannot be solved efficiently/greedily in general.

Submit your assignment with the issue label limit.

Due 3/6

Program 3: Spanning Tree
Implement a Minimal Spanning Tree algorithm. Also make sure to commit your code to the mst branch of the graph repository.

Submit your assignment with the issue label mst.

Due 3/13

Program 4: Greedy TSP: 2-Opt
Implement this greedy algorithm to approximately solve the TSP.

Submit your assignment with the issue label 2opt.

Due 3/20

Program 5: Dynamic Programming TSP: Held-Karp
Implement the Held-Karp algorithm for solving the TSP

Submit your assignment with the issue label dyn.

Due 12/17

Analysis 6: Little Timmy's Reading Plan
Little Timmy's mom promises to take him to the Enchanted Forest if he reads enough during the summer. She gives him points for the reading level of each book he finishes. For example a 1st grade reading level book gives him 1 point, while a second grade reading level book gives him 2, etc. Little Timmy does not get points for partly completed books and he can only read one book at a time. Of course the time it takes Little Timmy to read is based directly on the book's length. Naturally, Little Timmy has asked you to provide an algorithm to determine the books that will maximize his total number of points for the summer so he is guaranteed to go to the Enchanted Forest.

Find a greedy algorithm that solves Little Timmy's problem and provide pseudo-code for it. Also, write a justification, one or two paragraphs, of why your algorithm will or will not find the optimal assignment. Provide examples or counter-examples for position. Note: you can assume the amount of time Little Timmy has available to read is given as an argument to your algorithm along with a list of books. Each book has a reading level and the amount of time it will take to read it.

Due 4/3

Program 6: Randomized TSP: Genetic Algorithm
Implement a genetic algorithm to solve the TSP

Submit your assignment with the issue label genetic.

Due 4/3

Analysis 7: Genetic Algorithm
Evaluation of your implementation of the TSP algorithm. Specifically, run your algorithm over the files EIL101 and KROA100 from the TSP repository. Compare your results to those reported by Tao and Michalewicz in Table 1. For your analysis you may instrument your code with additional output that logs the number of inversions and iterations; remove any logging code from code you submit. Note that the processing time is not relevant since we're using very different hardware, programming languages and graph representations. But we can compare the number of inversions, iterations, and proximity to the optimal path.

Make a table comparing your results with the relevant values from the original paper. Discuss the similarities and differences.

Submit your assignment with the issue label benchmark.

Due 4/17

Program 7: Branch & Bound TSP
Implement the branch and bound algorithm for the TSP.

Submit your assignment with the issue label branch.

Due 4/17

Analysis 8: The Grand Finale
Evaluate your branch & bound algorithm and all of the TSP algorithms on the following TSP files. Make a table of the run times and path lengths discovered by each method on each graph. Describe the results table and explain what you expected versus what you observed. Note that your implementation of branch & bound or other algorithms may not be able handle the larger graphs. Run the algorithms on as many of these graphs as you can, but limit the time per graph to an hour.

Submit your assignment with the issue label finale.

Assigned	Due Date	Assignment
Weekly	See schedule	Engineering Your Soul (EYS) Read the assigned reading and participate as directed on the course syllabus page.
1/13	1/23	Analysis 1: Set Complete the `Set` class in Go by finding an efficient data structure to use to construct it. You will need to finish the following methods: NewSet Equal UnEqual Len Add Extend Delete Remove ToArray Contains Intersect Union Difference Subsets The starter code has comments that describe how each method should behave. The `Subsets` method is a bit more complicated, so I have provided pseudocode for it. Make sure to not alter the method signatures. Also answer the question in the repository's `README.md` file. You will want to make your own test file, an example is in the repository. Submit your assignment with the issue label `set`.
1/23	1/30	Analysis 2: Find Minimum Create an algorithm in Go that finds and returns the minimum value in an unsorted array of `int` using a Divide and Conquer strategy. Note, you may not simply call merge sort then pick the first value. Express the time complexity of the algorithm you created as a recurrence equation. Using the Master Theorem give the closed-form solution for the complexity. Submit your assignment with the issue label `min`.
1/30	2/6	Analysis 3: Sorting & Benchmark Implement and test the following three sorting algorithms : Recursive version of Quicksort Non-recursive version of Quicksort Iterative version of Insertion Sort Write a test harness (i.e., `main()` or a Go unit test to benchmark the three sorting algorithms and the built-in Go sorting algorithm. Go's sorting algorithm is in a method named `sort.Ints`. It is also a variation of MergeSort. Compare the four algorithms by creating random arrays of increasing size and plot the results. You will need to determine reasonable sizes for the arrays. Also, note that you may need to run the experiments multiple times and average the sort times to get reasonable results. In your analysis include two graphs of your testing results - one containing all four methods and another that omits `insertionSort` (be careful with your axis). Discuss of whether the results match your expectations. Do the algorithms reflect their purported average-case complexity? How did your implementations compare to Go's built-in implementation? Your discussion should be several paragraphs in length. Commit your graphs to your repository and make sure to include them in your README.md by using markdown. Submit your assignment with the issue label `sort`.
2/5	2/11	Program 1: Graph Implement the Graph class. Note add comments and documentation to your Graph class see more here. Also make sure to commit your code to the `graph` branch of the `graph` repository. Submit your assignment with the issue label `graph`.
2/11	2/20	Program 2: Dijkstra Implement Dijkstra's Algorithm. Also make sure to commit your code to the `dijkstra` branch of the `graph` repository. Submit your assignment with the issue label `dijkstra`.
2/20	2/27	Analysis 4: Scaling Suppose you have a computer that requires 1 minute to solve problem instances of size n=1000. Suppose your new computer runs 1000 times faster. What instance sizes can be run in 1 minute, assuming the following time complexities T(n) for the problem? (hint: represent 1000 in the same way as the right hand side of the equation) T(n) = n T(n) = n³ T(n) = 10ⁿ What is the major implication of the results of the previous question? That is, are faster computers a solution to the problem of algorithmic complexity? Explain. Submit your assignment with the issue label `scaling`.
2/20	2/27	Analysis 5: Dijkstra's Limit & NP-Completeness Suppose we have a directed, weighted graph given by the following list of edges: `[ (A, B, 1), (A, D, 9), (B, C, 1), (D, B, -20) ]` Give a step-by-step description of how Dijkstra's algorithm proceeds (and fails!) on this graph to find shortest paths from `A`. Prove/justify why the longest path problem cannot be solved efficiently/greedily in general. Submit your assignment with the issue label `limit`.
2/27	3/6	Program 3: Spanning Tree Implement a Minimal Spanning Tree algorithm. Also make sure to commit your code to the `mst` branch of the `graph` repository. Submit your assignment with the issue label `mst`.
3/6	3/13	Program 4: Greedy TSP: 2-Opt Implement this greedy algorithm to approximately solve the TSP. Submit your assignment with the issue label `2opt`.
3/13	3/20	Program 5: Dynamic Programming TSP: Held-Karp Implement the Held-Karp algorithm for solving the TSP Submit your assignment with the issue label `dyn`.
12/10	12/17	Analysis 6: Little Timmy's Reading Plan Little Timmy's mom promises to take him to the Enchanted Forest if he reads enough during the summer. She gives him points for the reading level of each book he finishes. For example a 1st grade reading level book gives him 1 point, while a second grade reading level book gives him 2, etc. Little Timmy does not get points for partly completed books and he can only read one book at a time. Of course the time it takes Little Timmy to read is based directly on the book's length. Naturally, Little Timmy has asked you to provide an algorithm to determine the books that will maximize his total number of points for the summer so he is guaranteed to go to the Enchanted Forest. Find a greedy algorithm that solves Little Timmy's problem and provide pseudo-code for it. Also, write a justification, one or two paragraphs, of why your algorithm will or will not find the optimal assignment. Provide examples or counter-examples for position. Note: you can assume the amount of time Little Timmy has available to read is given as an argument to your algorithm along with a list of books. Each book has a reading level and the amount of time it will take to read it.
3/20	4/3	Program 6: Randomized TSP: Genetic Algorithm Implement a genetic algorithm to solve the TSP Submit your assignment with the issue label `genetic`.
3/20	4/3	Analysis 7: Genetic Algorithm Evaluation of your implementation of the TSP algorithm. Specifically, run your algorithm over the files EIL101 and KROA100 from the TSP repository. Compare your results to those reported by Tao and Michalewicz in Table 1. For your analysis you may instrument your code with additional output that logs the number of inversions and iterations; remove any logging code from code you submit. Note that the processing time is not relevant since we're using very different hardware, programming languages and graph representations. But we can compare the number of inversions, iterations, and proximity to the optimal path. Make a table comparing your results with the relevant values from the original paper. Discuss the similarities and differences. Submit your assignment with the issue label `benchmark`.
4/3	4/17	Program 7: Branch & Bound TSP Implement the branch and bound algorithm for the TSP. Submit your assignment with the issue label `branch`.
4/3	4/17	Analysis 8: The Grand Finale Evaluate your branch & bound algorithm and all of the TSP algorithms on the following TSP files. Make a table of the run times and path lengths discovered by each method on each graph. Describe the results table and explain what you expected versus what you observed. Note that your implementation of branch & bound or other algorithms may not be able handle the larger graphs. Run the algorithms on as many of these graphs as you can, but limit the time per graph to an hour. Submit your assignment with the issue label `finale`.

This page was last modified on 2025-04-10 at 22:14:02.

George Fox University · 414 N Meridian St · Newberg, Oregon 97132 · 503-538-8383
Copyright © 2018–2025 George Fox University. All rights reserved.