April 04, 2005
Linear programming problem (due 4/13)
Here is the problem to solve with your linear programming project. The project is due the last day of classes. There will be no late days. The project is to turn this problem into a linear programming problem and then solve it with your simplex solver. You are free to use any input format you like and you are free to just hard-code the input right into your program if you like. This is the only problem your program will be tested on (but we will look at your source code to make sure your program isn't just "wait 2 seconds then return the solution").You are the operations director for a processing plant at a large mine. Your job is to devise a program, or plan, for the plant that maximizes profits while staying within the resource budget. The plant produces four major resources: copper, gold, silver and platinum.
In a given week, the mine produces 2,000 tons of ore that must be processed into some combination of the four major resources. A ton of ore contains 10 ounces of copper, 2 ounces of gold, 3 ounces of silver and 1 ounce of platinum. You many only extract one resource from each unit of ore processed.
Processing the ore requires power, water, labor and use of one of the three processing lines. Producing each of the resources requires different amounts of processing resources. One ounce of copper requires 30 kW hours, 1,000 gallons of water, 50 hours of labor and 4 hours of processing time on a processing line. One ounce of gold requires 15 kW hours, 6,000 gallons of water, 20 hours of labor and 6 hours of processing time on a processing line. One ounce of silver requires 19 kW hours, 4,100 gallons of water, 21 hours of labor and 19 hours of processing time on a processing line. One ounce of platinum requires 12 kW hours, 9,100 gallons of water, 10 hours of labor and 30 hours of processing time on a processing line.
There is only a limited amount of power, water, labor and processsing line time available. In a given week, you may use 1,000 kW hours of power, 1,000,000 gallons of water, 640 hours of laber and you can run the processing lines 24 hours a day for 7 days a week for a total of 504 hours.
Finally, each ounce of finished resource has an associated profit. An ounce of copper is worth $10.20, an ounce of gold is worth $422.30 dollars, an ounce of silver is worth $6.91 and an ounce of platinum is worth $853.00.
Posted by jones at 10:29 AM | Comments (2)
TSP is due today, Monday 4/4
Just a reminder that the due date for the TSP project was moved to today. Be sure to turn something in (not neccesarily today) even if it is incomplete.
Posted by jones at 08:41 AM | Comments (0)
March 30, 2005
Scheduling for presentations
April 6 Rob and Doyle and Chris Hathaway and
April 8 Kawika and Andrew Harris and Ben Booth and Brad
Posted by jones at 03:54 PM | Comments (0)
More about improvement presentations
YOu have to write a presentation and describe your favorite improvement. That presentation should go about 10 minutes and you should allow a few minutes for questions. The TAs will use the following form to evaluate your presentation:
- Content [60 points]: Could you understand what they did for their improvement? Did you know what their improvement was supposed to accomplish? Did they present enough data so that you could conclude that their improvement did or did not accomplish its objective? Did their conclusion about their improvement match the data they presented? Did they have any idea why their improvement did or did not work ? Did they have any ideas for what to do next to either improve their improvement or try something else?
- Visual Presentation [20 points]: Were the slides readable? Was the data well-presented? Were the slides tacky and distracting? Did they look at their feet or the keyboard the whole time?
- Oral presentation [20 points]: Did they speak clearly? Did they vary their tone and speed?
For 312, you will probably want to use an outline that goes something like this. Variations are fine, you know the scoring criteria so have fun if you want to do something completely different.
- INtroduction. What problem does your improvement work on? (1 slide)
- What is your improvement supposed to improve about your solution to that problem? How do you know that this is a problem? (1 or 2 slides)
- What is your improvement? (1 or 2 slides) This would be a good place to talk about how you implemented your improvement, but be careful not spend forever talking about coding.
- Say wehter or not you think your improvement accomplished anything and then present some data that supports your conclusions. (2-3 slides)
- Close by saying why your improvement did or did not work and what you would change next if you had enough time. (1 slide).
I've posted a guide to writing presentations. It is written mostly for graduate students presenting research, but the ideas apply to presenting improvements. You'll find that its pretty opinionated. I can be pretty dogmatic when I want to be, and I did. So try not to get caught up in that.
Posted by jones at 02:35 PM | Comments (0)
An Access Database with more TSP Examples
A kind student has created an access database with more TSP examples
Warning: some lines have a preceeding space on their row definition and others do not.
Posted by jones at 10:37 AM | Comments (0)
March 28, 2005
More TSP Problems
We have created an archive with more tsp problems. They aren't in an access database, you get to do that tedious step yourself.
If you do put them in the database you are invited to send that database to me and I will distribute it.
Posted by jones at 10:41 AM | Comments (0)
March 14, 2005
No self assessment for magic squares project (in section 003 at least)
So all you have to do is code it up and get in under a second.
Posted by jones at 03:10 PM | Comments (0)
TSP with Branch and Bound project (due 4/1)
[TSP with Branch and Bound Homepage] The homepage includes a description of the database, some documentation for the algorithm and a sample database. This is not an easy lab. Its probably more similar to crossing the desert than drill core alignment. The entire algorithm is covered in the documentation and in class. Its a tricky algorithm to understand but really isn't that hard to code up once you get your head around it. Start early and learn the algorithm before you start coding. Due April 1.
Posted by jones at 12:54 PM | Comments (1)
February 28, 2005
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...
- 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.
- What was the hardest part of this project?
- How much time did you spend on this project before you wrote your first line of code?
- How much time did you spend writing code?
- How much time did you spend debugging?
- Give pseudocode for the algorithm you used to extract the matched layers from your table.
Posted by jones at 07:32 PM | Comments (0)
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)
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 17, 2005
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)
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)
February 15, 2005
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
Phylo Project Important Information
We have disovered 3 things that you will want to be aware of while working on your phylogenetics projects:
- 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.
- 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.
- Open the phylo.mdb file located in the project distribution using Access
- Select the "tables" option in the viewer
- Open the tTaxa table
- Find the node 8 taxa for problem 3
- Right-click and choose delete record
- 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)
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)
February 11, 2005
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 04, 2005
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)
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)
Adobe Library that is required for Phylo Lab.
If you are not going to do all of your development in the department laboratories, then you will need to install a library from adobe. The library handles the display of ps and pdf images. (which will be created by graphViz to vizualize your project). [Page for Scalable Vector Graphics]
Posted by jones at 12:32 PM
February 02, 2005
More about the improvements
Here's some timely info about the improvement part of the project from the syllabus. Its due anytime on friday. You can email it, turn it in on paper whatever is best for you.
You pass off the first part using a project submission tool we will give you. You pass off the second part by writing a 1-2 page report that describes your improvement, what it is supposed to do and give some empirical data from which you conclude whether or not it did what it was supposed to do.
I would expect that you’ll get an idea for your improvement as you work on getting your program to go fast enough to pass off. Remember, the performance requirement to pass off your program is pretty conservative. Just get it running correctly and fast enough, turn it in and start working on your improvements. I think getting it to run fast enough will be about 60% of the total work for a project and doing the improvement and writing about will be about 40% of the total work.
You are encouraged to work together on your projects and improvements. If you work with someone else, just say who it is in your final report. While you each need tot write your own code and report, you can both work on the same improvement and you can share results. For example, you might think up a clever but difficult improvement. You might each only be able to code up ˝ of it. You might combine your implementations into one and write a report about that. Note that each of you wrote about ˝ the code and each of you wrote your own report but you only ended up with one program in the end.
Posted by jones at 08:50 PM | Comments (0)
Description of the Phylogenetics Project
We have completed the description of the phlyogenetics project. It is due February 16. The file distribution will be available soon. [DC Phylo Project (pdf)]
Posted by jones at 03:06 PM | Comments (0)
January 31, 2005
Discussion of Crossing the Desert
I was a little surprised today that so many people were having so many issues with the project. Well, I wasn't surprised that there were issues, but I was surprised that I didn't hear anything until today.
Here's the idea: post your problems related to project 1 here. If you've got a solution to your problem or someone elses' post it here too. I get mail everytime a comment is posted.
Posted by jones at 06:48 PM | Comments (2)
Crossing the desert
[File distribution, project description (see page 5)] This project is due January 31. The problem is solvable using a greedy algorithm, the main challenge is designing the cost function. (Distribution has been fixed).
Posted by jones at 03:28 PM | Comments (2)
January 18, 2005
New Visualizer for the Desert Lab.
Roger has thoughtly spent his nights and weekends working away to create a new visualizer for the desert lab. I have tried it. It works great! The difference between the new version and the version we distributed before is that the new version graphically shows all the nodes so it might make it easier to guess what your solution is doing.
If you are interested in this new visualizer download it from where you downloaded the lab originally (the new version has been posted in place of the old version).
If you have any problems then please send an email to cs312ta[at]gmail[dot]com.
Posted by terry at 06:47 PM | Comments (0)
Maximum Parsimony Scoring
[A good explanation (.ppt), Google Search: maximum parsimony scoring algorithm ] It looks like max parsimony scoring can/should be done one letter at a time. That's good because that's the only way I know how to do it!
Maximum parsimony is the process of finding the simplest explanation possible for a set of data. In phylogenetics, it means finding the simplest tree that might explain the evolution of a set of taxa. Of course, the trick is how to define simple. For this lab, we are going to define "simple" as requires the fewest mutations of each nucleotide assuming that each nucleotide's mutation is independant of the others.
Posted by jones at 09:29 AM | Comments (0)
January 12, 2005
Random thoughts on a phylogenetics lab
We think we have reached concensus on a lab from phylogenetics. The following isn't quite a full write up of the lab, but its a convenient place to record the ideas that will go into it.
Do a simplification of branch swapping. In which we randomly pick an interior edge, delete it AND its endpoints to form a quartet of trees. Then we recurse on the four subtrees. The recursion bottoms-out at say 4 taxa (leaves). The recombination step takes the 4 subtrees and recombines them in any of the 24 possible re-joinings of 4 subtrees around a single (new) interior edge. A scoring function based on maximum parsimony ranks the 24 recombinations and picks the very best one. This one is passed up to the parent for recombination and the next level up.
The tree datastructure isn't really a tree because it doesn't have a root. It doesn't have a root because that doesn't make sense from a biological stand point (I think). So the tree is really a Steiner topology. We then need a data structure that supports the splitting and joining of Steiner topologies. One way to do this is to do a doubly linked list with three links per node rather than just 2.
An interior edge is an edge that connects two interior points. An interior point is a branching point with degree three. In the datastructure, an interior point is a node with three non-null pointers.
The biological interpretation still makes sense, but the difficulty of implementing the algorithm has been reduced. That means we will still find meaningful solutions, but not optimal solutions.
Problems to solve:
- representing the first tree in the database.
- good description of the scoring algorithm. Does it matter what you pick for the root in the scoring algorithm? Will you get different scores based on what you pick for the root ?
- coming up with problem sets.
Posted by jones at 01:29 PM | Comments (0)
January 11, 2005
Part of a Phylogenetics project
[Majority Tree Algorithm] After dividing up a tree into pieces, one needs a way to recombine the trees. This algorithm looks like a good idea for 312.
Posted by jones at 02:13 PM | Comments (0)
January 10, 2005
Disk covering method
[The Disk Covering Method for Large Scale Tree Reconstruction] We are still looking for a good description of a divide and conquer method for phylogenetics. This algorithm looks like a good candidate. Now we need a more detailed description.
Posted by jones at 08:47 PM | Comments (0)
How hard was it to learn C#?
Based on what I am hearing from you all, here are the conclusions I've reached regarding C# in 312...
- This wasn't a very good experiment. Something that actually required writing more C# would have been helpful.
- The visual Studio aspect of the project (ie, the windows and buttons and etc) were interesting and easy. Though it was wierd to use code you didn't write.
- The most annoying part of the change was the syntax (like figuring out how to write "exponent").
- VisualStudio's help interface got mixed reviews.
- The majority of students were either neutral or for using using C#.
Posted by jones at 02:51 PM | Comments (0)
January 05, 2005
Creating a windows application with a textbox and button in C#
A few pointers for creating a windows application in C# that has a textbox and a button. Clicking the button changes the value in the textbox. This has alot of interface programming problems, but should be a nice introduction to what the tools do.
- Create a new project that is a C# windows application (its the top left selection in the C# menu pane).
- In the form1.cs[Design] view, select "View -> Toolbox" to get the drag and drop interface widgets to appear.
- In the bottom right corner of this view, you will see a "properties" box. It might be somewhere else. You can right click on a widget to bring up a menu, then click Properties. One of the properties is "Text". This, as you might be able to see, is the text on the button label or the text in the text box.
- The first line of hte properties box gives the name of the widget. This name is the name you'll use in your code to modify and use the widget.
- Double click on the button in your new form to bring up the C# method that will handle button click events for the button. This is where you will write code to do whatever you want to do when the button is clicked. (For example, you might increment a counter, compute 2 raised to that counter and write a string to the text box).
- To change the value in the textbox, note the name of the text box and set the text attribute of the textbox object to the new value (its all so object oriented!), like so,
textBox1.text = "some new text";You'll know you got the name of thte textBox1 object correct if: when you type the "." a completion window pops up to let you select the attribute you'd like to set (or read) or method you'd like to call. - These widgets do their own damage and updates automatically. Damage is when you change the value of a widget and update is when you redraw the widget with the new value. So you don't have to do damage and updates (you might not appreciate this, but you should be glad that's one less thing to worry about).
- You can declare you own variables that will be visible to all of your widget objects. One place to do this is right after the declarations of your textbox and button objects. In my version (and probably yours too because I just used the default code) that's on about line 16. For example, you might want to declare a new integer that stores the number of times a button has been clicked. You'd declare it here.
Posted by jones at 01:46 PM
January 03, 2005
Drill core alignment project
[Drill core alignment] In which you use the longest common subsequence algorithm to align soil layers in drill core samples. The hard part is figuring out what to do with misaligned layers. We restrict the problem to two dimensions to make it easier. Due on or about March 2.
Posted by jones at 11:38 AM | Comments (0)
January 02, 2005
Crossing the desert
[Crossing the desert] the project description is on page 5. We will use a different input format because you will be reading problems from an Access database and writing to a database. Well, the TA code will handle the database stuff and you get to implement the function that solves the problem. More details about the TA code (including a link to the TA code) coming soon.
Posted by jones at 07:43 PM | Comments (0)
December 30, 2004
Rooted supertree methods in phylogenetics
[Rooted supertree method, Google Search: "a supertree method for rooted trees' ] Its a divide and conquer algorithm with real application from the literature that isn't too complicated to understand. That makes it a great 312 divide and conquer project. Hopefully we can find some real data to run it on.
Posted by jones at 02:28 PM | Comments (0)
December 16, 2004
Background on Needleman/Wunsch DNA alignment
[A nice introduction to the algorithm] This might make an interesting dynamic programing project. I don't understand the biological implications or meaning of DNA alignment though.
Posted by jones at 11:21 AM | Comments (0)
Background on neighbor joining method
[The original paper, Lecture notes, a good discusion] This might be an interesting project. It appears to be a greedy algorithm with no clear objective function.
Posted by jones at 11:12 AM
Setting Command Line Parameters
For many projects, you will need to pass your netID and a database filename in on the command line. Here's how to do that...
Choose "Project |
Then add the arguements under "Command arguements." For most projects, add the name of the database first followed by your netid. So for the Crossing the Desert project, I have to following:
Command arguements: desert.mdb mdj
Posted by jones at 10:44 AM | Comments (0)