Announcement AWC 400 Level Lecture Series The AWC will be running its 400 level lecture series 400 LLS on October 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 Tuesday Kruskal 451 Getoor 421 Pop 423 Wednesday Hick 412 Golbeck 498N Zelkowitz 430 Washington 456 Thursday Jacobs 427 Hugue 420 Duraiswami 460 Lower Bounds Finding 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 one
View Full Document
Unlocking...