Lecture 25 Greedy algorithm

Today, we talked about the application of greedy algorithm on two examples. Minimum Spanning Tree and Activity selection.

Homework 4

Homework 4 is out today. Please leave comments here.

Problem 1

Q: .Initially, how are we going to choose C from F while F has no edges? does that mean choosing one node in the first iteration? do we add the minimum edge to F or separate set?

A: if there are no edges in the graph, each node itself is a connected component. In the first iteration, you choose an arbitrary node and then choose  the smallest edge leaving from that node. We will then add the minimum weight edge into F. Suppose the edge we add into F is (u,v).  Now u and v is in the same connected component  And in the second iteration, you can either choose a single vertex w other than (u,v) or you can choose the connected component {u,v}.

The main point of this problem is to show that no matter which connected component is chosen, the algorithm always output the correct Minimum Spanning Tree. Actually, both Prim's algorithm and Kruskal's algorithm can be viewed as a special case of this algorithm when there is a specific way of choosing the connected component.


Problem 2
Q: Can we use hashmap for problem 2a?

A:  You can use hash function.  Please state which hash function you use and what if there are many collisions for the function you choose.

Additional Hint 1.  you can solve the problem WITHOUT using hash function.
Additional Hint 2. there is an algorithm similar to the idea of merge sort.

Q: can you give some more hint on 2b?
Additional Hint: Try to related the problem with the polynomial:  \sum x^d_i


Problem 3
Q: can you give us some hint on Problem 3?

3.1:  run the algorithm for the binary alphabet for k times
3.2:  it is somewhat similar to the algorithm from homework 3's problem 1.
3.3: try to combine the algorithm from the first two problems

Prim's Algorithm

Today, we talked about Prim's algorithm for the Minimum Spanning Tree Problem.

Lecture 24 Multiplying two polynomials and clarification

This lecture finishes the algorithm for fast multiplication of two polynomials.

Homework 3

Problem 1, the length of the pattern m is less than n.

There is a typo in problem 2 regarding the definition of the delta function (some variable  "m"  should be"i" instead).  I've corrected the typo and uploaded the correct version.


Problem 3, You might be able to get bound better than O((m+n) log n).

Problem 4.

Q :Why can't we just 
 Delete(x);
 Insert(k)

A: you need to implement delete(x). If you just remove the node, it is no longer a binomial tree.

Homework 2

Full score is 90
Average 73.86
Median 75

Lecture 23. fast polynomial multiplication algorithm

In this class, we explain the idea of multiplying two polynomials of degree n in time O( n log n).

Lecture 22. String matching and polynomial multiplication

In this class, we explain the following relationship between approximate string matching and polynomial multiplication.

If you can multiply two polynomials of length N in time O(N log N). Then you can solve the problem of string matching problem in time O(n log m) where n is the length of the string and m is the length of the pattern.

Course evaluation

Hi, Class

It is the time for midterm course evaluation.
Please leave comments (through the system) on how happy (or angry) you are with me for the past half semester. Any suggestion on how the course should proceed is welcomed.


==========================instructions====================================


Please participate in the mid-semester evaluation of CS courses and instructors.  I will not see the form you
submit but only a summary or compilation of the responses to each question.  You will thus be anonymous --
unless you put your name in a comment box, which you should NOT do.

Go to:

    https://portals.cs.purdue.edu/

log in using your Purdue career account ID and password,

click on "Course Evaluations", and then

click on  "Mid-Semester Evaluations".

The deadline is Sunday, October 21.

The form consists mostly of multiple-choice questions, but you will have the opportunity to make comments,
and you would do well to be prepared for that.

You should see all your current CS courses on the form.  If you enter anything for a course and submit the
form, the course will not appear if you ask for the form again.  Unmarked courses will appear again.

<signature>

Lecture 21. KMP algorithm and approximate string match

In this class, we finished KMP's algorithm for string matching. We also showed the connection between approximate string matching and calculating convolution between two sequences.

Grade Distribution of Midterm

Median 69
Average 67.3

Lecture 20 String Matching (2)

Today, we talked about the KMP algorithm for string matching. It improves the Finite Automata approach with a simpler pre-process.

Lecture 19 String Matching (1)

Today, we talked about how to find whether a string of length n has a substring of length m. We described an algorithm which runs in O(n) assuming that we can prepoccess the pattern.

Homework 1's grading

 It is 10pts for each problem.

The average is 41.36.

Lecture 18. Union Find (2)

Today, we finish the lecture on Union Find. In the end of the class, we had a pretty complicate proof for the log*n running time. If you are confused, have a look at the following page
http://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_Union_Find

The proof is not exactly accurate, but you can start read from the proof below the picture of many buckets.