CSC 532 Schedule

Spring 2012

This is a tentative schedule for CSC 532 and is subject to change without notice elsewhere. Please bookmark it in your browser and refer to it at least weekly during the semester.

Week/Dates

Work

Notes

12 January

1) Basic search and optimizations

a) Enumeration

i) Permutation Generator

(1) Permute

ii) Logic Value Table Generator (LVTG)

(1) Allow an arbitrary number of independent variables

(2) Permit multi-valued, discrete, logic variables

Problem 1

Due: 24 January

Generate a histogram of all solutions and find the basic descriptive statistics (mean, median, mode, maximum, minimum, range, standard deviation, and variance) for a capacitated, weighted assignment problem. How do the statistics of the distribution of solutions compare with a distribution obtained by generating 100,000 compliant, random assignments and noting the cost of each assignment to obtain distribution statistics?

17, 19 January

b) Random

c) Greedy

d) Some examples

i) Resource Allocation

ii) Warehouse Location

iii) Quadratic Assignment

iv) Cost-based Abduction

24, 26 January

Reports of findings

Problem 2

Due: 7 February

Given adjacency table representations for two graphs, create a method that will determine whether or not the corresponding graphs are isomorphic. Here is a file with test data that includes eleven examples of isomorphic graphs and four graph pairs for which the relationship has not been stated. Determine whether the unclassified graph pairs are isomorphic. Contrast the graph isomorphism problem with the concentrator assignment problem. Compare their computational complexities, run times, objectives, the potential and performance of heuristic solutions, programming complexities, and common or similar elements. What are some applications of the graph isomorphism problem? What heuristics were you able to use to facilitate finding solutions?

31 January, 2 February

2) Constraint Satisfaction Problems

a) Satisfiability

b) Graph Isomorphism

c) Knight’s Tour

7, 9 February

3) Discrete Domain Transformations

a) Algoritharium

i) RGB space

ii) HSB space

Problem 3

Due: 21 February

Use the Algoritharium to implement and demonstrate:

1. Color-to-gray-scale conversion. Is this an invertible operation?

2. Convert an image to its negative. Is this an invertible operation?

3. Find and “enhance” boundary contours.

4. Fading from one image to another.

5. Rotating parts of an image.

6. Warping parts of an image.

7. Implement image filters for smoothing and sharpening, as well as removing speckle

8. Use a method, possibly as a “template,” to locate features (such as, eyes in a portrait or heads in a family group photo) automatically.

9. Contrast enhancement (Is this an invertible operation?) and compare the results obtained via the histogram equalization method using:

· RGB space

Find histograms in the red, green, and blue color spaces and use the histograms to remap the RGB levels. Use the remapped values to assign pixel values in a contrast enhanced image. How would you describe the qualitative differences between the original image and the contrast enhanced image?

· HSB space

Transform the RGB values into HSB values (Hue, Saturation, and Brightness) to enhance an image using histogram equalizations over seven subsets HSB values (H, S, or B only, H and S, H and B, S and B, and HSB).

· What qualitative differences do you observe among the resultant images

· How do the images compare with the results obtained by RGB equalization?

10. Some test images:

a. Who

b. Boom

c. Mars face

d. Shoemaker-Levy impact

e. Towers

f. Tanks

14, 16 February

b) Fourier (DFT or FFT)

i) A framework in vector projections

ii) Digital Signal Processing

iii) Image Filtering

21, 23 February

Reports of findings

Problem 4

Due: 17 April

Select a data set from one of the following areas (or similar):

· Physical, climatological or meteorological data

· Audio data

· Stock market data

· RF/Sonar

· Digital imagery

Identify and interpret any spectral behavior indicated by the data.

28 February,

1 March (SIG CSE. No class meeting this date.)

iv) Wavelet (DWT)

6, 8 March

8 March: Mid-term exam

10/

13, 15 March

No classes

Spring Break, 10-18 March

DRAFT VALID TO HERE

6 January 2012

11/

20, 22 March

(Visiting speaker on one date this week.)

4) Encryption/Data Compression

a) Run length encoding

b) Quantization

c) Entropy-based encoding

d) Steganography and paper

12/

27, 29 March

5) Classifying/Clustering

a) Supervised (Bayesian Classification)

b) Unsupervised (C-Means)

13/

3 April

No class 5 April

6) Linear Principal Component Analysis (PCA)

a) Vector and Matrix Arithmetic

b) Covariance

c) Eigenvectors and eigenvalues

14/

10-12 April

7) Finite Difference Modeling

a) Life (John H. Conway)

Problem 5-6

Student selected problem…

Due: 24 April

15/

17, 19 April

8) Markov Models

a) Language generator

b) Shopper’s aid

16/

24, 26 April

Reports of findings

17/

1 May

Reading Day, Tuesday, 1 May

Exams begin 2 May

18/

8 May, Final Exam

CSC 532 Final Exam,

3:00-6:00 PM,

Tuesday, 8 May, CIS 1006

CSC 532-001, Spring 2012 Schedule Ends Here

Errata

Vvvvvvvvvvvvvvvvvvvvvvvvvv

Previous problems

Comparison-based Sorting Reports of findings

Results of previously assigned exercises

AC2

Comparing Sorting Methods

For 30 lists containing 50,000 uniformly distributed and for 30 lists containing 50,000 normally distributed integers in the range [-100,000, 100,000] compare the numbers of comparisons and average run times of:

· Insertion sort;

· Selection sort;

· Bubble sort;

· Quick sort;

· Merge sort;

· Heap sort; and

· Bucket sort.

Knights Tour

A knight’s tour is a sequence of knight’s moves that allow a knight to visit each square on a board exactly once. If the starting square is under attack from the final position of the knight, the tour is said to be closed; otherwise the tour is open. Create a program that will:

· Integers M, N, P, and Q that represent the number of squares per side of an MxN board and a starting location (row P, column Q) for the knight;

· Determine whether or not a knight’s tour exists for a given board and starting location;

· Find all tours from a given starting point; and

· Report any tour that is found, classifying it as open or closed

Traveling Salesperson

Generate a histogram of all solutions and find the basic descriptive statistics (mean, median, mode maximum, minimum, range, standard deviation, and variance) for a 14-city travelling sales-person problem with all cities distributed uniformly randomly within a unit square. How do the statistics of the distribution of solutions compare with a distribution obtained by 100,000 times, randomly riffle shuffling a list of city labels and noting the length of the associated trips to obtain distribution statistics?

Two-set Partition Problem

Create a method that will generate a table of all possible combinations binary logic values {0, 1} for n independent logic variables. Demonstrate the algorithm by determining whether a set A ={ x| 0 < x < 100} of n randomly selected integers contains a subset that sums exactly to an integer value k. 1789. For demonstration purposes, let n = 35 and k = 1789. Be sure to show A and every subset that sums to 1789.

General Set Partitioning

Extend the LVTG method to permit n-ary logic values {0, 1,…, (n-1)}. Demonstrate the algorithm by determining whether there exists a partition of A such that the sums of the elements of A_i differ by no more than a non-negative integer k. For the demonstration, assume n=3 and k=1.