« April 2006 | Main | June 2006 »
May 31, 2006
Lecture11
Lecture 11
lecture 11 second half
Posted by tonglaga at 07:19 PM | Comments (0)
the correction of the test
There is a mistake in the test. Question 5 is about quick sort, not binary search. I will see if I can make the change before the test is distributed. sorry about that.
tonga
Posted by tonglaga at 06:38 PM | Comments (0)
Exam 1 Study Guide
Here is the list of things to study for the midterm exam:- Understand the concepts from the homeworks
- Go through the lecture notes to find emphasized topics - make sure you understand those topics
- Be prepared to discuss what you learned about efficient programming from the projects (and don't worry about phylogenetics specific questions, there aren't any)
- NP-completeness: how to prove it and what does it mean
- big-O, big-Theta and big-Omega, and how they relate to one another
- parts of a greedy algorithm
- greedy algorithms for minimum spanning trees, sorting, and knapsack loads and how they work
- Equation 7.1 (The "Master Theorem" - pp 223-224)
- parts of a divide and conquer algorithm
- binary search
- quicksort, the pivot selection problem and worst-case behavior of quicksort
- solving non-homogeneous recurrence relations
- performing the change of variables operation on recurrence relations
- dynamic programming
- principle of optimality
Understand that this is a superset of the subjects on the exam, as it is basically just straight from the schedule. So not everything listed will be on the exam, but if you study everything listed, it will help you to be well prepared for the exam.
Posted by ryanShepherd at 05:15 PM | Comments (0)
the test
There was a miscommunication in the CS office and the test got into the testing center a little late. The testing center will have the test available tomorrow, but not exactly when it opens. sorry about the inconvenience.
tonga
Posted by tonglaga at 04:08 PM | Comments (0)
Homework 8
1. Section 3.2, first question, on page 10 of the Recurrence Relations notes
2. Consider figure 8.4 for filling a knapsack using dynamic programming. Let's use a new set of objects whose weights are 1, 2, and 4 units, and whose values are 1, 7, and 15, respectively. If we can carry a maximum of 12 units of weight, construct a new table like 8.4 to determine the optimal load in a knapsack (using DP) with these objects. Analyze the new table to determine which objects will be included in the optimal load.
3. 8.13 (on extracting equivalent optimal solutions to 0/1 knapsack from the DP table)
4. 8.17 page 279
Due Friday, June 2.
Posted by tonglaga at 11:29 AM | Comments (0)
project 4
Posted by tonglaga at 11:26 AM | Comments (0)
May 30, 2006
Homework keys 4, 5, 6, and 7
Here are the keys for homeworks 4 - 7
Homework 4 RTF
Homework 5 RTF
Homework 6 RTF
Homework 7 RTF
Posted by ryanShepherd at 03:53 PM | Comments (0)
May 27, 2006
Update on Project 3
For those who are experiencing a problem with two layer 5s in problem 1, core 2, here is an updated version of the database with the layers renumbered properly.
You can also just make it so that when you see a duplicate layer number, you always go with the last duplicate you saw - in this instance the limestone would end up being layer 5, and the sandstone layer 5 would be thrown away. I think that's what the professors ended up going with last semester.
Good luck, and also, since Monday is a university holiday, I don't think it counts as a late day (as the TMCB is completely closed).
Posted by ryanShepherd at 03:04 PM | Comments (0)
May 24, 2006
Homework 7
Homework #7 due Friday, May 26
Homework problems from the recurrence relations handout - all the problems from both parts 1 and 2 (parts 1.2 and 2.3 respectively).
Posted by ryanShepherd at 04:22 PM | Comments (0)
May 19, 2006
TA Hours for Friday
Since I'm going to be doing the class today (Friday), I won't be holding my regular hours. If you weren't planning on coming, but have questions about project 2, I suggest you come to class, as we will spend some time discussing it. See you there.
Posted by ryanShepherd at 12:57 AM | Comments (0)
May 17, 2006
no homework today and friday
No homework today and friday. Good luck on your project.
tonga
Posted by tonglaga at 04:01 PM | Comments (0)
Lecture 7
Posted by tonglaga at 03:57 PM | Comments (0)
May 15, 2006
project 3
Posted by tonglaga at 11:19 PM | Comments (0)
Lecture 6
lecture 6
lecture 6 second half
Posted by tonglaga at 04:26 PM | Comments (0)
Homework 6
Homework #7: Due Wed May 17 (More intense)
7.10 (write down how you became convinced)
7.12 (be sure that your proof of the correct big-O bound is solid)
7.14
7.15
7.23
Posted by tonglaga at 04:15 PM | Comments (2)
May 12, 2006
lecture 5
Posted by tonglaga at 04:14 PM | Comments (0)
Homework 5
1. Problem 6.18
1. Problem 7.2
2. Problem 7.7
3. Use equation 7.1 to give a bound on the running time of a divide and conquer algorithm that splits a problem into pieces that are 1/5 the size of the original problem, solves 4 of the pieces and requires ?(n^2) to recombine subproblems at each level. Suppose that you could recombine the subproblems using an ?(n) algorithm if you solved all 5 subproblems rather than only 4. Which algorithm has a better bound?
Due Monday, May 15
Posted by tonglaga at 04:11 PM | Comments (0)
May 10, 2006
Lecture4
Lecture 4
lecture 4 second half
Posted by tonglaga at 06:43 PM | Comments (0)
Homework 3 key
Homework 3 RTF
Posted by ryanShepherd at 05:08 PM | Comments (0)
May 09, 2006
Homework Keys
Here are the keys for Homeworks 1 & 2
Homework 1 RTF
Homework 2 RTF
Posted by ryanShepherd at 02:58 PM | Comments (0)
Homework 4
Question 1 Simulate each step of Dijkstra's algorithm, and turn in a table similar to the table in the middle of page 199, on the following directed graph consisting of 5 vertices labeled 1,2,3,4,5 and the following 5 edges
1 to 2 is connected by an edge with cost 6
1 to 3 is connected by an edge with cost 4
2 to 4 is connected by an edge with cost 3
1 to 4 is connected by an edge with cost 9
1 to 5 is connected by an edge with cost 20
4 to 5 is connected by an edge with cost 6
Question 2 Implementing Dijkstra's algorithm requires finding the smallest element in a set (line 8 of pseudocode on page 199) and removing an element from a set (line 9). Discuss the datastructures and algorithms that you might use to implement these operations in the intelligent scissors project. In your discussion, address the efficiency implications of your decisions.
due Friday, May 10.
Posted by tonglaga at 12:03 PM | Comments (0)
Lecture 3
Posted by tonglaga at 08:49 AM | Comments (0)
May 08, 2006
New Description of project 1
The following link gives the new project description. It is just a subset of the original description. It takes off the things you don't need to do.
Posted by tonglaga at 04:53 PM | Comments (3)
Homework 3
1. Problem 6.1 page 214
2. how that the greedy algorithm for making change in Section 6.1 will or will not always make correct change for the Nephite coinage system given in Alma 11.
3. get really comfortable with VS 2005.
i. Read through the highlights of set of documents linked from this page at MSDN: Introduction to C#
ii. Work through this "Hello, World" example at MSDN: Hello, World
iii. Extend your "Hello, World" example:
For this assignment, please simply submit a screenshot of your final sorting GUI and indicate which sorting algorithm you implemented.
Read sections 6.3 and 6.4 on Spanning Trees and Shortest Paths.
due Wed, May 10.
Posted by tonglaga at 04:30 PM | Comments (0)
May 05, 2006
lecture2
Posted by tonglaga at 05:04 PM | Comments (0)
Lecture 1
Posted by tonglaga at 04:48 PM | Comments (0)
homework 2
Consider the following algorithm for getting a drink of water in an apartment in which n roomates share n cups.
Procedure get-drink (dirty: int, clean: int, n:int)
if (clean = 0) then
for (j = 1 to n) do wash-cup(j);
dirty = 0;
clean = n;
drink-water();
return (dirty+1, clean-1,n)
Question 1 Suppose that rather than using the get-drink algorithm above, the roomates decided to implement a "you use it, then you wash it" policy instead. Under policy, one would get a drink of water then immediately wash the cup so that all cups were clean at all times. Compare and contrast the amount of time required to get a drink of water under both policies. How does this related to the design of algorithms and data structures?
Question 2 Problem 4.19 page 142
Question 3 Problem 12.35
Question 4 problem 12.49
due Monday, May 8.
Posted by tonglaga at 10:47 AM | Comments (0)
May 04, 2006
Ryan's TA Hours
My hours will be as follows:
Monday from 4 to 7 P.M.
Tuesday from 2 to 5 P.M.
Wednesday from 4 to 7 P.M.
Thursday from 3 to 5 P.M.
Friday from 12 to 2 P.M.
I may be available earlier than 3 on Thursdays (hopefully not any later than 3 though). This schedule is tentative, so it may change during the course of the term. Also, I have a wedding to go to tomorrow so I will not be here. If there are any questions about the homework due tomorrow, you can email me (see the syllabus for my address) and I will try to answer your questions.
Posted by ryanShepherd at 03:51 PM | Comments (0)
May 03, 2006
Homework
Homework is 1.21, 2.2, 2.3, 2.4, 3.5, 3.20
Due Friday, May 5.
Posted by tonglaga at 03:52 PM | Comments (2)
May 01, 2006
phylogenetics
Project 2: phylogenetics with dotty
Project 2: phylogenetics without dotty
Posted by tonglaga at 12:41 PM | Comments (2)
Intelligent Scissors
Project 1: Intelligent Scissors
Posted by tonglaga at 11:49 AM | Comments (0)