COMP 251 Study Guide - Final Guide: Dynamic Programming, Optimal Substructure, Glossary Of Ancient Roman Religion

• School: McGill University
• Department: Computer Science (Sci)
• Course: COMP 251
• Professor: Michel Lapointe

Document Summary

This is a collection of problems that you can use to prepare the comp 251 nal exam. This selection of problems covers the second part of the class (i. e. after the mid-term exam). However, the nal exam will also cover the material of the rst part of the class. Please, refer to the practice problems for the mid-term and solution of the midterm (lecture 24) to prepare this component. Dynamic programming: the coin row problem: suppose you have a row of coins with values that are positive integers c1, , cn. Your task is to pick up coins have as much total value as possible, subject to the constraint that you don?t ever pick up two coins that lie beside each other. Solve the problem for coins with values c1 to c6 as follows: (5, 1, 2, 10, 6, 2). Solution: the idea for the recurrence is as follows. You either pick it up or you don?t.