[-] שאלה 1-ב
by yonatana - Tuesday, 8 May 2012 13:55:13
הוכחת האלגוריתם האיטרטיבי:
לפי המקום נראה כי נדרשת רק הוכחה שהריצה אפשרית בזמן הנדרש, כלומר שהחישוב של M אפשרי, ולא הוכחה מלאה לנכונות האלגוריתם. 
האם זאת כוונתכם? 
thread
Re: שאלה 1-ב
by taig - Tuesday, 8 May 2012 17:53:36
No. Not related to the running time, you have extra space for that. The correctness proof is based on:
1. The correctness of the formula (which you prove separately).
2. Each time the algorithm is computing opt(v) all the needed entries for the computation were already calculated (this is what you should prove here).
thread