Announcement: AWC 400 Level Lecture SeriesThe AWC will be running its 400 level lecture series (400 LLS) onOctober 17,18 and 19 (5-6pm) in CSIC 3117. FREE FOOD.Professors who will be teaching the 400 level courses in the spring will each spend 15 minutes talking about what material the course will cover and how they intend to run it. This is a great opportunity to help you determine which 400 level course you will be interested in taking next semester. Schedule:TuesdayKruskal 451Getoor 421Pop 423WednesdayHick 412Golbeck 498NZelkowitz 430Washington 456ThursdayJacobs 427Hugue 420Duraiswami 460Lower BoundsFinding a value in a list with Divide and Conquer:Any Divide and Conquer algorithm that recurses both sides has this form: T(n) = T(an) + T((1-a)n) + b, where minimum value of b = 1.The “Simplex” problem in linear algebra is an interesting one to consider.• algorithms exist with polynomial expected runtime, but this doesn’t change the upper bound of the problem• people came up with new pivot rules for the Dantzig algorithm, but there has always been some input that would force the algorithm to run in exponential time• the question of whether a pivot rule exists that would not have any cases end up leading to worse than polynomial time is still (as far as I know) an open
View Full Document
Unlocking...