Category Archives: fall 2011

Roadmap for today’s class Look at the weighted interval scheduling problem. Devise an algorithm for the problem. Analyze the algorithm’s runtime. Modify the algorithm slightly to dramatically improve the runtime. Step back and observe how memoization, which is at the … Continue reading →

In this lecture, we spent the whole time trying to solve the weighted interval scheduling problem using Dynamic Programming. Let’s look at the details: Weighted Interval Scheduling (WIS): 1       |———-V1=2———|               … Continue reading →

Kick ass Lemma:   If   s= s’  S s.t d(s,s’)< S             =>  s and s’ are within 15 positions of each other in S     Q                 … Continue reading →

 Proof of lemma                                                                                                                                                             Kick ass Lemma   If Ǝ s= s’ Є S s * t d(s,s’) < S             =>  s and s’ are within 15 positions of each other in S   … Continue reading →

The lecture discusses about finding the pair of closes pair of points in a graph. //Start algorithm The first step is to sort the points by both axis, and let the sorted lists for x and y axis be Px and … Continue reading →

We spent all of lecture today going through the algorithm to find the closes pair of any amount of 2-D points (represented by x and y coordinates, and closest referring to smallest Euclidian distance). By the end of class, we … Continue reading →

Homework 8 Solutions will be handed out at the end of the class Homework 7 is graded and available for pickup There are two review sessions this week: Tuesday Review Session 1-1:50 Jesse Commons 9 (Review of covered material, Post … Continue reading →

There will be two review sessions, as follows: Tuesday from 1:00 – 1:50 in Comons 9, proctored by Jesse Friday from 11:30 – 12:20 in Bell 242, proctored by Atri Bring specific questions. Todays lecture was divided into two sections, … Continue reading →

Poster: Jim Dobler So today we saw a story of hope, hope dashed and reborn anew. Our input: n distinct numbers a1…an. Our goal, to count the number of inversions, defined as a pair (i,j) where i a_j. No mean … Continue reading →

Atri announced a possible review session. He and Jesse will each have a 1 hour session on subject material chosen by the online survey. Last class we went over how to do multiplication in O(n^2) time and this class we … Continue reading →