CSCI 430: Algorithm Design and Analysis
Fall 2017

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 1.1: 1.1-1 through 1.1-5
Chapter 1.2: 1.2-1 through 1.2-3
Assigned: 08/29
Due: 09/05

Homework 2:

Chapter 2.1: 2.1-1 through 2.1-4
Assigned: 08/31
Due: 09/07

Homework 3:

Chapter 2.2: 2.2-1 through 2.2-3
Assigned: 09/05
Due: 09/12

Homework 4:

Chapter 2.3: Exercises 2.3-3 through 2.3-6, Problems 2-1ab, 2-2abcd
Assigned: 09/20
Due: 10/01 (via github)

Homework 5:

Chapter 3.1: Exercises 3.1-1 through 3.1-4, 3.1-6 and 3.1-7
Chapter 3.2: Exercises 3.2-1 through 3.2-3, 3.2-6, Problems 3-1, 3-2, 3-4
Assigned: 09/28
Due: 10/05 (via github)

Homework 6:

Chapter 4.1: Exercises 4.1-1, 4.1-2, 4.1-4
Chapter 4.3: Exercises 4.3-1 through 4.3-3
Chapter 4.5: Exercises 4.5-1 through 4.5-3 note:
  • 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.
Non-Chapter: Use the tabular method to solve
  • Try g(n) = 1 - f(n).
Assigned: 10/13
Due: 10/22 (via github)

Homework 7:

Chapter 6.1: Exercises 1-1, 1-3 through 1-5
Chapter 6.2: Exercises 2-1, 2-3, 2-6
Chapter 6.3: Exercises 3-3
Chapter 6.4: Exercises 4-2
Assigned: 10/27
Due: 11/06 (via github)

Homework 8:

Chapter 7.1: Exercises 1-3
Chapter 7.2: Exercises 2-1 through 2-4
Chapter 7.3: Exercises 3-1, 3-2
Chapter 7.4: Exercises 4-2, 4-5
Assigned: 11/10
Due: 11/17 (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.
Compile the results of experimentation in a spreadsheet.
Describe the results of your experimentation in a text file.

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
Implementation specs:
  • Your implementations for insertion and merge sort should both take a command line parameter n. Your program should then randomly generate n integers in the range 0..1000.
  • Each test should have a single associated script with an obvious name (so that I only have to run one thing to get results).
  • The only output on the terminal should be the times of each test (as reported by /usr/bin/time).
  • The original array and the sorted array should be outputted to standard out, which should then be redirected into a file in the test directory.
  • You should have tests of both algorithms under the following circumstances: ordered data, reversed data, random data.
  • You can encode the 6 tests as separate scripts/binaries, or as a single one that is capable of doing all tests (as long as it is only performing one test per run so the output of /usr/bin/time is accurate).
You may use the following files to get you started:
  • A sample bash script that expects a program called insertion_sort.py, a directory called test where it outputs the results of the tests, and invokes /usr/bin/time to report test results. (Files like this should be located in insertion and merge directories.) Run with bash filename.bash.
  • A sample spreadsheet to organize your results. (Please put in the sort directory.)
  • A sample report on your results (Please put in the sort directory.)
Assigned: 09/07
Due: 09/17 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).
  • Augment your previous spreadsheet to accommodate the new results. Have at least one graphic that compares the four sorting algorithms directly (pick the most reasonable test results per search algorithm).
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: 09/28
Due: 10/11

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: 10/27
Due: 11/10

Program 4 (Optional)

Implement the text's algorithm for Counting Sort.
If you choose to implement Counting Sort, please update your excel report, and add it to your sorting directory as you otherwise would.

If your submission is satisfactory you will earn +3 points on your lowest programming assignment grade.

Assigned: 12/01
Due: TBA

Program 5 (Optional)

Implement DPLL. Your submission will take two forms:
  1. Submit your code in your repo in a new "search" directory.
  2. Verify your code here.
I will explain how to submit verification next week.

Note: Your work should be your own. The above link's plagiarism detection is quite good. Please don't test this.

Assigned: 12/01
Due: TBA