« January 2005 | Main | March 2005 »

February 28, 2005

[Projects] Self assessment for drill core alignment project (due 3/2)

There is no explicit performance requirement for this lab. This is one of the benefits of being a pioneer, I suppose. Instead, you get to answer the following questions...

  1. Does your project work? Same deal as last time: if it doesn't, then describe the problem in as much detail as possible. You can get full credit with a detailed explanaition of why your code doesn't work.
  2. What was the hardest part of this project?
  3. How much time did you spend on this project before you wrote your first line of code?
  4. How much time did you spend writing code?
  5. How much time did you spend debugging?
  6. Give pseudocode for the algorithm you used to extract the matched layers from your table.

Posted by jones at 07:32 PM | Comments (0)

[Projects] C# timer

[The Code Project - High-Performance Timer in C# - C# Programming] While there is no explicit performance requirement for this lab, you may find this timer class useful in your self-assessment or improvement.

(Thanks to Doyle for the pointer to the class.)

Posted by jones at 07:25 PM | Comments (0)

[Lectures] Matrix multiplication and top-down dynamic programming

Index of /~jones/cs312 see 16-matrixmemory.pdf. The notes about Floyd's algorithm are near the end.

Posted by jones at 03:10 PM | Comments (0)

[Projects] Magic Squares lab

[Homepage for magic squares lab] This one involves backtracking. Its not quite as easy as the core alignment project (sorry...) and not quite as hard as the phylogenetics project. SAme deal as last time: read problems from a database, solve them and write solutions back out. Database is linked to the project homepage.

Posted by jones at 12:45 PM | Comments (0)

February 25, 2005

[Exams] Exam 1 stats

Average time to complete the exam: 1h 5minutes (max was 1:57 and min was 34 mins).

Average: 84.2
Std Deviaion: 12.94
Variance 167.56

The sample size is pretty small, so you can't conclude too much, but generally speaking, higher scores correlated with spending less time taking the test.

Posted by jones at 02:05 PM | Comments (0)

[Announcements] Grades and the gradebook

I got a little behind on grading, but I am close to being caught up. Here's the scoop: crossing the desert is completely graded, but there were problems getting it into blackboard. It will be online soon, meanwhile you can send mail to the TAs at cs312ta@gmail.com to get your grade.

Homework upto recurrence relations is graded and entered. Send the TA's mail if you are missing a grade.

I've graded all of the phylo improvement papers that I got. Grades will be posted soon. I didn't get very many papers, only like 4. If you don't have a grade for that by next wednesday, send me your report, tell me when you finished it and i"ll grade it.

Phylo project will be graded soon.

Posted by jones at 01:58 PM | Comments (1)

February 23, 2005

[Homework] Floyd's algorithm (due 2/28)

From the book, problems 8.17 and 8.18. Due 2/28. Note that in problem 8.18, you are adapting Floyd's algorithm to find a path if it exists, rather than find the shortest path. In this problem, you aren't given edge costs, so you don't care about finding the shortest path--just any old path will do.

solution
8.17 Yes. The algorithm works fine as long as there are no negative cycles. If there is a negative cycle, then a negative value is written to a diagonal.
8.18 The main modification is that don't add path lengths and use the min function. Instead, you just and together path existences and set matrix entries to 1 if a path exists.

Posted by jones at 03:16 PM | Comments (0)

[Homework] Knapsack and Dynamic Programming (due 2/25)

From the textbook, problems 8.11 (hint: the equation on page 267 will be useful for you) and 8.12

Posted by jones at 03:12 PM | Comments (0)

February 22, 2005

[Lectures] Notes for introduction to dynamic programming

see Index of /~jones/cs312 and get the file 18-2005-intro-to-dp.pdf

Posted by jones at 03:20 PM | Comments (0)

February 17, 2005

[Projects] updated phylo lab available

There is a new slightly modified distributable of the phylo lab available at http://students.cs.byu.edu/~rdp/phylo/phylo.zip
This is the same with a few more test cases.

Posted by roger at 03:13 PM | Comments (2)

[Projects] Drill core alignment files

We have prepared a writup describing the drill core alignment problem and algorithm. For this project, there is no file distribution. You get to create your own from scratch. But we did create a database of sample problems and a problem generator (which you may use at your own risk!)

Posted by jones at 10:27 AM | Comments (0)

[VisualStudio] Reading and writing from an Access database

For the drill core lab, you get to write you own code to connect to the database. If you are smart and lazy, you might just copy and modify the TA's code for connecting to databases. You used that code in the first two projects. Here are a few ideas for how to adapt their code for this project. Of course, you might also decide to use your own method for connecting to a database. That's fine too.

You will need to add

using System.Data.OleDb; // needed for database code
to list of "using" directives near the top of your file.

The TA's establishConnection function needs a string that gives the location of the database relative to the executable created for your program. As you may know, your executable will live in either <projectHome>/bin/debug or <projectHome>/bin/release. YOu will put your database file in the <projectHome> directory which means that you will need to use ..\\..\\core-samples.mdb as the source string parameter to establishConnection.

In the TA code for the phylogenetics project, the aptly named function "load" loads a problem from the database. You will be reading from tables that have a slightly different and simpler format than in the phylogenetics project.

Here's some more info from the good people at Microsoft. [Creating Connections to Access Databases (Visual Basic and Visual C# Concepts)]

Posted by jones at 08:09 AM

February 15, 2005

[Homework] Change of Variables (due 2/18)

The problems from section 3 of the handout on recurrences. Due 1 hour before class on Friday.

solution
Here is my solution to the first problem. Neither myself nor the other professor were able to solve the last one. I've posted this in good faith, but am sure that there's at least one error on it. i'll give everyone who points out an arithmetic error in my notes one extra point on their homework per error. No limit. Everyone who finds the same error gets a point. Have fun. :)

Posted by jones at 09:32 AM | Comments (0)

[Projects] Phylo. project now due Friday 2/18

[Updated schedule] I think the workload was a little compressed over the last week and I think that the phylo project is harder than most people think. So be smart and get a head start on it.

Posted by jones at 08:51 AM | Comments (0)

February 14, 2005

[Announcements] Phylo Project Important Information

We have disovered 3 things that you will want to be aware of while working on your phylogenetics projects:

  1. The example dot files have a spurious "}" character midway in the files. You will want to ignore this extra closing curly brace. You can also do many more things to format your dot file to better meet your needs. The GraphViz website has a lot of good documentation.
  2. Problem 3 has an extra taxa that need to be deleted for the tree to make sense. The bad taxa is taxa number 8. You can download a new database here or you can delete the taxa from your current database. You need to copy the downloaded database over your existing database in your project distribution directory. To delete the taxa from your current database, you need to first have Microsoft Access installed on your machine.
    1. Open the phylo.mdb file located in the project distribution using Access
    2. Select the "tables" option in the viewer
    3. Open the tTaxa table
    4. Find the node 8 taxa for problem 3
    5. Right-click and choose delete record
  3. The current viewer only passes taxa sequences of 9 characters to your UnrootedTree:defineTaxa function rather than 10 character sequences as in the database. This is fine! Just work on 9 character sequences rather than 10.

Posted by egm at 09:39 AM | Comments (0)

[Projects] Using the SVG Viewer in the CS Open Labs

The viewer works for sure in room 1066. Supposedly, it was or will be installed in the other windows labs.

Posted by jones at 09:39 AM | Comments (0)

[Homework] Nonhomogenous linear recurrances (due 2/16)

See the homework at the end of section 2 of the handout. Due 2/16. Remember not to stay stuck for more than 1/2 an hour on any one problem.

solution Typesetting of solutions curtesy of Andrew Harris.

1) Solve tn - 4(tn-1) + 3(tn-2) = 0.

tn - 4(tn-1) + 3(tn-2) = 0
replace tn with r^n...
r^n - 4r^(n-1) + 3*r^(n-2) = 0
write down characteristic function using theorem...
(r^n - 4r^(n-1) + 3*r^(n-2))/(r^n-2) = 0
factor ...
r^2 - 4r + 3 = 0
(r-3)(r-1) = 0
write down general solution...
tn = 1^n, 3^n
c1*1^n + c2*3^n = 0

use intial conditions to solve general solution for these initial conditions...
t0 = c1*1^0 + c2*3^0 = 0
t1 = c1*1^1 + c2*3^1 = 1

c1 + c2 = 0
c1 + 3*c2 = 1

c1 = 1/2
c2 = -1/2

and the final answer is...
----------------------------
tn = (1/2)*1^n + (-1/2)*3^n
----------------------------

2) Same idea, just more complicated. You may leave solutions with more than 2 unknowns in this form on an exam. I'll assume that you can solve for several unknowns, or that you will learn it in an algebra class...

tn - 3(tn-1) + 2(tn-2) = 1^n * n^2
(r^2 - 3r^2 + 2) (r-1)^3 = 0
(-2 (r^2 - 1)) (r-1)^3 = 0
(-2(r-1)(r+1)) (r-1)^3 = 0

tn = c1*(1)^n + c2*n*(1)^n + c3*n^2*(1)^n + c4*n^3*(1)^n + c5*(-1)^n
t0 = 0
t1 = 1
t2 = 7
t3 = 28
t4 = 86
t5 = 227

t0 = c1 + 0 + 0 + 0 +c5 = 0
t1 = c1 + c2 + c3 + c4 - c5 = 1
t2 = c1 + c2*2 + c3*4 + c4*8 + c5 = 7
t3 = c1 + c2*3 + c3*9 + c4*27 - c5 = 28
t4 = c1 + c2*4 + c3*16 + c4*64 + c5 = 86
t5 = c1 + c2*5 + c3*25 + c4*125 - c5 = 227

Posted by jones at 07:43 AM | Comments (0)

February 11, 2005

[Projects] Phylogenetics self-assessment

For this project there will be no performance requirement. Instead, you get to fill out a self assessment (.doc) (or .pdf version). You may email the completed form, write your own version of the form on your own text editor or turn in a paper copy. Whatever works for you.

Posted by jones at 01:32 PM | Comments (0)

February 10, 2005

[Homework] Linear homogeneous reccurance relations (due 2/14)

Do the homework in the recurrance relation notes (see full post for link to notes).

solution

1. first one is, others are not.

2. t_n = 2^n is indeed a solution for t_n - 5t_{n-1} + 6t_{n-2} = 0 because 2^n -5(2^{n-1}) +6t^{n-2) = 0 (details left for the reader).

3. Finally, we can verify that verify that c1(3^n) + c2(2^n) is a solution for t(n) - 5t(n-1) + 6t(n-2) = 0 for any constants c1 and c2. by doing the following (curtesy of Kawika Heftel). 

c1(3^n) + c2(2^n) - 5(c1(3^(n-1)) + c2(2^(n-1))) + 6(c1(3^(n-2)) + c2(2^(n-2))) = 0
c1(3^n) + c2(2^n) - 5c1(3^(n-1)) - 5c2(2^(n-1)) + 6c1(3^(n-2)) + 6c2(2^(n-2)) = 0
c1(3^n) - 5c1(3^(n-1)) + 6c1(3^(n-2)) + c2(2^n) - 5c2(2^(n-1)) + 6c2(2^(n-2)) = 0
c1((3^n) - 5(3^(n-1)) + 6(3^(n-2))) + c2((2^n) - 5(2^(n-1)) + 6(2^(n-2))) = 0
c1*3^n(1 - 5(3^-1) + 6(3^-2)) + c2*2^n(1 - 5(2^-1) + 6(2^-2)) = 0
c1*3^n(1 - 5/3 + 6/9) + c2*2^n(1 - 5/2 + 6/4) = 0
c1*3^n(1 - 5/3 + 2/3) + c2*2^n(1 - 5/2 + 3/2) = 0
c1*3^n(1 - 1) + c2*2^n(1 - 1) = 0
c1*3^n(0) + c2*2^n(0) = 0
0 = 0

Posted by jones at 08:15 PM | Comments (0)

[Lectures] Approximate schedule for recurrence relations

There's a handout (click on title to see the full post along with the link to the notes) on recurrence relations that I'll pass out in class on Friday. The schedule said it should be passed out on wednesady, but we are about 1 day behind. Updated 2/14 to include another section for today's class and more homework that will due 2/16.

Posted by jones at 07:11 PM | Comments (0)

[VisualStudio] More efficient and stable for C# than for C++?

The word I am getting from people in the class is that visualStudio is much more efficent and stable for C# than C++. The interactive debugger is even fast enough to be useful with C#. That's consistent with my experience. I took a minute to reflect on my visualStudio experience and realized that I have always used it for C# programming. So that's why I was a little surprised when so many of you reported slowness and instability on the first projetc (in which we used C++ you may recall).

What has been your experience?

Posted by jones at 10:38 AM | Comments (0)

February 09, 2005

[Exams] Important Typo on Problem 6

In question 6, "binary search" should be "quicksort". So when you take the test, replace "binary search" with "quicksort" and answer the question.

Posted by jones at 01:25 PM | Comments (0)

February 08, 2005

[Exams] Test 1 extended to Satuday

I extended the first test to run from Wednesday to Saturday. (Except for Rob, for you its not extended :) just kidding).

Posted by jones at 03:54 PM | Comments (0)

February 07, 2005

[Exams] Study List for Exam 1

Focus on the reading, lectures, homework and study questions. Make sure you are comfortable with the following topics:

Crossing the desert won't be on the exam and there won't be anything about other methods for deriving solutions to recurrance relations. We'll get plenty of recurrance relations on the next exam.

Posted by jones at 02:52 PM | Comments (0)

[Study Problems] Divide and Conquer Problems

A few questions related to divide an conquer algorithms. These are not required or graded, but might be useful for studying for exams. These questions deal with divide and conquer algorithms.

1. How does divide and conquer improve the efficiency of searching in binary search?

solution

Kind of an easy question, maybe too easy. Basically, you narrow your search space by 1/2 an each iteration.

2. Suppose you have a divide and conquer algorithm for multiplying large matrices. Suppose your algorithm divides each of the original n by n matrices into n/3 by n/3 matrices. Suppose that you have a way of multiplying and recombining the n/3 matrices into the n by n product that requires 8 matrix multiplications and 5 matrix additions. What is the complexity of your new algorithm (use Equation 7.1)? Does your algorithm perform better than Strassen's algorithm?

solution

This is an impossible situation, but we will do the analysis anyway. 

 

T(n) = 8(T(n/3)) + O(n^2)

So that l = 8, b = 3, k = 2 and 8 < 9 so you get big-Theta(n^k) = big-Theta(n^2).


3. Prove that m1 + m2 + m4 - m7 really is the correct value for the bottom left corner of the product matrix on page 242 on the book. The product matrix is in equation 7.10 and the multiplicands appear earlier on teh same page.

solution

sort of a tedious but easy little proof. basically, you expand each m-term and simplify the resulting expression and find that you get a21b11 + a22b21 as desired.

Posted by jones at 02:44 PM | Comments (0)

February 05, 2005

[Announcements] New webpage layout

As you can see, I've redesigned the webpage. I hope its easier to find things. Let me know what you think of this one. By the way, this version was created based on a comment from Prajwol.

Posted by jones at 08:38 PM | Comments (0)

February 04, 2005

[Projects] Discussion of Phylo. project

Same deal as the Crossing the Desert project. Post your problems and solutions here as they related to project 2.

Posted by jones at 06:39 PM | Comments (4)

[Projects] Phylogenetics Project (due 2/16)

In which you implement an algorithm for doing phylogenetic inference. Due (in section 003) on 16 February. You will need to download some files, install an Adobe library (if you aren't using a lab machine) and move a directory...

1. Read the project description and learn the algorithm that you will be implementing.

2. Download the project file distribution. Unzip it and move the "tmp" folder to your C drive as c:\tmp (this is a bit of a hack, but you are free to improve it if it really bothers you--but it doesn't count as the improvement project!).

3. If you are NOT using a CS department windows lab machine, install the Adobe SVG library.

4. Implement the unrootedTree class as described in the UnrootedTree.cs file in the project distribution.

I've written some more notes on debugging with visualStudio that will hopefully save you some time learning the interface.

Posted by jones at 02:01 PM | Comments (5)

[VisualStudio] Debugging

If you can't debug, then you are probably going to struggle with the projects. If you can't see what your program is doing, then you can't debug. Here's some ideas on debugging in VisualStudio.

Keep in mind that the help functionality of VisualStudio is actually pretty good and that we have free online access to the O'Reilly books.