Read Sections 4.3,4.4, 4.5.
Programs done on Jan. 30, 2006, class

PDP, the Partial Digest Program: final version.

PROFILEold3, the very beginning of the Profile algorithm.
Homework for Jan. 30, due Feb. 3:

Finish the Cook procedure.
 Read Sections 4.5, 4.6, 4.7.
Sudoku contest (due Feb. 13 [extended deadline])
Write a Maple program that solves Sudoku problems
on an n**2 time n**2 grid (not just n=3).
$10 price for the fastest running pogram.
Input: a list of lists of size n**2 each of whose
entry is a row of length n**2.
Each entry is eitehr an integer from 1 to 9 and 0
denots blanks.
Output: The SET of solutions (that should be a singleton for
a good puzzle). Each such solution should have no 0s.
Note: Andrew Baxter pointed my attention to the
Sudoku site, where you can create puzzles that
you test your program with.
Optional Suggested Outline:

Write a procedure Options(M,i,j) that inputs a Soduko puzzle (given
as a list of length n**2 of the rows, where each row is a
list of length n**2, and blanks are denoted by 0), and
a location [i,j] (occupied by 0) and outputs the
subset of {1,2,3,4,5,6,7,8,9} that can be
put there without violating the row column and section
condition.
 Write a procdeure Champion(M) that locates a location [i,j]
such that M[i][j]=0 and the size of Option(M,i,j) is
nonempty and as small as possible.
If it can't find it return FAIL.
 Write a procedure Children(M) that finds all the
matrices obtained by replacing the 0 at location [i,j] (the
outout of Champion(M)) by one of the members of Options(M,i,j),
where [i,j] is the Champion. Of course Children(M) may be the
empty set (if one of the Option(M,i,j) sets is empty)
 Write a procedure Descendants(M) that inputs a Soduko
matrix M and outputs the set of all possible solutions
(possibly the empty set). Define it recursively using
Children(M), and if M is legal and has no zeros (blanks)
left it returns {M}.
Added Feb. 2, 2006:
Phillip Matchett Wood kindly found the following
Sudoku Challenge, by which we will compare the contesting programs.
Follow the instructions in that file to generate the output file
with the running time.
Added Feb, 4, 2006: The real test is with four extra problems,
taken from the Yedioth newspaper of Feb. 3, 2006.
To participate in the progarm run the
TestFile.
Your output shuold look like this
OutTestFile, but of course with different timings.
Added Feb. 5, 2006: Arvind Ayyer kindly found
Three more Sudoku puzzles, for you to test your programs.
Added Feb. 6, 2006: Please put your Sudoku Maple program in
the public_html directory of your eden account, as well as
the output file.
ADDED Feb. 13, 2006:
CONGRATULATIONS TO
Bobby Griffin for winning TEN DOLLARS from Dr. Z.
for writing
the fastest Sudoku program
.
Programs done on Jan. 30, 2006, class
PROFILEold2 [so far]
See also
Andrew Baxter's Cook Program.
Homework for Feb. 2, due Feb. 6:

Implement in Maple Procedures NextLeaf, NextVertex,
and Bypass in Section 4.7
 Read Sections 4.7, 4.8, and 4.9
Program done on Feb. 6, 2006, class
Homework for Feb. 6, due Feb. 9:
Finish up
PROFILE by writing a Maple procedure
FindMotif(M,L), that inputs M (a tlist of nlists in
some alphabet), and a positive integer L (L larger than 2),
and outputs the following three items:
 The highest scoring motif (a list of length L)
 The tlist that indicates the locations
 The score (a number between .25 and 1)
Mandatory Homework due Feb. 14
HW2_14 by writing a Maple procedure
Program done on Feb. 9, 2006, class

PROFILE [the Bad part is still buggy]
Homework for Feb. 9, due Feb. 16:
 Debug the Bad programs: ConBad, BestMotifBad etc.
 Using Bypass, write a procedure that skips
hopeless parts of the trees by adding to the partial
score L*(tnops(W))
 Read Chapter 5
 [optional] Implemenet the Median String Approach (section 4.6)
that searches for all possible words of in {1,2,3,4} of
length L and finds the one that best "fits"
and the locations.
 [optional] Do an improved version with Bypass.
Programs done on Feb. 13, 2006, class

FLIP [Flipping pancakes (prefix reversal)]

FLIPa [Sorting by Adjacent Transpositions]

FLIPb [Sorting by Reversals]
Homework for Feb. 13, due Feb. 16:

Write a Maple procedure that inputs a permutation
and outputs a sequence of pairs [i,j] that sorts
it using the FLIPb flippings. Use the naive approach
of the book (looking for the first i that is not equal
to pi[i] and bringing it to the iplace)

Inplement the "clever greedy" algorithm of the book
that finds the [i,j] that minimizes the
number of breakpoints, if possible, or reverses an increasing
block.
Programs done on Feb. 16, 2006, class

ReversalGreedy, The Stupid Greedy Reversal sorting
algorithm.

ReversalClever, The "Clever" Greedy Reversal sorting
algorithm [not provably an algorithm.]
Homework for Feb. 16, due Feb. 23:

Cute Problem from the internet
(communicated to me by the great biophysicist Terrell Hill)

Write another file, ReversalVeryClever, by
adapting
ReversalClever
by adding the condition that whenever all segments between
consecutive breakpoints are inceasing, it reverses the first such
segment.

Compare the performance of
ReversalGreedy,
ReversalClever, and your ReversalVeryClever, by
running them on random permutation of length 100
(use randperm of the package combinat).

Read Sections 6.16.3
Program done on Feb. 20, 2006, class

NYCold, Find the walk in Manhattan with the largest
number of attractions, using complete brute force.
[to be continued]
Homework for Feb. 20, due Feb. 27:

Complete BPb(HorizA,VertA,a,b), in
NYC, by testing each and every walk of W(a,b) and
picking the one that has the maximal weight.
The program should return the best walk followed by its
weight.

Use Dynamical Programming to write a more efficient program.
Call it BP(HorizA,VertA,a,b),
Lara's Answers to 1 and 2.

Read Sections 6.46.6 .
Programs done on Feb. 23, 2006, class

NYC, Find the walk in Manhattan with the largest
number of attractions, using complete brute force (BPb)
and Dynamical Programming.

Feb 23 version of KING, Finds the best walk
for ForwardMoving King using both brute force
and Dynamical Programming.
[still incomplete]
Homework for Feb. 23, due Feb. 27:

Finish up
KING, to work for the King's walk problem
(right now we only adapted W(a,b) and Wt, do the rest)

Read Sections 6.76.8 .
Programs done on Feb. 27, 2006, class

KING, Finds the best walk
for ForwardMoving King using both brute force
and Dynamical Programming.

LCS, Finds the longest common subsequence of two
inputted words using KING.
Homework for Feb. 27, due March 2

Write a program GlobalSequenceAllignmen, by adapting
LCS, to write a program that inputs an alphabet
of n letters and an (n+1) times (n+1) matrix
(given as a list of lists) with Blank the (n+1)th letter,
signifying the cost (positive or negative), and a pair
of words, and finds the best Global allignment.

Adapt your GlobalSequenceAllignment above to
write a program LocalSequenceAllignment
(see section 6.8)

Read Sections 6.96.14
 Write Maple code that inputs a constant like e, pi, or sqrt(2),
and a positive integer n, and finds the smallest prime number in
n consecutive digits of that constant.
(a) That runs as fast as possible (b) That has the shortest possible code
[5 dollars prizes for the best submission in each category]

Try to go to Christos Papadimitriou's fascinating
talk on Thurs., March 2, 2006, 11:00pm, Core Auditurim.
Program done on March, 2, 2006, class

CHRISTOS, Wasteless prefixreversal sorting.
Homework for March 2, due March 9
 Write a program that inputs a tree (in the awkward
datastructre of a list of list of list of ...)
in
CHRISTOS, write a procedure that inputs such a tree
and outputs the set of leaves.
 Write a program that inputs a tree (in the awkward
datastructre of a list of list of list of ...)
in
CHRISTOS, write a procedure that inputs such a tree
and a leaf and outputs the path to the root, as well as the
sequence of flipplaces from the root to the leaf.

Look up Groebner bases, so that you will be ready to
Professor
Diane Maclagan's fascinating guest lecture.
Work done on March, 6, 2006, class
Homework for March 6, due March 20

Do all the homework in Professor Maclagan's
handout.
Program done on March, 9, 2006, class

EXONb, Exonchaining by bruteforce.

EXONc, Exonchaining by Dynamical Programming.
Homework for March 9, due March 20

Read Section 6.14 carefully and write a Maple program
for the Spliced Allignment Problem.
Programs done on March, 20, 2006, class
We took a break from the book, studying some
random walk problems.

ORW, Oriented Random Walk in one dimension.

ORW2, Oriented Random Walk in two dimensions.
Homework for March 20, due March 27
 Generalize ORW2 to k dimensions, where k is arbitrary.
The procedure whould be GFk(k,x,t,p) where the variables are
x[1], ..., x[k], variable t takes care of the length, and p is
the probability of doing the same kind of step as yesterday,
and all other options are equiprobable (with probability (1p)/(2k1)).
 Implement in Maple (using the plot package)
Tupper's selfreferential formula.
Tupper's selfreferential formula.
[Thanks to Arvind Ayyer for suggesting this].
 Read Chapter 7
 Try to think about a Final project.
Programs done on March, 23, 2006, class

Merge Sort (illustrating Divide and Conquer)

KingWalks, the number of ways for a forwardmoving King
to walks from the origin to a designated point (m,n), using O(max(m,n))
memory.
Homework for March 23, due March 30
 Adapt
KingWalks to have a memoryefficient program to compute
the length of the longest paths in the edit graph
where the input are two words in the alphabet and a table of
weights for w[a,b] for each pair of letters a and b and
w[a,BLANK], w[BLANK,a] for each letter a.
Programs done on March 27, 2006, class

EDIT [Best editing sequence with linear memory usage]
[still incomplete]

MEMORY, "Memory wheel" (a.k.a. deBruijn sequences).
[to be continued...]
Homework for March 27, due March 30
 Finish up
EDIT by implementing the pseudocode PATH(source,sink)
on the top of p. 234.

Write a bruteforce Maple program that inputs a directed
graph [V,E] and outputs a Hamiltonian path if one exists
or FAIL. Apply this to G({0,1},3) obtained from
MEMORY.
Programs done on March 30, 2006, class

MEMORY1 "Memory wheel" (a.k.a. deBruijn sequences), second version,
[to be continued...]

HAMILTON,
Hamiltionian paths by brute force.

EULER,
Eulerian paths and cycles [just started]
Homework for March 30, due April 6
 Finish up
EULER by finishing procedure Fleury (that just got started)
that inputs a directed graph and outputs a Eulerian cycle if one
exists or returns FAIL. Feel free to introduce as many
other procedures as you wish.
NOTE: Proposals for Final Projects due April 15, 2006. The
Projects themselves are due May 10, 2006.
Programs done on April 3, 2006, class

MEMORY1 : Final Version (includes DeBEfast, uses Fleury's
algorithm).

EULER,
Eulerian paths and cycles [final version, bug corrected].
Homework for April 3, due April 10

Modify Fleury(G,u) in
EULER, that inputs a directed graph G=[V,E] and a
vertex u and outputs a Eulerian cycle that starts and ends at u,
to write a procedure FleuryP(G,u,v) that finds a Eulerian
path from u to v or returns FAIL.

Write a more efficient program for Fleury's algorithm than the one
currently in
EULER.
[Five dollars prize for the most efficient program]

Implement Dijkstra's algorithm (described, for example,
in Robin Wilson's book "Graph Theory", 4th edition, pp. 3839)
for finding the shortest
path from vertex a to vertex b in a weighted directed
graph given as [V,E] where each member of E is a triplet
[u,v,weight] meaning there is an edge from u to v of weight
weight.

Modify it to find the shortest "alternating path"
which alternatively goes with the arrow and against
the arrow.

Use it to solve the following classical riddles:
 How can Cabbage, Wolf, Sheep and Man cross a river
with a small rowboat that can only take one or two passengers
and only the man knows how to row.

Ditto for 3 missionaries and 3 cannibals
(version 1: they all know how to row, version 2: only one
cannibal does)

How can four people who can walk through a dark
narrow tunnel (that has room for at most two people
at a time) in 1,2,4,5 minutes, do it if the battery
of the flashlight will only last 12 minutes?
Programs done on April 6, 2006, class

GREP : Searching for a pattern in a text.

RandTreeBaxter,
Andrew Baxter's program for generating a general random tree.
Homework for April 6, due April 10

Write a program that inputs a set of keywords and
outputs a keyword tree.
Program done on April 10, 2006, class
Homework for April 10, due April 17

Write StupidViterbi, and if possible Viterbi
(look at Ch. 11 of the book).
Two Suggested Projects
Program done on April 17, 2006, class

HMM, Hidden Markov Model and Viterbi's Algorithm.
Homework for April 17, due April 20

Write Backwards1 (as analog of Forward1) and
a program to find the probability distribution
of the states at any time i, given the
vector of outcomes x.
Programs done on April 20, 2006, class
It was a beautiful day so we did the algorithms
for Hierarchical Clusters with pencil and paper
sitting under a real tree.
Homework for April 20, due April 27

Implement in Maple HierarchicalClustering on p. 345 of the book
Program done on April 24, 2006, class
Homework for April 24, due May 4

Finish
CLIQUE, by writing a program that inputs a simple
graph and outputs a graph that is a disjoint union of
cliques and is as "close" as possible to the original graph.
Program done on April 27, 2006, class

CLIQUE, The Brute Force Corrupted Clique [finished]

PCC, The PCC algorithm JonesPevzner, p. 352
[still buggy and just started. to be continued].
Homework for April 27, due May 1, 2006

SetP of
PCC, does not run. Please write a good program.
Program done on May 1, 2006, class
It was again a nice day, so we used our natural
computers (a.k.a. human brains) to study the
AdditivePhylogeny algorithm described on p. 364.
Optional homework for May 1, 2006, class
Implement AdditivePhylogeny in Maple.
Final Projects
Dr. Z's teaching page.