COMPSCI 170 Study Guide - Midterm Guide: Umesh Vazirani, Dynamic Programming, Linear Programming
Document Summary
Write down the names of the students around you as they appear on their sid. Note: for each question part, 20% of the points will be given to any blank answer, or to any clearly crossed- out answer. Note: if you nish in the last 15 minutes, please remain seated and not leave early, to not distract your fellow classmates. Instructions: you may consult one handwritten, two-sided sheet of notes. You may not consult other notes, textbooks, etc. Cell phones and other electronic devices are not permitted. On questions asking for an algorithm, make sure to respond in the format we request. Do not turn this page until an instructor tells you to do so. Maximum spanning tree (i) find a maximum spanning tree of the graph below (indicate it by circling the weights of the edges included in the spanning tree). Linear programming fundamentals min 2x1 + 4x2 x1 + x2 30.
