CSCI 430: Algorithm Design and Analysis
Fall 2018

Course Assignments




Note: Homework will be assigned regularly. I will try to keep this page up to date, but homework should otherwise be announced in class. If you miss class and the day's homework has not been posted, please make sure to contact your professor so you don't miss anything.


Note About Assignments: Creating Better Looking Documents: Typesetting with LaTeX and graphviz

Note from the syllabus that the required typesetting toolchain for class consists of LaTeX (pdflatex) and Graphviz. Please see the resources page for information about getting up and running, and for initial typesetting instructions. All of the above should work immediately in the UD Lab (recommended) for those of you who do not wish to support the above on your own systems.

It is my very strong recommendation that you start working on assignments in the lab in order to get comfortable with their use before attempting your own install.

Homework Assignments

Homework 1:

Chapter 2.1: 2.1-1 through 2.1-4
Assigned: 09/04
Due: 09/11 09/14

Note: In your github repo please create the following directories:
  • homework/1 - contents of this homework.
    • Should also contain a typeset pdf of your assignment.
  • homework/1/source - any source files used to create your pdf (e.g., .tex, images, etc.).
    • Do not upload any LaTeX temporaries (e.g., .aux, .log, etc.) or other non-source files.
You can use the above directory structure as a template for future assignments.

Homework 2:

Chapter 2.2: 2.2-1 through 2.2-3
Chapter 2 Problems*: 2-2abcd
Assigned: 09/14
Due: 09/21

*Problems can be found at the end of the chapters to summarize the whole chapter. These can be found under the "Problems" heading after section 2.3 (bottom of page 39).

Homework 3:

Chapter 2.3: 2.3-3 through 2.3-6
Chapter 2 Problems: 2-1ab
Chapter 3.1: 3.1-1, 3.1-4, 3.1-7
Assigned: 10/04
Due: 10/12

Homework 4:

Chapter 3.2: 3.2-1, 3.2-2
Chapter 3 Problems: 3-2, 3-4
Chapter 4.1: 4.1-1, 4.1-2
Assigned: 10/22
Due: 10/31

Homework 5

Chapter 4.3: Exercises 4.3-1 through 4.3-3
Chapter 4.5: Exercises 4.5-1, 4.5-3
  • Chapter 4.3: Please use the substitution method from class to derive a Θ bound.
  • Show all your work. You don't need to prove the bound, just derive it.
  • Chapter 4.5: Use the master method as instructed (identify all figures, argue conclusions by the master method)
Non-Chapter: Use the tabular method ("subtract and guess") to solve
  • Try g(n) = 1 - f(n).
Assigned: 11/08
Due: 11/15 (via github)

Homework 6:

Chapter 6.1: Exercises 1-1, 1-3 through 1-5
Chapter 6.2: Exercises 2-1, 2-3, 2-6
Chapter 6.4: Exercises 4-2
Assigned: 11/19
Due: 11/26 (via github)

Programming Assignments

Program 1: Insertion and Merge Sort

Goals:
  • Implement the text's algorithm for Insertion Sort.
  • Implement the text's algorithm for Merge Sort.
  • Chart/graph the results of experimentation in a spreadsheet.
  • Describe the results of your experimentation.
First, in your repo create the following directory structure:
  • sort
    • insertion - implementation files/test scripts here
      • test - output of trials here*
    • merge - implementation files/test scripts here
      • test - output of trials here*

*Please commit a dummy file here (e.g., a README). You should not commit your test results because they may take up a bit of space and can be generated on my end.

Note: You may use whatever language you want as long as it is supported on the lab machines. I am using Python3 as the example, but just change the extension to an appropriate choice if you do not wish to use Python.

What you should implement:

  • Algorithm files (algorithms only, but if you use Python you can set up a "__main__" for testing purposes):
    • insertion.py - contains the algorithm implementation
    • merge.py - contains the algorithm implementation
  • Test programs:
    • ordered.py - tests over ordered data (i.e., [1, 2, ..., n]
    • backward.py (i.e., [n, n-1, ..., 2, 1])
    • random.py (i.e., generated by rand() or randint()

    Your test programs should take a single command line parameter n. Your program should then randomly generate n integers in the range 0..1,000,000.

    Your test files should also output (1) the original array and (2) the sorted array to stdout, which can be redirected to a file in your Bash script.

  • Bash scripts to automate testing:
    • e.g., ordered.sh, backward.sh, random.sh

You may use the following to get you started:
  • A sample bash script that expects a program called insertion_sort.py and generates test results. You can run this with:
    bash filename.bash
  • A sample spreadsheet to organize your results. (Please put in the sort directory.) You should include tables/graphs of at least the following results:
    • One table and accompanying graph associated with each algorithm.
    • Three additional tables/graphs that compare the best, worst, and average cases across algorithms.
  • A sample report on your results (Please put in the sort directory.)

The idea is that you should generate sufficient test results to see whether the plots of your data match your expectations of the associated functions. (Feel free to take the experiments as far as you need past my starting point to see what happens.)

Assigned: 09/14
Due: 09/21 at 11:59 p.m.

Program 2

Building on the previous results, add new directories, source files, and tests for the following algorithms:
  • selection sort
  • bubble sort
Please make sure to add the following:
  • Add a new report: report2.txt (or pdf) (in your sort directory).
  • Augment your previous spreadsheet to accommodate the new results. (Include a graph of your random, sorted, and reversed data for each algorithm and add to your best, worst, and average case graphs that compare all algorithms.)
Implement the text's algorithm for the Max Subarray problem.
  • Add a new toplevel directory called max to store your results.
  • Add new test cases where n random values are timed for various values of n. (Experiment to determine the range/step for yourself.)
  • Include a new spreadsheet in this directory documenting your results as well as a new report.
Assigned: 10/22
Due: 11/02

Program 3

Implement the text's algorithm for Heapsort, Quicksort, and (randomized) Quicksort.
Add them to your xlsx sheets (try to consolidate into one file for sorting), and add a new report. Draw a conclusion about the best sorting algorithms so far.
Assigned: 11/19
Due: 11/28