ÿþ<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta http-equiv=Content-Type content="text/html; charset=unicode"> <meta name=ProgId content=Word.Document> <meta name=Generator content="Microsoft Word 12"> <meta name=Originator content="Microsoft Word 12"> <base href="http://www.cs.tau.ac.il/~orilahav/CompModelFall09/"> <link rel=File-List href="file:///C:\Users\Ori\Documents\html\CompModelFall09\comp_model09_files\filelist.xml"> <o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="place"/> <o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="PlaceName"/> <o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="PlaceType"/> <!--[if gte mso 9]><xml> <o:DocumentProperties> <o:Author>School of CS</o:Author> <o:Template>Normal</o:Template> <o:LastAuthor>Ori</o:LastAuthor> <o:Revision>99</o:Revision> <o:TotalTime>187</o:TotalTime> <o:Created>2009-10-13T07:45:00Z</o:Created> <o:LastSaved>2010-02-14T09:15:00Z</o:LastSaved> <o:Pages>2</o:Pages> <o:Words>1637</o:Words> <o:Characters>8188</o:Characters> <o:Company>Tel-Aviv University</o:Company> <o:Lines>68</o:Lines> <o:Paragraphs>19</o:Paragraphs> <o:CharactersWithSpaces>9806</o:CharactersWithSpaces> <o:Version>12.00</o:Version> </o:DocumentProperties> </xml><![endif]--> <link rel=themeData href="file:///C:\Users\Ori\Documents\html\CompModelFall09\comp_model09_files\themedata.thmx"> <link rel=colorSchemeMapping href="file:///C:\Users\Ori\Documents\html\CompModelFall09\comp_model09_files\colorschememapping.xml"> <!--[if gte mso 9]><xml> <w:WordDocument> <w:Zoom>130</w:Zoom> <w:SpellingState>Clean</w:SpellingState> <w:GrammarState>Clean</w:GrammarState> <w:TrackMoves>false</w:TrackMoves> <w:TrackFormatting/> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:DoNotPromoteQF/> <w:LidThemeOther>EN-US</w:LidThemeOther> <w:LidThemeAsian>X-NONE</w:LidThemeAsian> <w:LidThemeComplexScript>HE</w:LidThemeComplexScript> <w:Compatibility> <w:BreakWrappedTables/> <w:SnapToGridInCell/> <w:WrapTextWithPunct/> <w:UseAsianBreakRules/> <w:DontGrowAutofit/> <w:SplitPgBreakAndParaMark/> <w:DontVertAlignCellWithSp/> <w:DontBreakConstrainedForcedTables/> <w:DontVertAlignInTxbx/> <w:Word11KerningPairs/> <w:CachedColBalance/> </w:Compatibility> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> <m:mathPr> <m:mathFont m:val="Cambria Math"/> <m:brkBin m:val="before"/> <m:brkBinSub m:val="&#45;-"/> <m:smallFrac m:val="off"/> <m:dispDef/> <m:lMargin m:val="0"/> <m:rMargin m:val="0"/> <m:defJc m:val="centerGroup"/> <m:wrapIndent m:val="1440"/> <m:intLim m:val="subSup"/> <m:naryLim m:val="undOvr"/> </m:mathPr></w:WordDocument> </xml><![endif]--><!--[if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="false" DefSemiHidden="false" DefQFormat="false" LatentStyleCount="267"> <w:LsdException Locked="false" QFormat="true" Name="Normal"/> <w:LsdException Locked="false" QFormat="true" Name="heading 1"/> <w:LsdException Locked="false" QFormat="true" Name="heading 2"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 3"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 4"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 5"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 6"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 7"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 8"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 9"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="caption"/> <w:LsdException Locked="false" QFormat="true" Name="Title"/> <w:LsdException Locked="false" Priority="1" Name="Default Paragraph Font"/> <w:LsdException Locked="false" QFormat="true" Name="Subtitle"/> <w:LsdException Locked="false" Priority="99" Name="Hyperlink"/> <w:LsdException Locked="false" QFormat="true" Name="Strong"/> <w:LsdException Locked="false" QFormat="true" Name="Emphasis"/> <w:LsdException Locked="false" Priority="99" Name="No List"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" Name="Placeholder Text"/> <w:LsdException Locked="false" Priority="1" QFormat="true" Name="No Spacing"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading"/> <w:LsdException Locked="false" Priority="61" Name="Light List"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3"/> <w:LsdException Locked="false" Priority="70" Name="Dark List"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 1"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 1"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 1"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 1"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 1"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 1"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" Name="Revision"/> <w:LsdException Locked="false" Priority="34" QFormat="true" Name="List Paragraph"/> <w:LsdException Locked="false" Priority="29" QFormat="true" Name="Quote"/> <w:LsdException Locked="false" Priority="30" QFormat="true" Name="Intense Quote"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 1"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 1"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 1"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 1"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 1"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 1"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 1"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 1"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 2"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 2"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 2"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 2"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 2"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 2"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 2"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 2"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 2"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 2"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 2"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 2"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 2"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 2"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 3"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 3"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 3"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 3"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 3"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 3"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 3"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 3"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 3"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 3"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 3"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 3"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 3"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 3"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 4"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 4"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 4"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 4"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 4"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 4"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 4"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 4"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 4"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 4"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 4"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 4"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 4"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 4"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 5"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 5"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 5"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 5"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 5"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 5"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 5"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 5"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 5"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 5"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 5"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 5"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 5"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 5"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 6"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 6"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 6"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 6"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 6"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 6"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 6"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 6"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 6"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 6"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 6"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 6"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 6"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 6"/> <w:LsdException Locked="false" Priority="19" QFormat="true" Name="Subtle Emphasis"/> <w:LsdException Locked="false" Priority="21" QFormat="true" Name="Intense Emphasis"/> <w:LsdException Locked="false" Priority="31" QFormat="true" Name="Subtle Reference"/> <w:LsdException Locked="false" Priority="32" QFormat="true" Name="Intense Reference"/> <w:LsdException Locked="false" Priority="33" QFormat="true" Name="Book Title"/> <w:LsdException Locked="false" Priority="37" SemiHidden="true" UnhideWhenUsed="true" Name="Bibliography"/> <w:LsdException Locked="false" Priority="39" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="TOC Heading"/> </w:LatentStyles> </xml><![endif]--><!--[if !mso]><object classid="clsid:38481807-CA0E-42D2-BF39-B33AF135CC4D" id=ieooui></object> <style> st1\:*{behavior:url(#ieooui) } </style> <![endif]--> <style> <!--p.P6 {min-height: 14.0px;} p.P11 {min-height: 14.0px;} /* Font Definitions */ @font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-1610611985 1107304683 0 0 159 0;} @font-face {font-family:Times; panose-1:2 2 6 3 5 4 5 2 3 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-536859921 -1073711039 9 0 511 0;} @font-face {font-family:"Lucida Grande"; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-alt:"Times New Roman"; mso-font-charset:0; mso-generic-font-family:roman; mso-font-format:other; mso-font-pitch:auto; mso-font-signature:0 0 0 0 0 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin:0cm; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman";} h1 {mso-style-unhide:no; mso-style-qformat:yes; mso-style-link:"ÛÕêèê 1 êÕ"; mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; mso-outline-level:1; font-size:24.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} h2 {mso-style-unhide:no; mso-style-qformat:yes; mso-style-link:"ÛÕêèê 2 êÕ"; mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; mso-outline-level:2; font-size:18.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} a:link, span.MsoHyperlink {mso-style-priority:99; mso-style-unhide:no; color:blue; text-decoration:underline; text-underline:single;} a:visited, span.MsoHyperlinkFollowed {mso-style-unhide:no; color:blue; text-decoration:underline; text-underline:single;} span.1 {mso-style-name:"ÛÕêèê 1 êÕ"; mso-style-unhide:no; mso-style-locked:yes; mso-style-link:"ÛÕêèê 1"; mso-ansi-font-size:14.0pt; mso-bidi-font-size:14.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:major-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:major-fareast; mso-hansi-font-family:Cambria; mso-hansi-theme-font:major-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:major-bidi; color:#365F91; mso-themecolor:accent1; mso-themeshade:191; font-weight:bold;} span.2 {mso-style-name:"ÛÕêèê 2 êÕ"; mso-style-unhide:no; mso-style-locked:yes; mso-style-link:"ÛÕêèê 2"; mso-ansi-font-size:13.0pt; mso-bidi-font-size:13.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:major-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:major-fareast; mso-hansi-font-family:Cambria; mso-hansi-theme-font:major-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:major-bidi; color:#4F81BD; mso-themecolor:accent1; font-weight:bold;} p.p1, li.p1, div.p1 {mso-style-name:p1; mso-style-unhide:no; margin:0cm; margin-bottom:.0001pt; text-align:center; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman";} p.p2, li.p2, div.p2 {mso-style-name:p2; mso-style-unhide:no; margin-top:0cm; margin-right:0cm; margin-bottom:12.0pt; margin-left:0cm; text-align:center; mso-pagination:widow-orphan; font-size:18.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman";} p.p3, li.p3, div.p3 {mso-style-name:p3; mso-style-unhide:no; margin-top:0cm; margin-right:0cm; margin-bottom:12.0pt; margin-left:0cm; text-align:center; mso-pagination:widow-orphan; font-size:13.5pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman";} p.p4, li.p4, div.p4 {mso-style-name:p4; mso-style-unhide:no; margin-top:0cm; margin-right:0cm; margin-bottom:9.0pt; margin-left:0cm; text-align:center; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman";} p.p5, li.p5, div.p5 {mso-style-name:p5; mso-style-unhide:no; margin-top:0cm; margin-right:0cm; margin-bottom:9.0pt; margin-left:0cm; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman";} p.p6, li.p6, div.p6 {mso-style-name:p6; mso-style-unhide:no; margin-top:0cm; margin-right:0cm; margin-bottom:9.0pt; margin-left:0cm; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman";} p.p7, li.p7, div.p7 {mso-style-name:p7; mso-style-unhide:no; margin:0cm; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman";} p.p8, li.p8, div.p8 {mso-style-name:p8; mso-style-unhide:no; margin:0cm; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman"; color:red;} p.p9, li.p9, div.p9 {mso-style-name:p9; mso-style-unhide:no; margin-top:0cm; margin-right:0cm; margin-bottom:9.0pt; margin-left:0cm; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman"; color:#000CEE;} p.p10, li.p10, div.p10 {mso-style-name:p10; mso-style-unhide:no; margin:0cm; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman"; color:#000CEE;} p.p11, li.p11, div.p11 {mso-style-name:p11; mso-style-unhide:no; margin:0cm; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman";} p.p12, li.p12, div.p12 {mso-style-name:p12; mso-style-unhide:no; margin-top:0cm; margin-right:.75pt; margin-bottom:0cm; margin-left:.75pt; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:9.0pt; font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman";} p.style2, li.style2, div.style2 {mso-style-name:style2; mso-style-unhide:no; mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; color:white;} p.style4, li.style4, div.style4 {mso-style-name:style4; mso-style-unhide:no; mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; color:black;} p.p8style2, li.p8style2, div.p8style2 {mso-style-name:"p8 style2"; mso-style-unhide:no; mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman";} p.p8style4, li.p8style4, div.p8style4 {mso-style-name:"p8 style4"; mso-style-unhide:no; mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman";} span.s1 {mso-style-name:s1; mso-style-unhide:no; color:#000CEE; text-decoration:underline; text-underline:single;} span.s2 {mso-style-name:s2; mso-style-unhide:no; mso-ansi-font-size:7.5pt; mso-bidi-font-size:7.5pt; font-family:"Times","serif"; mso-ascii-font-family:Times; mso-hansi-font-family:Times; mso-bidi-font-family:Times;} span.s3 {mso-style-name:s3; mso-style-unhide:no; color:red;} span.s4 {mso-style-name:s4; mso-style-unhide:no; text-decoration:underline; text-underline:single;} span.s5 {mso-style-name:s5; mso-style-unhide:no; color:black; text-decoration:underline; text-underline:single;} span.s6 {mso-style-name:s6; mso-style-unhide:no; color:black;} span.s7 {mso-style-name:s7; mso-style-unhide:no; mso-ansi-font-size:9.0pt; mso-bidi-font-size:9.0pt; font-family:"Lucida Grande","serif"; mso-ascii-font-family:"Lucida Grande"; mso-hansi-font-family:"Lucida Grande";} span.s8 {mso-style-name:s8; mso-style-unhide:no; color:#000CEE;} span.apple-converted-space {mso-style-name:apple-converted-space; mso-style-unhide:no;} span.apple-style-span {mso-style-name:apple-style-span; mso-style-unhide:no;} span.il {mso-style-name:il; mso-style-unhide:no;} span.SpellE {mso-style-name:""; mso-spl-e:yes;} span.GramE {mso-style-name:""; mso-gram-e:yes;} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-size:10.0pt; mso-ansi-font-size:10.0pt; mso-bidi-font-size:10.0pt;} @page Section1 {size:595.3pt 841.9pt; margin:72.0pt 90.0pt 72.0pt 90.0pt; mso-header-margin:35.4pt; mso-footer-margin:35.4pt; mso-paper-source:0;} div.Section1 {page:Section1;} /* List Definitions */ @list l0 {mso-list-id:342512803; mso-list-template-ids:2091284160;} @list l0:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l0:level2 {mso-level-tab-stop:72.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l0:level3 {mso-level-tab-stop:108.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l0:level4 {mso-level-tab-stop:144.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l0:level5 {mso-level-tab-stop:180.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l0:level6 {mso-level-tab-stop:216.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l0:level7 {mso-level-tab-stop:252.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l0:level8 {mso-level-tab-stop:288.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l0:level9 {mso-level-tab-stop:324.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l1 {mso-list-id:451706628; mso-list-template-ids:830271050;} @list l1:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l1:level2 {mso-level-tab-stop:72.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l1:level3 {mso-level-tab-stop:108.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l1:level4 {mso-level-tab-stop:144.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l1:level5 {mso-level-tab-stop:180.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l1:level6 {mso-level-tab-stop:216.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l1:level7 {mso-level-tab-stop:252.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l1:level8 {mso-level-tab-stop:288.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l1:level9 {mso-level-tab-stop:324.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l2 {mso-list-id:854267182; mso-list-template-ids:-1703086354;} @list l2:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l2:level2 {mso-level-tab-stop:72.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l2:level3 {mso-level-tab-stop:108.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l2:level4 {mso-level-tab-stop:144.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l2:level5 {mso-level-tab-stop:180.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l2:level6 {mso-level-tab-stop:216.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l2:level7 {mso-level-tab-stop:252.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l2:level8 {mso-level-tab-stop:288.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l2:level9 {mso-level-tab-stop:324.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l3 {mso-list-id:1495412964; mso-list-template-ids:-839601778;} @list l3:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l3:level2 {mso-level-tab-stop:72.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l3:level3 {mso-level-tab-stop:108.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l3:level4 {mso-level-tab-stop:144.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l3:level5 {mso-level-tab-stop:180.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l3:level6 {mso-level-tab-stop:216.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l3:level7 {mso-level-tab-stop:252.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l3:level8 {mso-level-tab-stop:288.0pt; mso-level-number-position:left; text-indent:-18.0pt;} @list l3:level9 {mso-level-tab-stop:324.0pt; mso-level-number-position:left; text-indent:-18.0pt;} ol {margin-bottom:0cm;} ul {margin-bottom:0cm;} --> </style> <!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"ØÑÜÔ èÒÙÜÔ"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman","serif";} table.MsoTableList3 {mso-style-name:"èéÙÞÔ ÑØÑÜÔ 3"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-unhide:no; border-top:solid black 1.5pt; border-left:none; border-bottom:solid black 1.5pt; border-right:none; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-border-insideh:.75pt solid black; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman","serif";} table.MsoTableList3FirstRow {mso-style-name:"èéÙÞÔ ÑØÑÜÔ 3"; mso-table-condition:first-row; mso-style-unhide:no; mso-tstyle-border-bottom:1.5pt solid black; mso-tstyle-diagonal-down:none; mso-tstyle-diagonal-up:none; color:navy; mso-ansi-font-weight:bold; mso-bidi-font-weight:bold;} table.MsoTableList3LastRow {mso-style-name:"èéÙÞÔ ÑØÑÜÔ 3"; mso-table-condition:last-row; mso-style-unhide:no; mso-tstyle-border-top:1.5pt solid black; mso-tstyle-diagonal-down:none; mso-tstyle-diagonal-up:none;} table.MsoTableList3SWCell {mso-style-name:"èéÙÞÔ ÑØÑÜÔ 3"; mso-table-condition:sw-cell; mso-style-unhide:no; mso-tstyle-diagonal-down:none; mso-tstyle-diagonal-up:none; color:navy; mso-ansi-font-style:italic; mso-bidi-font-style:italic;} table.MsoTableElegant {mso-style-name:"ØÑÜÔ ÐÜÒàØÙê"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-unhide:no; border:double black 2.25pt; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-border-insideh:.75pt solid black; mso-border-insidev:.75pt solid black; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman","serif";} table.MsoTableElegantFirstRow {mso-style-name:"ØÑÜÔ ÐÜÒàØÙê"; mso-table-condition:first-row; mso-style-unhide:no; mso-tstyle-diagonal-down:none; mso-tstyle-diagonal-up:none; color:windowtext; text-transform:uppercase;} table.TableNormal {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-unhide:no; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman","serif";} </style> <![endif]--> <meta http-equiv=Content-Style-Type content="text/css"> <meta name=CocoaVersion content=949.46> <!--[if gte mso 9]><xml> <o:shapedefaults v:ext="edit" spidmax="56322"/> </xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext="edit"> <o:idmap v:ext="edit" data="1"/> </o:shapelayout></xml><![endif]--> </head> <body lang=EN-US link=blue vlink=blue style='tab-interval:36.0pt'> <div class=Section1> <p class=p1><st1:PlaceType w:st="on"><span style='font-size:11.0pt'>School</span></st1:PlaceType><span style='font-size:11.0pt'> of <st1:PlaceName w:st="on">Computer</st1:PlaceName> Science, <st1:place w:st="on"><st1:PlaceName w:st="on">Tel</st1:PlaceName> <st1:PlaceName w:st="on">Aviv</st1:PlaceName> <st1:PlaceType w:st="on">University</st1:PlaceType></st1:place><o:p></o:p></span></p> <h1 align=center style='margin-top:0cm;margin-right:0cm;margin-bottom:12.0pt; margin-left:0cm;text-align:center;font-size-adjust: none;font-stretch: normal; -x-system-font: none'><span style='font-size:20.0pt;font-family:"Times","serif"; mso-fareast-font-family:"Times New Roman"'>Computational Models</span><span style='font-size:20.0pt;font-family:"Times","serif";mso-fareast-font-family: "Times New Roman";font-weight:normal'><o:p></o:p></span></h1> <p class=p4><b><span style='font-size:11.0pt'>0368.2200</span></b><span style='font-size:11.0pt'><o:p></o:p></span></p> <p class=p4><span style='font-size:11.0pt'>Fall 2009<o:p></o:p></span></p> <p class=p5><span style='font-size:11.0pt'>The course is being taught in two groups:<o:p></o:p></span></p> <p class=p5><span style='font-size:11.0pt'>(a) Monday 13-16 (<span class=SpellE>Dach</span> 005), with two recitations on Wednesday 15-16 (Schreiber&nbsp;007), 16-17 (Schreiber&nbsp;007).<o:p></o:p></span></p> <p class=p5><span style='font-size:11.0pt'>(b) Thursday 16-19 (<span class=SpellE>Dach</span> 005), with two recitations on Tuesday 13-14 (<span class=SpellE>Shenkar</span> 222), 14-15 (<span class=SpellE>Shenkar</span> 222).<o:p></o:p></span></p> <p class=p5><b><span style='font-size:11.0pt'>Lecturers</span></b><span style='font-size:11.0pt'>: <a href="http://www.cs.tau.ac.il/~kempe/">Dr. Julia <span class=SpellE>Kempe</span></a> (1<sup>st</sup> half of the course) and <a href="http://www.cs.tau.ac.il/~nachumd/Homepage.html">Prof. <span class=SpellE>Nachum</span> <span class=SpellE>Dershowitz</span></a> (2<sup>nd</sup> half of the course)<o:p></o:p></span></p> <p class=p5><b><span style='font-size:11.0pt'>Group (a) Teaching Assistant</span></b><span style='font-size:11.0pt'>: <a href="http://www.cs.tau.ac.il/~orilahav">Mr. <span class=SpellE>Ori</span> <span class=SpellE>Lahav</span></a> <o:p></o:p></span></p> <p class=p5><b><span style='font-size:11.0pt'>Group (b) Teaching Assistant</span></b><span style='font-size:11.0pt'>: <a href="http://www.cs.tau.ac.il/~jonatha6">Mr. Jonathan <span class=SpellE>Berant</span></a><o:p></o:p></span></p> <p class=p5><b><span style='font-size:11.0pt'>Grader</span></b><span style='font-size:11.0pt'>: <span class=SpellE>Demitry</span> Lev (mail box 300) (<span class=SpellE>demitryl</span>  at post.tau.ac.il)<o:p></o:p></span></p> <p class=p5><b><span style='font-size:11.0pt'>Exam</span></b><span style='font-size:11.0pt'>: <span class=SpellE>Moed</span> <span class=GramE>A</span> 10/02/2010. <span class=SpellE>Moed</span> B 10/08/2010.<o:p></o:p></span></p> <p class=p5><span style='font-size:11.0pt'>Note: The recitations are taught concurrently in two groups. While there will be some differences in presentation style and details, the material to be covered is the same. Homework assignments and final exams will be identical for both groups. Note that the recitation on Tuesday (Jonathan's) will cover the material of the previous week Thursday lecture.<o:p></o:p></span></p> <p class=p5><span style='font-size:11.0pt'><o:p>&nbsp;</o:p></span></p> <p class=p7><b><span style='font-size:11.0pt'>Class Bulletin-Board<br style='mso-special-character:line-break'> <![if !supportLineBreakNewLine]><br style='mso-special-character:line-break'> <![endif]><o:p></o:p></span></b></p> <table class=MsoTableList3 border=1 cellspacing=0 cellpadding=0 style='border-collapse:collapse;border:none;mso-border-top-alt:solid black 1.5pt; mso-border-bottom-alt:solid black 1.5pt;mso-yfti-tbllook:1184;mso-padding-alt: 0cm 5.4pt 0cm 5.4pt'> <tr style='mso-yfti-irow:-1;mso-yfti-firstrow:yes'> <td width=70 valign=top style='width:52.5pt;border-top:solid black 1.5pt; border-left:none;border-bottom:solid black 1.5pt;border-right:none; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 style='mso-yfti-cnfc:1'><span style='font-size:11.0pt;color:navy'>Date<b><o:p></o:p></b></span></p> </td> <td width=699 valign=top style='width:524.25pt;border-top:solid black 1.5pt; border-left:none;border-bottom:solid black 1.5pt;border-right:none; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 style='mso-yfti-cnfc:1'><span style='font-size:11.0pt;color:navy'>Announcement<b><o:p></o:p></b></span></p> </td> </tr> <tr style='mso-yfti-irow:0'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>18/10/09<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7><span style='font-size:11.0pt'>Welcome to computational models, fall 09', we hope you have a wonderful semester!<o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:1'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>10/11/09<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span class=apple-style-span><span lang=HE style='font-size:10.0pt;font-family: "Arial","sans-serif";color:black'>ÔêèÒÙÜ ÑÞÕÓÜÙÝ ×ÙéÕÑÙÙÝ çÑÕæÔ 05</span></span><span dir=LTR></span><span class=apple-converted-space><span dir=LTR style='font-size:10.0pt;font-family:"Arial","sans-serif";color:black'><span dir=LTR></span>&nbsp;</span></span><span class=apple-style-span><span lang=HE style='font-size:10.0pt;font-family:"Arial","sans-serif";color:black'>éàÙêß â&quot;Ù ÜÔÑ ÐÕèÙ ÑÙÞÙ Ó' ÑéâÕê 15:00-16:00</span></span><span dir=LTR></span><span class=apple-converted-space><span dir=LTR style='font-size:10.0pt;font-family: "Arial","sans-serif";color:black'><span dir=LTR></span>&nbsp;</span></span><span class=apple-style-span><span lang=HE style='font-size:10.0pt;font-family: "Arial","sans-serif";color:black'>ÔÕâÑè ÑÐÕäß çÑÕâ ÜéèÙÙÑè 007</span></span><span dir=LTR style='font-size:11.0pt'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:2'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>10/11/09<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7><span style='font-size:11.0pt'>You are welcome to try </span><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'><a href="http://wareseeker.com/Home-Education/visual-automata-simulator-1.2.1.zip/1faeddbd7" target="_blank"><span style='color:#2A5DB0'>http://wareseeker.com/Home</span><span style='color:#2A5DB0'>-</span><wbr><span style='color:#2A5DB0'>Education/visual-automata</span><span style='color:#2A5DB0'>-</span><wbr><span style='color:#2A5DB0'>simulator-1.2.1.zip/1faeddbd7</span></a></span></span><span class=apple-converted-space><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; mso-fareast-font-family:"Times New Roman";mso-fareast-theme-font:major-fareast; color:black'>&nbsp;</span></span><span style='font-size:11.0pt'><o:p></o:p></span></p> <p class=p7><span style='font-size:11.0pt'>It is nice Java application; supports NFA, DFA and conversions between the two; supports Turing machines</span><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'><o:p></o:p></span></span></p> </td> </tr> <tr style='mso-yfti-irow:3'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>11/11/09<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>ÜÞÙ éÔÙÔ ÑêèÒÕÜ ÔÙÕÝ (ÙÕÝ èÑÙâÙ) ÑéâÔ 15:00 - âéÙêÙ ØâÕê ÑÔÕÛ×Ô ÑÓÕÒÞÔ éÜ ÜÞê ÔàÙäÕ× ÜéäÕê ×áèÕê Ôçéè. ÜÐ ÔêÙÙ×áàÕ ÜâÕÑÓÔ é-</span><b><span dir=LTR style='font-size:11.0pt'>v</span></b><span dir=RTL></span><b><span lang=HE style='font-size:11.0pt'><span dir=RTL></span> ÙÛÕÜ ÜÔÙÕê èÙç</span></b><span lang=HE style='font-size:11.0pt'>. ×éÑÕ ÛÙæÓ àÙêß ÜØäÜ ÑÞçèÔ ÖÔ (éÙÞÕ ÜÑ éàÕÑâ ÞÛÚ ÞÙÙÓÙê é-</span><span dir=LTR style='font-size:11.0pt'>y</span><span dir=RTL></span><span lang=HE style='font-size:11.0pt'><span dir=RTL></span> ÜÐ èÙç). äàÕ ÐÜÙ ÐÝ ÖÔ ÜÐ ÔáêÓè. èÐÕ ÒÝ ÔÕÛ×Ô éÜ ØâàÔ ÖÕ Ñéçã 34 ÑÞæÒê 4. ÐÕèÙ.</span><span dir=LTR style='font-size:11.0pt'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:4'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>18/11/09<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>êÕçàÔ ØâÕê Ñéçã 19 ÑÞæÒê éÜ ÔèæÐÔ 4. ÑÞæÒê ÔçÕÓÞê ÔÙÔ </span><span dir=LTR style='font-size:11.0pt'>star S ’! µ | SS&quot;</span><span dir=RTL></span><span lang=HE style='font-size:11.0pt'><span dir=RTL></span>&quot; ÜÜÐ ÔêÕáäê éÑáÕÒèÙÙÝ ÑéÕèÕê ÔÐ×èÕàÕê.</span><span dir=LTR style='font-size:11.0pt'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:5'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>29/12/09<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>ÔÒéê êèÒÙÜ 4 àÓ×Ùê ÑÞáäè ÙÞÙÝ (èÐÕ ÑØÑÜÔ ÜÞØÔ). ÐÑÜ, ÜÐ êÔÙÔ Ó×ÙÙÔ ÑÞÕâÓ ÔÔÒéÔ éÜ êèÒÙÜ 5.</span><span dir=LTR style='font-size:11.0pt'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:6'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>03/01/10<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>èÞÖ ÜéÐÜÔ </span><span dir=LTR></span><span dir=LTR style='font-size:11.0pt'><span dir=LTR></span>1g</span><span dir=RTL></span><span lang=HE style='font-size:11.0pt'><span dir=RTL></span> ÑêèÒÙÜ 5: &quot;ÔÙáØÕèÙÔ ×ÙéÕÑÙê&quot;.</span><span dir=LTR style='font-size:11.0pt'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:7'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>08/01/10<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>ÔÜÙàç ÔÑÐ âéÕÙ ÜÔÙÕê ÞâàÙÙß ÐÕ ÞÕâÙÜ âÑÕèÛÝ:</span><span class=apple-style-span><span dir=LTR style='font-family:"Arial","sans-serif"; color:black'><o:p></o:p></span></span></p> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span class=apple-style-span><span lang=HE style='font-size:10.0pt;font-family: "Arial","sans-serif";color:black'><a href="http://video.google.com/videoplay?docid=2727170905577830475" target="_blank"><span lang=EN-US dir=LTR style='color:#2A5DB0'>http://video.google.com</span><span lang=EN-US dir=LTR style='color:#2A5DB0'>/</span><wbr><span lang=EN-US dir=LTR style='color:#2A5DB0'>videoplay?docid</span><span lang=EN-US dir=LTR style='color:#2A5DB0'>=</span><wbr><span lang=EN-US dir=LTR style='color: #2A5DB0'>2727170905577830475#</span></a></span></span><span class=apple-style-span><span dir=LTR><o:p></o:p></span></span></p> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>ÔÜÙàç ÔÑÐ ÞáÛÝ ÑÐÕäß ä×Õê ÞçÕÑÜ Ðê Ð×ê ÔÔÕÛ×Õê Ô×éÕÑÕê ÑçÕèá:</span><span dir=LTR style='font-size:11.0pt'><o:p></o:p></span></p> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span class=apple-style-span><span lang=HE style='font-size:10.0pt;font-family: "Arial","sans-serif";color:black'><a href="http://www.cs.rice.edu/~vardi/comp409/scooping.pdf" target="_blank"><span lang=EN-US dir=LTR style='color:#2A5DB0'>http://www.cs.rice.edu/~vardi</span><span lang=EN-US dir=LTR style='color:#2A5DB0'>/</span><wbr><span lang=EN-US dir=LTR style='color:#2A5DB0'>comp409/scooping.pdf</span></a></span></span><span dir=LTR style='font-size:11.0pt'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:8'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>19/01/10<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>êèÒÕÜ ÔéÜÞÔ ÜçÑÕæÕê éÜ ÙÕàêß ÙÙâèÚ ÑÙÕÝ éÙéÙ ÔçèÕÑ ÑéâÔ 12 ÑéèÙÙÑè 7</span><span dir=LTR style='font-size:11.0pt'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:9'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>23/01/10<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>Óã ÔÕèÐÕê ÜÞÑ×ß  ÐàÐ çèÐÕ  <a href="MoedA09Cover.pdf">âÞÕÓ èÐéÕß</a></span><span dir=LTR style='font-size: 11.0pt'><o:p></o:p></span></p> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>ÑàÕáã  ÑçÕÑå ÖÔ êÞæÐÕ ÞÑ×àÙÝ ÙéàÙÝ ÜéÙÞÕéÛÝ </span><span class=apple-style-span><span lang=HE style='font-size:7.5pt; font-family:"Arial","sans-serif";color:black'> </span></span><span class=apple-style-span><span lang=HE style='font-size:11.5pt;font-family: "Times New Roman","serif";mso-ascii-theme-font:major-bidi;mso-hansi-theme-font: major-bidi;mso-bidi-theme-font:major-bidi;color:black'><a href="exams_modelim.zip">ÞÑ×àÙÝ ÙéàÙÝ</a></span></span><span dir=LTR style='font-size:11.0pt;background:yellow;mso-highlight:yellow'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:10'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>04/02/10<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>êèÒÕÜ ×ÖèÔ ÙÕâÑè â&quot;Ù ÙÔÕàêß ÑÙÕÝ éàÙ ÑéâÕê </span><span dir=LTR></span><span dir=LTR style='font-size:11.0pt'><span dir=LTR></span>16-18</span><span dir=RTL></span><span lang=HE style='font-size:11.0pt'><span dir=RTL></span> ÑÐÕÜÝ ÞÜÞÓ 6.</span><span dir=LTR style='font-size:11.0pt'><o:p></o:p></span></p> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'>ÐêÝ ÞÕÖÞàÙÝ ÜéÜÕ× ÜÙÔÕàêß éÐÜÕê éêèæÕ éÙäêÕè ÑêèÒÕÜ.</span><span dir=LTR style='font-size:11.0pt;background:yellow; mso-highlight:yellow'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:11'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>14/02/10<o:p></o:p></span></p> </td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.0pt;mso-border-top-alt:solid black .75pt;mso-border-top-alt: solid black .75pt;mso-border-bottom-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 dir=RTL style='text-align:right;direction:rtl;unicode-bidi:embed'><span lang=HE style='font-size:11.0pt'><a href="EXAMsol.pdf">äêèÕß ÞçÕæè éÜ ÞÕâÓ Ð'</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:12;mso-yfti-lastrow:yes'> <td width=70 style='width:52.5pt;border:none;border-bottom:solid black 1.5pt; mso-border-top-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'></td> <td width=699 valign=top style='width:524.25pt;border:none;border-bottom: solid black 1.5pt;mso-border-top-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'></td> </tr> </table> <p class=MsoNormal><span style='font-size:14.0pt;display:none;mso-hide:all'><o:p>&nbsp;</o:p></span></p> <p class=p7><span style='font-size:11.0pt'><o:p>&nbsp;</o:p></span></p> <p class=p7><b><span style='font-size:11.0pt'>Homework Assignments<br style='mso-special-character:line-break'> <![if !supportLineBreakNewLine]><br style='mso-special-character:line-break'> <![endif]><o:p></o:p></span></b></p> <table class=MsoTableElegant border=1 cellspacing=0 cellpadding=0 width=1000 style='width:750.15pt;border-collapse:collapse;border:none;mso-border-alt: double black 2.25pt;mso-border-bottom-alt:solid windowtext .5pt;mso-yfti-tbllook: 1184;mso-padding-alt:0cm 5.4pt 0cm 5.4pt'> <tr style='mso-yfti-irow:-1;mso-yfti-firstrow:yes'> <td width=122 style='width:91.25pt;border-top:double 2.25pt;border-left:double 2.25pt; border-bottom:solid 1.0pt;border-right:solid 1.0pt;border-color:black; mso-border-top-alt:double 2.25pt;mso-border-left-alt:double 2.25pt; mso-border-bottom-alt:solid .75pt;mso-border-right-alt:solid .75pt; mso-border-color-alt:black;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center;mso-yfti-cnfc:1'><b><span style='font-size:11.0pt;text-transform:uppercase'>Assignment<o:p></o:p></span></b></p> </td> <td width=132 style='width:98.8pt;border-top:double black 2.25pt;border-left: none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt; mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; mso-border-top-alt:double black 2.25pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center;mso-yfti-cnfc:1'><b><span style='font-size:11.0pt;text-transform:uppercase'>date handed<o:p></o:p></span></b></p> </td> <td width=208 style='width:155.8pt;border-top:double black 2.25pt;border-left: none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt; mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; mso-border-top-alt:double black 2.25pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center;mso-yfti-cnfc:1'><b><span style='font-size:11.0pt;text-transform:uppercase'>due date<o:p></o:p></span></b></p> </td> <td width=133 style='width:99.55pt;border-top:double black 2.25pt;border-left: none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt; mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; mso-border-top-alt:double black 2.25pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center;mso-yfti-cnfc:1'><b><span style='font-size:11.0pt;text-transform:uppercase'>solution<o:p></o:p></span></b></p> </td> <td width=406 style='width:304.75pt;border-top:double black 2.25pt; border-left:none;border-bottom:solid black 1.0pt;border-right:double black 2.25pt; mso-border-left-alt:solid black .75pt;mso-border-top-alt:double 2.25pt; mso-border-left-alt:solid .75pt;mso-border-bottom-alt:solid .75pt;mso-border-right-alt: double 2.25pt;mso-border-color-alt:black;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center;mso-yfti-cnfc:1'><b><span style='font-size:11.0pt;text-transform:uppercase'>Remarks<o:p></o:p></span></b></p> </td> </tr> <tr style='mso-yfti-irow:0'> <td width=122 style='width:91.25pt;border-top:none;border-left:double black 2.25pt; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-alt:solid black .75pt;mso-border-left-alt:double black 2.25pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="ex1.pdf">Ex1</a><o:p></o:p></span></p> </td> <td width=132 style='width:98.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>27/10<o:p></o:p></span></p> </td> <td width=208 style='width:155.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>11/11 10:00<o:p></o:p></span></p> </td> <td width=133 style='width:99.55pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="sol1.pdf">Sol1</a><o:p></o:p></span></p> </td> <td width=406 style='width:304.75pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:double black 2.25pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; mso-border-right-alt:double black 2.25pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>Note that only 1d<span class=GramE>,1e,2,3b,4b,5b,5c,6a</span> were graded.<o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:1'> <td width=122 style='width:91.25pt;border-top:none;border-left:double black 2.25pt; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-alt:solid black .75pt;mso-border-left-alt:double black 2.25pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="ex2.pdf">Ex2</a><o:p></o:p></span></p> </td> <td width=132 style='width:98.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>11/11<o:p></o:p></span></p> </td> <td width=208 style='width:155.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>25/11 13:00<o:p></o:p></span></p> </td> <td width=133 style='width:99.55pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="sol2.pdf">Sol2</a><o:p></o:p></span></p> </td> <td width=406 style='width:304.75pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:double black 2.25pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; mso-border-right-alt:double black 2.25pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>Only 2a 4b 4d 4e 5b 5c 6 7a were graded.<o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:2'> <td width=122 style='width:91.25pt;border-top:none;border-left:double black 2.25pt; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-alt:solid black .75pt;mso-border-left-alt:double black 2.25pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="ex3.pdf">Ex3</a><o:p></o:p></span></p> </td> <td width=132 style='width:98.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>25/11<o:p></o:p></span></p> </td> <td width=208 style='width:155.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>9/12 13:00<o:p></o:p></span></p> </td> <td width=133 style='width:99.55pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="sol3.pdf">Sol3</a><o:p></o:p></span></p> </td> <td width=406 style='width:304.75pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:double black 2.25pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; mso-border-right-alt:double black 2.25pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>Only 2<span class=GramE>,3b,3d,4a,4b,4c,5a,6a</span> were graded.<o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:3'> <td width=122 style='width:91.25pt;border-top:none;border-left:double black 2.25pt; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-alt:solid black .75pt;mso-border-left-alt:double black 2.25pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="ex4.pdf">Ex4</a><o:p></o:p></span></p> </td> <td width=132 style='width:98.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>09/12<o:p></o:p></span></p> </td> <td width=208 style='width:155.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><s><span style='font-size: 11.0pt'>30/12 13:00<o:p></o:p></span></s></p> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>03/01 13:00<o:p></o:p></span></p> </td> <td width=133 style='width:99.55pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="sol4.pdf">Sol4</a><o:p></o:p></span></p> </td> <td width=406 style='width:304.75pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:double black 2.25pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; mso-border-right-alt:double black 2.25pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'><span style='mso-spacerun:yes'> </span>Only 1a&nbsp;2a&nbsp;3b&nbsp;3e&nbsp;3f&nbsp;3g&nbsp;4a&nbsp;4b&nbsp;5&nbsp;6c&nbsp;6d&nbsp;6f&nbsp;6g were graded.<o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:4'> <td width=122 style='width:91.25pt;border-top:none;border-left:double black 2.25pt; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-alt:solid black .75pt;mso-border-left-alt:double black 2.25pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="ex5.pdf">Ex5</a><o:p></o:p></span></p> </td> <td width=132 style='width:98.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>23/12<o:p></o:p></span></p> </td> <td width=208 style='width:155.8pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>13/01 13:00<o:p></o:p></span></p> </td> <td width=133 style='width:99.55pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="sol5.pdf">Sol5</a><o:p></o:p></span></p> </td> <td width=406 style='width:304.75pt;border-top:none;border-left:none; border-bottom:solid black 1.0pt;border-right:double black 2.25pt;mso-border-top-alt: solid black .75pt;mso-border-left-alt:solid black .75pt;mso-border-alt:solid black .75pt; mso-border-right-alt:double black 2.25pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>Only 1a<span class=GramE>,1c,1d,1g,1h,1j,2b,4</span> were graded.<o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:5;mso-yfti-lastrow:yes'> <td width=122 style='width:91.25pt;border-top:none;border-left:double black 2.25pt; border-bottom:solid windowtext 1.0pt;border-right:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-top-alt:solid black .75pt; mso-border-left-alt:double black 2.25pt;mso-border-bottom-alt:solid windowtext .5pt; mso-border-right-alt:solid black .75pt;padding:0cm 5.4pt 0cm 5.4pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="ex6.pdf">Ex6</a><o:p></o:p></span></p> </td> <td width=132 style='width:98.8pt;border-top:none;border-left:none; border-bottom:solid windowtext 1.0pt;border-right:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-left-alt:solid black .75pt; mso-border-alt:solid black .75pt;mso-border-bottom-alt:solid windowtext .5pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>12/01<o:p></o:p></span></p> </td> <td width=208 style='width:155.8pt;border-top:none;border-left:none; border-bottom:solid windowtext 1.0pt;border-right:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-left-alt:solid black .75pt; mso-border-alt:solid black .75pt;mso-border-bottom-alt:solid windowtext .5pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>27/01 13:00<o:p></o:p></span></p> </td> <td width=133 style='width:99.55pt;border-top:none;border-left:none; border-bottom:solid windowtext 1.0pt;border-right:solid black 1.0pt; mso-border-top-alt:solid black .75pt;mso-border-left-alt:solid black .75pt; mso-border-alt:solid black .75pt;mso-border-bottom-alt:solid windowtext .5pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="sol6.pdf">Sol6</a><o:p></o:p></span></p> </td> <td width=406 style='width:304.75pt;border-top:none;border-left:none; border-bottom:solid windowtext 1.0pt;border-right:double black 2.25pt; mso-border-top-alt:solid black .75pt;mso-border-left-alt:solid black .75pt; mso-border-top-alt:solid black .75pt;mso-border-left-alt:solid black .75pt; mso-border-bottom-alt:solid windowtext .5pt;mso-border-right-alt:double black 2.25pt; padding:0cm 5.4pt 0cm 5.4pt'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>Only 1a<span class=GramE>,1c,1e,1g,1i</span> were graded.<o:p></o:p></span></p> </td> </tr> </table> <p class=p5><span style='font-size:11.0pt'><br> Your solution should be handed to the grader's mail box at the time and date specified. You can collect your checked home assignments from room 114.<o:p></o:p></span></p> <p class=p5><b><span style='font-size:11.0pt'>Course Timetable</span></b><span style='font-size:11.0pt'><o:p></o:p></span></p> <table class=TableNormal border=1 cellspacing=0 cellpadding=0 width=793 style='width:594.95pt;mso-cellspacing:0cm;border:solid black 2.25pt; mso-yfti-tbllook:1184;mso-padding-alt:0cm 0cm 0cm 0cm;mso-border-insideh:.5pt solid windowtext; mso-border-insidev:.5pt solid windowtext'> <tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><b><span style='font-size: 11.0pt'>Week</span></b><span style='font-size:11.0pt'><o:p></o:p></span></p> </td> <td width=382 style='width:286.8pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p12 align=center style='text-align:center'><b><span style='font-size:11.0pt'>Subject</span></b><span style='font-size:11.0pt'><o:p></o:p></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><b><span style='font-size: 11.0pt'>Reference(s)</span></b><span style='font-size:11.0pt'><o:p></o:p></span></p> </td> <td width=161 valign=top style='width:120.45pt;border:solid windowtext 1.0pt; mso-border-alt:solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p7 align=center style='text-align:center'><b><span style='font-size: 11.0pt'>Lecture Slides</span></b><span style='font-size:11.0pt'> (<span class=SpellE>pdf</span>)<o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:1'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span dir=RTL></span><span lang=HE dir=RTL style='font-size:11.0pt'><span dir=RTL></span>1</span><span style='font-size:11.0pt'><o:p></o:p></span></p> </td> <td width=382 valign=top style='width:286.8pt;border:solid windowtext 1.0pt; mso-border-alt:solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Administratrivia</span></span></span><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>. Overview. Preliminaries. Finite automata. Regular languages. Closure properties: Union.</span></span><span style='font-size:11.0pt'><o:p></o:p></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 0, 1.1<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute1_Intro-ju1_print.pdf">Intro</a><o:p></o:p></span></p> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute1_DFA_print.pdf">Lecture_1</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:2'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>2<o:p></o:p></span></p> </td> <td width=382 valign=top style='width:286.8pt;border:solid windowtext 1.0pt; mso-border-alt:solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Non-Deterministic Finite Automata (NFA). Closure properties of Regular Languages. Regular expressions and their equivalence with finite automata via generalized NFAs</span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif";color:black'>.<o:p></o:p></span></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 1.1-1.3<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute2-juprint.pdf">Lecture_2</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:3'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>3<o:p></o:p></span></p> </td> <td width=382 valign=top style='width:286.8pt;border:solid windowtext 1.0pt; mso-border-alt:solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Regular expressions and their equivalence with finite automata via generalized NFAs. Dealing with Non-regular languages: <span class=SpellE>Myhill-Nerode</span> Theorem and Examples. The Pumping Lemma. Algorithmic questions for NFA.</span><o:p></o:p></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 1.4, 4.1<o:p></o:p></span></p> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Hopcroft</span></span><span style='font-size:11.0pt'> and <span class=SpellE>Ullman</span> 3.4<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute3-juprint.pdf">Lecture_3</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:4'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>4<o:p></o:p></span></p> </td> <td width=382 valign=top style='width:286.8pt;border:solid windowtext 1.0pt; mso-border-alt:solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Context free grammars. Closure under union, concatenation, and star. Linear grammars. Ambiguity. CFL pumping lemma. Non context free languages. Push-down automata. The equivalence theorem (statement).</span><o:p></o:p></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 2.1-2.3<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute4-juprint.pdf">Lecture_4</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:5'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>5<o:p></o:p></span></p> </td> <td width=382 valign=top style='width:286.8pt;border:solid windowtext 1.0pt; mso-border-alt:solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Non-Determinism adds power to PDAs. Chomsky normal form of CFGs. More CFL closure properties. Some algorithmic questions for CFGs. Equivalence of Context Free Grammars and Push down automata.</span><o:p></o:p></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 2.1-2.2<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute5-juprint.pdf">Lecture_5</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:6'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>6<o:p></o:p></span></p> </td> <td width=382 valign=top style='width:286.8pt;border:solid windowtext 1.0pt; mso-border-alt:solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Turing Machines and alternative Models of Computers, Non Deterministic TMs</span></span><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:red'>.</span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif"; color:red'><o:p></o:p></span></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 3.1-3.3<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute6-juprint.pdf">Lecture_6</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:7'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>7<o:p></o:p></span></p> </td> <td width=382 valign=top style='width:286.8pt;border:solid windowtext 1.0pt; mso-border-alt:solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>The language classes R, RE and <span class=SpellE>coRE</span>. What is an algorithm?</span></span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'><br> <span class=apple-style-span>The Church-Turing Thesis.</span> <span class=apple-style-span>Hilbert's tenth problem</span><br> <span class=apple-style-span>Encoding of Turing Machines. Universal Turing Machine. </span></span><span class=apple-style-span><span style='font-family: "Arial","sans-serif";color:black'><o:p></o:p></span></span></p> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>The halting problem</span></span>. <span class=SpellE><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Diagonalization</span></span></span><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:red'><o:p></o:p></span></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 3.3,4.1,4.2<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute7-juprint.pdf">Lecture_7</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:8'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>8<o:p></o:p></span></p> </td> <td width=382 style='width:286.8pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Review of <span class=SpellE>Diagonalization</span>. The acceptance and halting problems are <span class=SpellE>undecidable</span> (<span class=SpellE>diagonalization</span> proof<span class=GramE>)</span></span><br> </span><span class=apple-style-span><span style='font-size:10.0pt;font-family: "Arial","sans-serif";color:black'>Computable functions. </span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif"; color:black'><o:p></o:p></span></span></p> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>The busy beaver function is not computable (not in book).</span></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 4.1,4.2,5.1<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute8-juprint.pdf">Lecture_8</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:9'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>9<o:p></o:p></span></p> </td> <td width=382 style='width:286.8pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=MsoNormal align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Additional <span class=SpellE>Undecidable</span> Languages, Reductions among languages, Mapping reductions</span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif"; color:red'><o:p></o:p></span></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 5.1,5.3<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute9-juprint.pdf">Lecture 9</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:10'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>10<o:p></o:p></span></p> </td> <td width=382 style='width:286.8pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=MsoNormal align=center style='text-align:center'><span class=SpellE><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Undecidability</span></span></span><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:black'> by Rice Theorem,</span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif";color:black'><o:p></o:p></span></span></p> <p class=MsoNormal align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Reductions by computational histories</span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif"; color:black'><o:p></o:p></span></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 5.1,5.3<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute10x_print.pdf">Lecture10</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:11'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>11<o:p></o:p></span></p> </td> <td width=382 style='width:286.8pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>The classes P, NP. Examples of Problems in NP.</span></span><span class=apple-style-span><span style='font-size:12.0pt;font-family:"Arial","sans-serif"; color:black'><o:p></o:p></span></span></p> <p class=MsoNormal align=center style='text-align:center'><span class=SpellE><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Veriûability</span></span></span><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:black'>.</span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif"; color:black'><o:p></o:p></span></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 7.2,7.3<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute11x.pdf">Lecture11</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:12'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>12<o:p></o:p></span></p> </td> <td width=382 style='width:286.8pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>The classes NP and <span class=SpellE>coNP</span>. Examples of Problems in NP. <span class=SpellE>Veriûability</span>. Poly-Time Reductions. NP completeness</span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif";color:black'><o:p></o:p></span></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'> 7.3,7.4,7.5<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute12x.pdf">Lecture12</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:13'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>13<o:p></o:p></span></p> </td> <td width=382 style='width:286.8pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>NP hardness. <span class=SpellE><span class=GramE>coNP</span></span> and <span class=SpellE>coNP</span> completeness.</span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif"; color:black'><o:p></o:p></span></span></p> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Additional reductions and NP complete problems.</span></span><span class=apple-style-span><span style='font-family:"Arial","sans-serif"; color:black'><o:p></o:p></span></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=SpellE><span style='font-size:11.0pt'>Sipser</span></span><span style='font-size:11.0pt'>, chapter7<o:p></o:p></span></p> <p class=p7 align=center style='text-align:center'><span style='font-size: 10.0pt'>(some material not covered)<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Compute13x.pdf">Lecture13</a><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:14;mso-yfti-lastrow:yes'> <td width=80 style='width:60.1pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p1><span style='font-size:11.0pt'>14<o:p></o:p></span></p> </td> <td width=382 style='width:286.8pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>Summary of some complexity classes with examples.<br> Graph isomorphism is not NPC implies P </span></span><span class=apple-style-span><span style='font-size:10.0pt;font-family:Symbol; mso-ascii-font-family:Arial;mso-hansi-font-family:Arial;mso-bidi-font-family: Arial;color:black;mso-char-type:symbol;mso-symbol-font-family:Symbol'><span style='mso-char-type:symbol;mso-symbol-font-family:Symbol'>¹</span></span></span><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'> NP.<br> <span class=SpellE>Undecidability</span> of Halt implies incompleteness of logic.<br> Church Turing thesis revisited. Oracles. Penrose</span> </span><span class=apple-style-span><span style='font-size:10.0pt;font-family:"Arial","sans-serif"; color:black'>argument</span>.<o:p></o:p></span></p> </td> <td width=170 style='width:127.6pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 0cm 0cm 0cm'> <p class=p7 align=center style='text-align:center'><span style='font-size: 11.0pt'>Not covered.<o:p></o:p></span></p> </td> <td width=161 style='width:120.45pt;border:solid windowtext 1.0pt;mso-border-alt: solid windowtext .5pt;padding:0cm 4.5pt 0cm 4.5pt'> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="hAOpg.pdf">Lecture14</a>a<o:p></o:p></span></p> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'><a href="Last.pdf">Lecture14b</a><o:p></o:p></span></p> <p class=p10 align=center style='text-align:center'><span style='font-size: 11.0pt'>(partial)<o:p></o:p></span></p> </td> </tr> </table> <p class=p5><span style='font-size:11.0pt'><br> <b>Course requirements and important information</b>:<o:p></o:p></span></p> <ul style='margin-top:0cm' type=disc> <li class=MsoNormal style='mso-list:l1 level1 lfo1;tab-stops:list 36.0pt'><span style='font-size:11.0pt;font-family:"Times","serif"'>6 homework assignments, to be handed individually. <o:p></o:p></span></li> </ul> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'>A random half of the homework will be checked and graded.<o:p></o:p></span></p> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'>The homework assignments will constitute 10% of the final grade.<o:p></o:p></span></p> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'><o:p>&nbsp;</o:p></span></p> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'>These 10% will be calculated as follows:<o:p></o:p></span></p> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'><span style='mso-tab-count:1'>            </span>If (average 5 best grades &gt; 49) then grade = average 5 best grades,<o:p></o:p></span></p> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'><span style='mso-tab-count:1'>            </span>Else grade = 0<o:p></o:p></span></p> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'><o:p>&nbsp;</o:p></span></p> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'>Late submission will be allowed only given proper approval (note from a doctor, etc.) <o:p></o:p></span></p> <p class=MsoNormal style='margin-left:18.0pt;text-indent:18.0pt'><span style='font-size:11.0pt;font-family:"Times","serif"'>One day extension will be given for every day of illness. 1.5 days will be given for every day of reserve duty.<o:p></o:p></span></p> <p class=MsoNormal style='text-indent:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'>Less than 5 grades will be used, if the solution is published within this extension period. <o:p></o:p></span></p> <p class=MsoNormal style='margin-left:18.0pt;text-indent:18.0pt'><span style='font-size:11.0pt;font-family:"Times","serif"'><o:p>&nbsp;</o:p></span></p> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'>External sources (books, web pages) can be used but should be clearly quoted. Assignment submission is usually due two weeks after publishing. Solving assignments independently is crucial and is strongly encouraged. <o:p></o:p></span></p> <p class=MsoNormal style='margin-left:36.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'><o:p>&nbsp;</o:p></span></p> <ul style='margin-top:0cm' type=disc> <li class=MsoNormal style='mso-list:l0 level1 lfo2;tab-stops:list 36.0pt; font-size-adjust: none;font-stretch: normal;-x-system-font: none'><b><u><span style='font-size:11.0pt;font-family:"Times","serif"'>No</span></u></b><span style='font-size:11.0pt;font-family:"Times","serif"'> midterm exam<b>.</b><o:p></o:p></span></li> <li class=MsoNormal style='mso-list:l0 level1 lfo2;tab-stops:list 36.0pt; font-size-adjust: none;font-stretch: normal;-x-system-font: none'><span style='font-size:11.0pt;font-family:"Times","serif"'>Course grade = 10% based on homework assignments, 90% on final exam.<o:p></o:p></span></li> </ul> <p class=MsoNormal style='margin-left:18.0pt'><span style='font-size:11.0pt; font-family:"Times","serif"'><o:p>&nbsp;</o:p></span></p> <p class=p5><b><span style='font-size:11.0pt'>Course Outline</span></b><span style='font-size:11.0pt'> The course deals with fundamental questions of computer science:<o:p></o:p></span></p> <ul style='margin-top:0cm' type=disc> <li class=MsoNormal style='mso-list:l3 level1 lfo3;tab-stops:list 36.0pt; font-size-adjust: none;font-stretch: normal;-x-system-font: none'><span style='font-size:11.0pt;font-family:"Times","serif"'>What is a computer?<o:p></o:p></span></li> <li class=MsoNormal style='mso-list:l3 level1 lfo3;tab-stops:list 36.0pt; font-size-adjust: none;font-stretch: normal;-x-system-font: none'><span style='font-size:11.0pt;font-family:"Times","serif"'>What can computers do (and what can they not do)?<o:p></o:p></span></li> <li class=MsoNormal style='mso-list:l3 level1 lfo3;tab-stops:list 36.0pt; font-size-adjust: none;font-stretch: normal;-x-system-font: none'><span style='font-size:11.0pt;font-family:"Times","serif"'>Why are some problems computationally hard, while very similar ones are computationally easy?<o:p></o:p></span></li> </ul> <p class=p7><span style='font-size:11.0pt'>These questions were mostly raised during the 20th century, and they accompanied and guided the actual development of computers.<o:p></o:p></span></p> <p class=p7><span style='font-size:11.0pt'>Many of these and related questions were resolved, but some (especially those dealing with computational hardness) retained their status as &quot;key open problems&quot; into the 21st century.<o:p></o:p></span></p> <p class=p5><span style='font-size:11.0pt'>&nbsp;<b><br> Prerequisites:</b> The course is a required course for Computer Science students, and &quot;extended intro to Computer Science&quot; is a prerequisite. &quot;Discrete Math&quot; is recommended, though not required. Students from other disciplines are encouraged to contact the lecturer.</span><b><span style='font-size:11.0pt;font-family:"Lucida Grande","serif"'><br> <br> </span></b><b><span style='font-size:11.0pt'>Textbook</span></b><span style='font-size:11.0pt'> &nbsp;</span><b><span style='font-size:11.0pt; font-family:"Lucida Grande","serif"'><o:p></o:p></span></b></p> <p class=p5><i><span style='font-size:11.0pt'>Introduction to the Theory of Computation</span></i><span style='font-size:11.0pt'>, M. <span class=SpellE>Sipser</span>,&nbsp;<i>PWS Publishing Co</i>.,<span class=GramE>&nbsp; 1997</span> (second edition, 2005).<o:p></o:p></span></p> <p class=p5><b><span style='font-size:11.0pt'>Reference Books<o:p></o:p></span></b></p> <ul style='margin-top:0cm' type=disc> <li class=MsoNormal style='mso-list:l2 level1 lfo4;tab-stops:list 36.0pt; font-size-adjust: none;font-stretch: normal;-x-system-font: none'><i><span style='font-size:11.0pt;font-family:"Times","serif"'>Computational Complexity</span></i><span style='font-size:11.0pt;font-family:"Times","serif"'>, C. Papadimitriou, <i>Addison-Wesley Publishing Co.</i>,<span class=GramE>&nbsp; 1994</span>.<o:p></o:p></span></li> <li class=MsoNormal style='mso-list:l2 level1 lfo4;tab-stops:list 36.0pt; font-size-adjust: none;font-stretch: normal;-x-system-font: none'><i><span style='font-size:11.0pt;font-family:"Times","serif"'>Elements of the Theory of Computation, </span></i><span style='font-size:11.0pt; font-family:"Times","serif"'>H. Lewis and C. Papadimitriou, <i>Prentice-Hall</i>, 1981.<o:p></o:p></span></li> <li class=MsoNormal style='mso-list:l2 level1 lfo4;tab-stops:list 36.0pt; font-size-adjust: none;font-stretch: normal;-x-system-font: none'><i><span style='font-size:11.0pt;font-family:"Times","serif"'>Introduction to Automata Theory, Languages, and Computation</span></i><span style='font-size:11.0pt;font-family:"Times","serif"'>, J. <span class=SpellE>Hopcroft</span> and J. <span class=SpellE>Ullman</span>, <i>Addison-Wesley Publishing Co.</i>, 1979.<o:p></o:p></span></li> <li class=MsoNormal style='mso-list:l2 level1 lfo4;tab-stops:list 36.0pt; font-size-adjust: none;font-stretch: normal;-x-system-font: none'><span style='font-size:11.0pt;font-family:"Times","serif"'>Automata and formal languages, the open university (in Hebrew<span class=GramE>) ,</span> 1991.<o:p></o:p></span></li> </ul> <p class=p11><span style='font-size:11.0pt'><o:p>&nbsp;</o:p></span></p> <p class=p5><b><span style='font-size:11.0pt'>Previous course sites<o:p></o:p></span></b></p> <p class=p11><a href="http://www.cs.tau.ac.il/~bchor/CM09/compute.html">http://www.cs.tau.ac.il/~bchor/CM09/compute.html</a><span style='font-size:11.0pt'><o:p></o:p></span></p> <p class=p11><a href="http://www.cs.tau.ac.il/~jonatha6/Computational%20Models%20-%20fall%202008.html">http://www.cs.tau.ac.il/~jonatha6/Computational%20Models%20-%20fall%202008.html</a><span style='font-size:11.0pt'><o:p></o:p></span></p> <p class=p11><span style='font-size:11.0pt'><o:p>&nbsp;</o:p></span></p> </div> </body> </html>