https://www.ocf.berkeley.edu/~shidi/cs61a/w/api.php?action=feedcontributions&user=Axis&feedformat=atomCS 61A Wiki - User contributions [en]2024-03-29T00:35:35ZUser contributionsMediaWiki 1.22.6https://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Past_examsPast exams2014-12-08T04:51:12Z<p>Axis: add su14 final</p>
<hr />
<div>This is a list of '''past exams'''.<br />
<br />
{| class="wikitable" border="1"<br />
|-<br />
! Semester<br />
! MT1<br />
! MT2<br />
! Final<br />
|-<br />
! Fall 2011<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test1-solutions.pdf|sol}}<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test2-solutions.pdf|sol}}<br />
|<br />
|-<br />
! Summer 2014<br />
| {{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1.pdf|exam}} ({{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1-sol.pdf|sol}})<br />
{{Plain link|https://docs.google.com/a/berkeley.edu/document/d/1DYjptJtKeWpGuWcFWADza0mADC3CMEaX3778dZpolZU/|env diagrams}}<br />
| {{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hxmdrtyyder49a/hkppg6doems102/i3fcek7u13ee/61asu14midterm2.pdf|exam}} ({{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hxmdrtyyder49a/hkppg6doems102/i3fca2dak3bj/61asu14midterm2_solutions.pdf|sol}})<br />
{{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hx2jz3h2i112h8/hkppg6doems102/i1sdqa1ejx6r/q3.pdf|(q3 sol)}}<br />
{{Plain link|http://goo.gl/rpb3wy|(q2b sol)}}<br />
| {{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hxmdrtyyder49a/hkppg6doems102/i3fcouxga40y/61asu14final.pdf|exam}} ({{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hxmdrtyyder49a/hkppg6doems102/i3fd0rep17w8/61asu14final_sol.pdf|sol}})<br />
|-<br />
! Fall 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1-solution.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt2-solution.pdf|sol}})<br />
| <br />
|}<br />
<br />
== Other Exams ==<br />
* [http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3.pdf Summer 2014 Exam 3] ([http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3_sol.pdf Solutions])<br />
<br />
[[Category:Logistical articles]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Past_examsPast exams2014-12-08T04:33:33Z<p>Axis: update su14 MT2 links</p>
<hr />
<div>This is a list of '''past exams'''.<br />
<br />
{| class="wikitable" border="1"<br />
|-<br />
! Semester<br />
! MT1<br />
! MT2<br />
! Final<br />
|-<br />
! Fall 2011<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test1-solutions.pdf|sol}}<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test2-solutions.pdf|sol}}<br />
|<br />
|-<br />
! Summer 2014<br />
| {{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1.pdf|exam}} ({{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1-sol.pdf|sol}})<br />
{{Plain link|https://docs.google.com/a/berkeley.edu/document/d/1DYjptJtKeWpGuWcFWADza0mADC3CMEaX3778dZpolZU/|env diagrams}}<br />
| {{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hxmdrtyyder49a/hkppg6doems102/i3fcek7u13ee/61asu14midterm2.pdf|exam}} ({{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hxmdrtyyder49a/hkppg6doems102/i3fca2dak3bj/61asu14midterm2_solutions.pdf|sol}})<br />
{{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hx2jz3h2i112h8/hkppg6doems102/i1sdqa1ejx6r/q3.pdf|(q3 sol)}}<br />
{{Plain link|http://goo.gl/rpb3wy|(q2b sol)}}<br />
|<br />
|-<br />
! Fall 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1-solution.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt2-solution.pdf|sol}})<br />
| <br />
|}<br />
<br />
== Other Exams ==<br />
* [http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3.pdf Summer 2014 Exam 3] ([http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3_sol.pdf Solutions])<br />
<br />
[[Category:Logistical articles]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Past_examsPast exams2014-10-31T12:47:01Z<p>Axis: fix</p>
<hr />
<div>This is a list of '''past exams'''.<br />
<br />
{| class="wikitable" border="1"<br />
|-<br />
! Semester<br />
! MT1<br />
! MT2<br />
! Final<br />
|-<br />
! Fall 2011<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test1-solutions.pdf|sol}}<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test2-solutions.pdf|sol}}<br />
|<br />
|-<br />
! Summer 2014<br />
| {{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1.pdf|exam}} ({{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1-sol.pdf|sol}})<br />
{{Plain link|https://docs.google.com/a/berkeley.edu/document/d/1DYjptJtKeWpGuWcFWADza0mADC3CMEaX3778dZpolZU/|env diagrams}}<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm2_sol.pdf|sol}})<br />
{{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hx2jz3h2i112h8/hkppg6doems102/i1sdqa1ejx6r/q3.pdf|(q3 sol)}}<br />
{{Plain link|http://goo.gl/rpb3wy|(q2b sol)}}<br />
|<br />
|-<br />
! Fall 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1-solution.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt2-solution.pdf|sol}})<br />
| <br />
|}<br />
<br />
== Other Exams ==<br />
* [http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3.pdf Summer 2014 Exam 3] ([http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3_sol.pdf Solutions])<br />
<br />
[[Category:Logistical articles]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Past_examsPast exams2014-10-31T12:46:20Z<p>Axis: add fa14 MT2</p>
<hr />
<div>This is a list of '''past exams'''.<br />
<br />
{| class="wikitable" border="1"<br />
|-<br />
! Semester<br />
! MT1<br />
! MT2<br />
! Final<br />
|-<br />
! Fall 2011<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test1-solutions.pdf|sol}}<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test2-solutions.pdf|sol}}<br />
|<br />
|-<br />
! Summer 2014<br />
| {{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1.pdf|exam}} ({{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1-sol.pdf|sol}})<br />
{{Plain link|https://docs.google.com/a/berkeley.edu/document/d/1DYjptJtKeWpGuWcFWADza0mADC3CMEaX3778dZpolZU/|env diagrams}}<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm2_sol.pdf|sol}}) {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1-solution.pdf|sol}})<br />
{{Plain link|https://d1b10bmlvqabco.cloudfront.net/attach/hx2jz3h2i112h8/hkppg6doems102/i1sdqa1ejx6r/q3.pdf|(q3 sol)}}<br />
{{Plain link|http://goo.gl/rpb3wy|(q2b sol)}}<br />
|<br />
|-<br />
! Fall 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1-solution.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt2-solution.pdf|sol}})<br />
| <br />
|}<br />
<br />
== Other Exams ==<br />
* [http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3.pdf Summer 2014 Exam 3] ([http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3_sol.pdf Solutions])<br />
<br />
[[Category:Logistical articles]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Past_examsPast exams2014-09-27T18:29:46Z<p>Axis: add fa14 MT1</p>
<hr />
<div>This is a list of '''past exams'''.<br />
<br />
{| class="wikitable" border="1"<br />
|-<br />
! Semester<br />
! MT1<br />
! MT2<br />
! Final<br />
|-<br />
! Fall 2011<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa11-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su12-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2012<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm1-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-solutions.pdf|sol}})<br />
{{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt.pdf|alt}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-midterm2-alt-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa12-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-sp13-final-solutions.pdf|sol}})<br />
|-<br />
! Summer 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-su13-final-solutions.pdf|sol}})<br />
|-<br />
! Fall 2013<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm1-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-midterm2-solutions.pdf|sol}})<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/sp14/exams/61a-fa13-final-solutions.pdf|sol}})<br />
|-<br />
! Spring 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test1-solutions.pdf|sol}}<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/sp14-test2-solutions.pdf|sol}}<br />
|<br />
|-<br />
! Summer 2014<br />
| {{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1.pdf|exam}} ({{Plain link|http://www.ocf.berkeley.edu/~shidi/cs61a/61a-su14-midterm1-sol.pdf|sol}})<br />
{{Plain link|https://docs.google.com/a/berkeley.edu/document/d/1DYjptJtKeWpGuWcFWADza0mADC3CMEaX3778dZpolZU/|env diagrams}}<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm2.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm2_sol.pdf|sol}})<br />
|<br />
|-<br />
! Fall 2014<br />
| {{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1.pdf|exam}} ({{Plain link|http://inst.eecs.berkeley.edu/~cs61a/fa14/assets/pdfs/61a-fa14-mt1-solution.pdf|sol}})<br />
| <br />
| <br />
|}<br />
<br />
== Other Exams ==<br />
* [http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3.pdf Summer 2014 Exam 3] ([http://inst.eecs.berkeley.edu/~cs61a/su14/exams/61a-su14-midterm3_sol.pdf Solutions])<br />
<br />
[[Category:Logistical articles]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/PythonPython2014-09-19T04:34:57Z<p>Axis: /* Boolean */ clarify</p>
<hr />
<div>{{Start-class}}<br />
'''Python''' is the main programming language for 61A. {{Basics sidebar}}<br />
== Basics ==<br />
* [http://en.wikibooks.org/wiki/Python_Programming Python Programming]<br />
* [http://www.cogsci.rpi.edu/~destem/igd/python_cheat_sheet.pdf Python cheatsheet]<br />
<br />
== Data types ==<br />
Every value is an object. The following are the most commonly used Python data types:<br />
<br />
=== Number ===<br />
A number can be an ''integer'' or a ''float''. An integer can be converted to a float using the <code>float()</code> constructor, and a float can be converted to an integer using the <code>int()</code> constructor.<br />
<br />
Examples:<br />
<syntaxhighlight lang="python"><br />
>>> 2 # integer<br />
2<br />
>>> 2.0 # float<br />
2.0<br />
>>> int(2.0)<br />
2<br />
>>> float(2)<br />
2.0<br />
</syntaxhighlight><br />
<br />
=== Boolean ===<br />
A ''boolean'' has only two possible values: <code>True</code> or <code>False</code>. The type of a boolean is <code>bool</code>. Comparison operators return booleans:<br />
<syntaxhighlight lang="python"><br />
>>> 1 > 2<br />
False<br />
>>> 1 < 2<br />
True<br />
>>> 's' == 's'<br />
True<br />
</syntaxhighlight><br />
<br />
In a boolean context, all values evaluate to <code>True</code> except the following, which evaluate to <code>False</code>:<br />
<syntaxhighlight lang="python"><br />
None<br />
0<br />
""<br />
[]<br />
()<br />
{}<br />
set()<br />
</syntaxhighlight><br />
<br />
=== String ===<br />
{{Main|Sequence#String}}<br />
<br />
=== Tuple ===<br />
{{Main|Sequence#Tuple}}<br />
<br />
=== List ===<br />
{{Main|Sequence#List}}<br />
<br />
=== Dictionary ===<br />
{{Main|Dictionary}}<br />
<br />
=== Set ===<br />
{{Main|Set}}<br />
<br />
== Operators ==<br />
{{Main|Operator}}<br />
<br />
== Statements and expressions ==<br />
Computer programs are generally made up of statements and expressions:<br />
* [[Statement]]s carry out actions. A program ''executes'' a statement. Examples include the <code>def</code>, <code>import</code>, <code>return</code>, and assignment (<code>=</code>) statements.<br />
* [[Expression]]s compute some value. A program ''evaluates'' an expression. Expressions can include anything from primitives (<code>True</code>, <code>2</code>, <code>3</code>, <code>2.0</code>) to lengthy call expressions.<br />
<br />
== Function call ==<br />
A function call is executed in the following way:<br />
* create a new local frame<br />
* bind arguments to formal parameters in that frame<br />
* execute the body<br />
<br />
==Iteration==<br />
{{Main|Iteration}}<br />
Iteration is the process of repeatedly executing a block of code.<br />
<br />
==Command Line==<br />
{{Workflow sidebar}}<br />
To start a Python interpreter, one can just type python3 into the command line, or the name of the command that leads to the Python 3 program:<br />
<syntaxhighlight lang="bash"><br />
python3<br />
</syntaxhighlight><br />
<br />
To run a Python file, one should include the file path. Any additional arguments provided can be accessed via <code>sys.argv</code>.<br />
<syntaxhighlight lang="bash"><br />
python3 path/to/file.py<br />
python3 path/to/file.py arg1 arg2 ...<br />
</syntaxhighlight><br />
<br />
To run a Python file and then continue execution with an interactive session, add the <code>-i</code> flag.<br />
<syntaxhighlight lang="bash"><br />
python3 -i path/to/file.py<br />
</syntaxhighlight><br />
<br />
==Testing==<br />
Python has a lot of built-in support for testing. The two testing modules used for this course are <code>doctest</code> and <code>unittest</code>.<br />
* [[Doctest]] - Find docstrings that model interactive sessions and compare the output specified in the docstrings to the actual output from the program.<br />
* [[Unittest]] - Organize test code into units and then run the units together, logging the tests that succeeded and the ones that failed.</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/RecursionRecursion2014-08-16T05:27:20Z<p>Axis: /* Example */ fix</p>
<hr />
<div>{{C-class}}<br />
'''Recursion''' is a technique for solving a large computational problem by repeatedly applying the same procedure(s) to reduce it to successively smaller problems. A recursive procedure has two parts: one or more ''base cases'' and a ''recursive step''. Base cases are predetermined solutions for the simplest versions of the problem — if the given problem is a base case, no further computation is necessary to get the result. The recursive step is a set of rules that eventually reduces all versions of the problem to one of the base cases when applied repeatedly.<br />
<br />
''Infinite recursion'' occurs if there is no base case or the recursive step does not make progress towards its base case(s).<br />
<br />
Example for how a recursive function looks:<br />
<syntaxhighlight lang="python"><br />
def fn(input):<br />
if <base case>:<br />
return ...<br />
else:<br />
return <combine input and fn(input_reduced)><br />
</syntaxhighlight><br />
<br />
<br />
==Simple recursion==<br />
In simple recursion — the most straightforward and common form of recursion — there is usually only one base case, and in the recursive step, the recursive procedure calls itself only once. <br />
<br />
===Analogy===<br />
Consider this procedure for learning the definition of recursion: "If you are Andrew Huang, you already know the definition. If not, find someone who is standing closer to Andrew Huang than you are and ask them what the definition of recursion is." Here, the base case is being Andrew Huang — once you reach this situation, no further work is necessary to get the definition of recursion. If you are not yet at a base case, the recursive step is to ask someone who is closer to Andrew, reducing the problem closer to the base case.<br />
<br />
Let's call the procedure <code>def_recursion</code>. We can think about it in terms of the ''stack'' from [[environment diagram]]s. Suppose Matthew, Rohin, and Andrew are standing in a line. Matthew wants to know the definition of recursion, so his call to <code>def_recursion</code> is pushed onto the stack. He isn't Andrew, so must find someone standing closer to Andrew than he is and ask them for the definition. So Matthew asks Rohin for the definition of recursion. Rohin's call to the ''same'' <code>def_recursion</code> function is pushed on top of Matthew's call. Rohin is also not Andrew, so he must ask someone standing closer to Andrew than he is — in this case, it's Andrew himself. Now Andrew's call to <code>def_recursion</code> is pushed on top of Rohin's call. <br />
<br />
Andrew is a base case, so he already knows the definition and immediately returns it to Rohin, and Andrew's frame pops off the stack. Now Rohin has the definition of recursion, which he can return to Matthew. Once he returns, Rohin's frame pops off the stack. Now Matthew's frame is the only one on the stack, and he has the definition of recursion. This was the initial goal, so Matthew's frame can return and pop off, leaving the stack empty.<br />
<br />
In pseudocode, <code>def_recursion</code>, which takes in the person who wants to know the definition of recursion as a parameter, can be written like this:<br />
<br />
<syntaxhighlight lang="python"><br />
def def_recursion(you):<br />
if you == AndrewHuang:<br />
return knowledge<br />
else:<br />
return def_recursion(someone closer to AndrewHuang)<br />
</syntaxhighlight><br />
<br />
Notice that in the recursive step, the same procedure is called again, but on a simpler version of the problem every time. If there were no base case (no one knew what recursion was), or the recursive step didn't make the problem smaller (everyone asked people ''further'' from Andrew what the answer was), then the recursion can malfunction and go into an infinite loop.<br />
<br />
===Examples===<br />
An example of simple recursion is the <code>factorial</code> function:<br />
<br />
<syntaxhighlight lang="python"><br />
def factorial(n):<br />
if n == 0:<br />
return 1<br />
else:<br />
return n * factorial(n - 1)<br />
</syntaxhighlight><br />
<br />
Notice that the <code>factorial</code> procedure is called only once in the body of the recursive procedure. However, it is possible for a call to the function to appear in multiple places in the function body — if only one of those calls is ever executed in each frame, the function still exhibits simple recursion. For example, consider the function that raises a base <code>b</code> to a power <code>p</code> through a recursive procedure called ''repeated squaring'':<br />
<br />
<syntaxhighlight lang="python"><br />
def pow(b, p):<br />
if p == 0:<br />
return 1<br />
elif p % 2 == 0:<br />
x = pow(b, p // 2)<br />
return x * x<br />
else:<br />
x = pow(b, p // 2)<br />
return b * x * x<br />
</syntaxhighlight><br />
<br />
Here, the recursive call to <code>pow</code> appears twice — once in the <code>elif</code> clause, once in the <code>else</code> clause. However, the whole procedure is still simply recursive, because only ''one'' of those else clauses is ever triggered in each recursive call, meaning the procedure can only ever call itself once per frame.<br />
<br />
==Tree recursion==<br />
A [[function]] is ''tree recursive'' if the recursive step contains more than one call to the same function. Tree recursive functions generally have more base cases than simply recursive functions as well, though this is not a necessary condition. If a tree recursive function makes repeated computations, it is more optimal to store previous return values rather than perform expensive recomputations. This technique can be implemented through [[memoization]].<br />
<br />
===Analogy===<br />
A tree recursive procedure can naturally be used to answer the question "How many ancestors do I have, up to a certain number of generations?" One natural way to answer this question is to say "I have a mother and a father, making two ancestors. Additionally, my mother's ancestors are my ancestors, and my father's ancestors are my ancestors." Consider the following pseudocode:<br />
<br />
<syntaxhighlight lang="python"><br />
def num_ancestors(you, num_gen):<br />
if num_gen == 0:<br />
return 0<br />
else:<br />
return 2 + num_ancestors(mom, num_gen - 1) + num_ancestors(dad, num_gen - 1)<br />
</syntaxhighlight><br />
<br />
The base case occurs when we only care about ancestors 0 generations up — that is, when we only care about <code>you</code>. Since you have no ancestors who are 0 generations older than you, we return 0. The recursive call then adds up your parents' ancestors, and adds 2 for your parents themselves. <br />
<br />
If we wanted to count up all your ancestors two generations up, we would start with a call to <code>num_ancestors(you, 2)</code>. In order to compute that, we need to computer <code>num_ancestors(your_mom, 1)</code> and <code>num_ancestors(your_dad, 1)</code>. In order to compute <code>num_ancestors(your_mom, 1)</code>, we must compute <code>num_ancestors(your_maternal_grandma, 0)</code> and <code>num_ancestors(your_maternal_grandpa, 0)</code>. Similarly, in order to compute your dad's call, we must make a call to each of your paternal grandparents.<br />
<br />
Until <code>num_gen</code> is equal to 0, each function call to a person produces ''two'' additional calls to the <code>num_ancestors</code> function. In general, tree recursive functions are distinguished from simply recursive functions by generating more than one call to the same function in the recursive step. If we draw a line from each frame to the frames it directly generates, the pattern of calls looks like a tree called the ''call tree'', with each "root" having two "branches." Here, the call tree mirrors the family tree.<br />
<br />
===Examples===<br />
==== Fibonacci numbers ====<br />
Consider this Python code for generating the nth Fibonacci number:<br />
<syntaxhighlight lang="python"><br />
def fib(n):<br />
if n == 0:<br />
return 1<br />
if n == 1:<br />
return 1<br />
return fib(n - 2) + fib(n - 1)<br />
</syntaxhighlight><br />
The call tree for the <code>fib</code> function looks similar to the call tree for the <code>num_ancestors</code> function, with each function call that was not a base case generating two more calls to <code>fib</code>.<br />
[[File:Fib call tree.png|thumb|left|300px|Call tree for <code>fib</code>]]<br />
{{clear}}<br />
<br />
==== Towers of Hanoi ====<br />
{{Main|Towers of Hanoi}}<br />
<br />
==== Power set ====<br />
{{Main|Power set}}<br />
<br />
==Mutual recursion==<br />
<br />
==Tail recursion==<br />
A function is ''tail recursive'' if the result of any recursive calls made in a function is immediately returned. Tail recursive functions do not make further calculations after a recursive call.<br />
<br />
In [[Scheme]], tail recursion is considered [[iteration]]. Scheme also supports tail call optimization, which will get rid of the frames that are no longer necessary, making the procedure more space efficient.<br />
<br />
=== Example ===<br />
The following factorial function is not tail recursive because the result from the recursive call still needs to be multiplied by <code>n</code>:<br />
<syntaxhighlight lang="scheme"><br />
(define (fact n)<br />
(if (= n 0)<br />
1<br />
(* n (fact (- n 1)))))<br />
</syntaxhighlight><br />
<br />
<code>(fact 2)</code> would execute as follows:<br />
<syntaxhighlight lang="scheme"><br />
(fact 2)<br />
(* 2 (fact 1))<br />
(* 2 (* 1 (fact 0)))<br />
(* 2 (* 1 1))<br />
(* 2 1)<br />
2<br />
</syntaxhighlight><br />
<br />
To make <code>fact</code> tail recursive, we use a helper function that has an extra parameter that keeps track of the running product:<br />
<syntaxhighlight lang="scheme"><br />
(define (fact n)<br />
(define (fact-tail n curr-product)<br />
(if (= n 0)<br />
curr-product<br />
(fact-tail (- n 1) (* curr-product n))))<br />
(fact-tail n 1))<br />
</syntaxhighlight><br />
<code>(fact 2)</code> would execute as follows:<br />
<syntaxhighlight lang="scheme"><br />
(fact 2)<br />
(fact-tail 2 1)<br />
(fact-tail 1 2)<br />
(fact-tail 0 2)<br />
2<br />
</syntaxhighlight><br />
<br />
==See also==<br />
* [[Iteration vs. recursion]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/CS61A_Wiki:Requested_articlesCS61A Wiki:Requested articles2014-08-11T23:25:58Z<p>Axis: /* Python basics (might not be necessary to write this up, maybe just need a link to Python docs) */ done</p>
<hr />
<div>{{plain link|url={{Base url}}/index.php?title=CS61A_Wiki:Requested_articles&action=edit&preload=Template:Requested_articles_preload&summary=add+request&nosummary=true&section=new|name=Click here}} to request an article. Give a brief description for the proposed topic.<br />
<br />
== Requests ==<br />
<br />
=== [[Higher-order function]] ===<br />
This a key idea in the course. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 11:53, 23 May 2014 (PDT)<br />
:Done. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 13:19, 23 May 2014 (PDT)<br />
<br />
=== [[Abstraction]] ===<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
:Done. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 23:13, 2 June 2014 (PDT)<br />
<br />
=== [[Pure vs. non-pure function]] ===<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
:Done. Content at [[pure function]] and [[non-pure function]]. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 13:57, 25 May 2014 (PDT)<br />
::Maybe we can merge these two into [[function]]? --[[Special:Contributions/50.185.204.52|50.185.204.52]] 16:38, 31 May 2014 (PDT)<br />
:::Good suggestion. Done. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 16:52, 31 May 2014 (PDT)<br />
<br />
=== [[Environment diagram]] ===<br />
* [[environment]]<br />
* [[frame]]<br />
* assignment statement execution procedure, function definition execution procedure, function call execution procedure, function call evaluation<br />
* variable lookup<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
:Done. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:43, 26 May 2014 (PDT)<br />
<br />
=== [[Python]] basics (might not be necessary to write this up, maybe just need a link to Python docs) ===<br />
* control structures (while loop, if-elif-else statement)<br />
* local assignment<br />
* boolean operators<br />
** false values<br />
* import statements<br />
* different ways to run python<br />
* doctests/docstrings<br />
* 2 types of division<br />
* default arguments<br />
* decorators<br />
* lambda function<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
:In progress. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 16:10, 28 May 2014 (PDT)<br />
:Done. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 16:25, 11 August 2014 (PDT)<br />
<br />
=== [[Currying]] ===<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
:Done. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 15:12, 5 June 2014 (PDT)<br />
<br />
=== [[Iterative improvement]] ===<br />
* [[Newton's method]]<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
:Done. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 11:34, 25 May 2014 (PDT)<br />
<br />
=== [[Iteration]] ===<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
:Done by [[User:Cem|Cem]]. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 11:58, 18 June 2014 (PDT)<br />
<br />
=== [[Recursion]] (traditional) ===<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
:Done by [[User:Acotra|Acotra]]. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 23:13, 2 June 2014 (PDT)<br />
<br />
=== [[Tree recursion]] ===<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
:Why wouldn't this be merged with Recursion? --[[User:Andrew|Andrew]] ([[User talk:Andrew|talk]]) 02:03, 28 May 2014 (PDT)<br />
::It depends on the size of [[recursion]]. If it turns out to be a long article, it would be better to have a separate page for [[tree recursion]]. Otherwise, we could have sections in [[recursion]] for tree recursion and mutual recursion. It's up to the writer's discretion how to organize it. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 10:22, 28 May 2014 (PDT)<br />
:Done by [[User:Acotra|Acotra]] at [[Recursion#Tree recursion]]. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 12:56, 5 June 2014 (PDT)<br />
<br />
=== [[Mutual recursion]] ===<br />
[[User:Axis|Axis]] ([[User talk:Axis|talk]]) 22:17, 24 May 2014 (PDT)<br />
<br />
=== [[Call expression]] ===<br />
The rules to evaluate a call expression, and a few examples. [[User:Dickson.tsai|Dickson.tsai]] ([[User talk:Dickson.tsai|talk]]) 22:22, 30 May 2014 (PDT)<br />
:Thanks for the suggestion! This content exists at [[Python#Function call]], but the page is still under construction. If you want, you can add examples to it!<br />
:Also, a quick reminder: page titles should be in sentence case (first word capitalized, rest lowercase). [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 23:17, 30 May 2014 (PDT)<br />
:'''Update: ''' it's now at [[Expression#Call expressions]]. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 15:20, 5 June 2014 (PDT)<br />
<br />
=== [[Basic unix]] ===<br />
Basic Unix commands for getting students up and running during the first week of class. [[User:Maxwolffe|Maxwolffe]] ([[User talk:Maxwolffe|talk]]) 23:03, 3 June 2014 (PDT)<br />
:Done. Content at [[Basic Unix]]. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 11:47, 4 June 2014 (PDT)<br />
<br />
=== [[Orders of growth]] ===<br />
Identifying and analyzing functions to determine their orders of growth. Examples. [[User:Austinhle|Austinhle]] ([[User talk:Austinhle|talk]]) 17:55, 7 June 2014 (PDT)<br />
:In progress. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 21:18, 7 June 2014 (PDT)<br />
:Done. Content at [[Order of growth]]. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 21:28, 10 June 2014 (PDT)<br />
<br />
=== [[Objects]] ===<br />
Object-oriented programming, inheritance, objects as data structures (data abstraction). Examples. Preparation for the Ants project. [[User:Austinhle|Austinhle]] ([[User talk:Austinhle|talk]]) 17:55, 7 June 2014 (PDT)<br />
:Done. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 09:46, 19 July 2014 (PDT)<br />
<br />
=== [[Trees]] ===<br />
Trees, traversals, binary search trees, trees as data structures. [[User:Austinhle|Austinhle]] ([[User talk:Austinhle|talk]]) 17:55, 7 June 2014 (PDT)<br />
:Done. I did not include traversals because they are generally not covered in 61A. [[User:Axis|Axis]] ([[User talk:Axis|talk]]) 11:57, 18 June 2014 (PDT)</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Tail_recursionTail recursion2014-08-11T23:25:16Z<p>Axis: Redirected page to Recursion#Tail recursion</p>
<hr />
<div>#REDIRECT [[Recursion#Tail recursion]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Summer_2014_FinalSummer 2014 Final2014-08-11T23:24:55Z<p>Axis: /* Topics */ add link</p>
<hr />
<div>== Logistics ==<br />
Changes from Exam 2 are in '''bold'''.<br />
<br />
2050 VLSB, '''5pm - 8pm on Thursday, August, 14 2014'''.<br />
There will be exactly one alternate exam on Friday.<br />
<br />
Bring<br />
* pencil and eraser<br />
* '''three''' front and back 8.5x11" cheatsheets (the idea is you bring your old cheatsheets and one new one)<br />
* a copy of [http://ocf.berkeley.edu/~shidi/cs61a/guerrilla/env.txt The Rules]<br />
** You can write on your copy of The Rules (8.5x11"), giving you '''4''' cheatsheets total.<br />
<br />
Don't bring<br />
* Any sort of electronics<br />
** Cell phones are okay, but must be turned off for the duration of the exam<br />
<br />
== Topics ==<br />
The Final is cummulative and will test the material from weeks 1-7. We expect about 75% (or 60 points) of the exam to focus on the first 6 weeks of class (exam 1 and 2 material). The remaining 25% (20 points) will focus on the material after Exam 2. This includes:<br />
<br />
{| class="wikitable"<br />
! Final Exam Topics<br />
|-<br />
| [[Recursion#Tail recursion|Tail Recursion]]<br />
|-<br />
| [[Stream]]s<br />
|-<br />
| [[Logic | Logic Programming]]<br />
|-<br />
| [[Concurrency]]<br />
|}<br />
<br />
'''Topics for Exam 2 (fair game)'''<br />
{| class="wikitable mw-collapsible mw-collapsed"<br />
! Exam 2 Topics<br />
|-<br />
| [[nonlocal]] and functions using nonlocal<br />
|-<br />
| Mutable Python data structures and functions on them ([[Sequence#Mutable_sequences|List]], [[Dictionary]])<br />
|-<br />
| [[Environment diagram|Environment diagrams]] on the above<br />
|-<br />
| [[Object-oriented programming|Object Oriented Programming]]<br />
|-<br />
| Interfaces and [[Magic method|'Magic' methods]]<br />
|-<br />
| [[Linked_list#OOP_ADT | Linked Lists]] (Known as Rlists in previous semesters)<br />
|-<br />
| [[Tree#Mutable Tree (OOP)|(Mutable) Trees]] (the kind with datum and children attributes)<br />
|-<br />
| [[Tree#Python_2|Binary Trees]] (the kind with entry, left, and right)<br />
|-<br />
| [[Iterator]]s, [[Iterable]]s and [[Generator]]s<br />
|-<br />
| [[Generic function]]s<br />
|-<br />
| [[Interpreter]]s<br />
|-<br />
| [[Scheme]]<br />
|}<br />
<br />
'''Topics from Exam 1 (fair game)'''<br />
{| class="wikitable mw-collapsible mw-collapsed"<br />
! Exam 1 Topics<br />
|-<br />
| [[Python]] Basics<br />
* [[expression]]s<br />
* [[Statement#Conditional_statements|if statement]]<br />
* [[Iteration#While_loop | while statement]]<br />
* [[Statement#Assignment_statement | assignment statement]]<br />
* [[Statement#Function_definition | def statement]]<br />
* [[Boolean#Boolean | booleans]]<br />
* [[Number#Number | numbers]]<br />
* [[String#String | strings]]<br />
* [[Function]]s<br />
* [[Expression#Call_expressions | Function Call Evaluation]]<br />
|-<br />
| [[Higher-order function]]s and [[Lambda | Lambda expressions]]<br />
|-<br />
| [[ Recursion ]]<br />
|-<br />
| [[Linked list]]s (ignore tuples and OOP); Also known as <code>rlists</code> in other semesters.<br />
|-<br />
| [[Recursion#Tree recursion|Tree Recursion]]<br />
|-<br />
| [[Environment]]s / [[Environment diagram]]s (Note that our Env. Diagrams are compatible with Fall 2012 and onward.)<br />
|-<br />
| [[Sequence]]s<br />
|-<br />
| [[Abstract data type]]s<br />
|-<br />
| [[Trees]] (We haven't covered BSTs or Trees in Scheme)<br />
|-<br />
| [[Linked list#Types | Deep lists]]<br />
|-<br />
| [[Orders of growth]]<br />
|-<br />
| [[Newton's method]]<br />
|-<br />
| [[Halting problem]] (Extra Credit)<br />
|}<br />
<br />
== Other skills ==<br />
* '''Writing out streams'''<br />
* "What will Logic output?"<br />
* Enumerating invalid output from poorly parallized code<br />
* Writing correct concurrent code<br />
<br />
All the skills from Exam 2 still apply:<br />
<br />
* '''Draw Box and pointer diagrams for mutable data structures'''<br />
* '''Drawing Environment diagrams with nonlocal'''<br />
* '''Reading the problem critically/figuring out what the problem is asking'''<br />
* '''Understanding doctests'''<br />
* Designing classes for Object Oriented Programming problems<br />
<br />
All the skills from Exam 1 still apply:<br />
<br />
* Identifying the Operator and Operands<br />
* Drawing Function Boxes<br />
* '''Identifying Domain and Range'''<br />
* '''Drawing Box and Pointers'''<br />
* '''Environment Diagrams'''<br />
* Identifying the Theta of a function<br />
<br />
== Practice Problems ==<br />
Start with the ones from from [[Summer 2014 Exam 1 | Exam 1]], [[Summer 2014 Exam 2 | Exam 2]], and [[Past exams]]. We'll add more soon.<br />
<br />
== How to study ==<br />
<pre>Here is an old algorithm for studying for tests:<br />
For each topic on the exam, find problems on them and do them.<br />
START ON THE TOPICS YOU'RE MOST UNFAMILIAR WITH!<br />
If you can solve them on your own, move on.<br />
Else if you are stuck, look at the solution and figure out if you<br />
are missing a trick or if you do not understand the concepts.<br />
If the problem is that you are stuck on some random trick,<br />
just learn the trick.<br />
Stare at the solutions, ask Piazza, your TA, etc.<br />
Questions you should ask at this stage:<br />
What is the problem asking me to do?<br />
How was I suppose to follow the instructions<br />
to solve the problem?<br />
What part of the problem do I not understand?<br />
What is the fastest way to clear up that misunderstanding?<br />
Then if you think you are still stuck conceptually, review<br />
and learn the concept, however you learn best.<br />
<br />
Suggestions for picking up concepts quickly (~1-2 hours):<br />
Discussion notes typically have a very concise recap of the<br />
thing they are going over.<br />
There are guides for particularly tricky things on the wiki,<br />
like Hanoi, powerset, etc.<br />
Find them and go over them.<br />
Ask a TA: "what is the best way to learn X?"<br />
If these do not work and you are still shaky after an hour<br />
or two, it might be worth watching a lecture or reading<br />
the notes. Be sure to try out some more problems as you're learning!</pre></div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/RecursionRecursion2014-08-11T23:23:55Z<p>Axis: /* Tail recursion */ add content</p>
<hr />
<div>{{C-class}}<br />
'''Recursion''' is a technique for solving a large computational problem by repeatedly applying the same procedure(s) to reduce it to successively smaller problems. A recursive procedure has two parts: one or more ''base cases'' and a ''recursive step''. Base cases are predetermined solutions for the simplest versions of the problem — if the given problem is a base case, no further computation is necessary to get the result. The recursive step is a set of rules that eventually reduces all versions of the problem to one of the base cases when applied repeatedly.<br />
<br />
''Infinite recursion'' occurs if there is no base case or the recursive step does not make progress towards its base case(s).<br />
<br />
Example for how a recursive function looks:<br />
<syntaxhighlight lang="python"><br />
def fn(input):<br />
if <base case>:<br />
return ...<br />
else:<br />
return <combine input and fn(input_reduced)><br />
</syntaxhighlight><br />
<br />
<br />
==Simple recursion==<br />
In simple recursion — the most straightforward and common form of recursion — there is usually only one base case, and in the recursive step, the recursive procedure calls itself only once. <br />
<br />
===Analogy===<br />
Consider this procedure for learning the definition of recursion: "If you are Andrew Huang, you already know the definition. If not, find someone who is standing closer to Andrew Huang than you are and ask them what the definition of recursion is." Here, the base case is being Andrew Huang — once you reach this situation, no further work is necessary to get the definition of recursion. If you are not yet at a base case, the recursive step is to ask someone who is closer to Andrew, reducing the problem closer to the base case.<br />
<br />
Let's call the procedure <code>def_recursion</code>. We can think about it in terms of the ''stack'' from [[environment diagram]]s. Suppose Matthew, Rohin, and Andrew are standing in a line. Matthew wants to know the definition of recursion, so his call to <code>def_recursion</code> is pushed onto the stack. He isn't Andrew, so must find someone standing closer to Andrew than he is and ask them for the definition. So Matthew asks Rohin for the definition of recursion. Rohin's call to the ''same'' <code>def_recursion</code> function is pushed on top of Matthew's call. Rohin is also not Andrew, so he must ask someone standing closer to Andrew than he is — in this case, it's Andrew himself. Now Andrew's call to <code>def_recursion</code> is pushed on top of Rohin's call. <br />
<br />
Andrew is a base case, so he already knows the definition and immediately returns it to Rohin, and Andrew's frame pops off the stack. Now Rohin has the definition of recursion, which he can return to Matthew. Once he returns, Rohin's frame pops off the stack. Now Matthew's frame is the only one on the stack, and he has the definition of recursion. This was the initial goal, so Matthew's frame can return and pop off, leaving the stack empty.<br />
<br />
In pseudocode, <code>def_recursion</code>, which takes in the person who wants to know the definition of recursion as a parameter, can be written like this:<br />
<br />
<syntaxhighlight lang="python"><br />
def def_recursion(you):<br />
if you == AndrewHuang:<br />
return knowledge<br />
else:<br />
return def_recursion(someone closer to AndrewHuang)<br />
</syntaxhighlight><br />
<br />
Notice that in the recursive step, the same procedure is called again, but on a simpler version of the problem every time. If there were no base case (no one knew what recursion was), or the recursive step didn't make the problem smaller (everyone asked people ''further'' from Andrew what the answer was), then the recursion can malfunction and go into an infinite loop.<br />
<br />
===Examples===<br />
An example of simple recursion is the <code>factorial</code> function:<br />
<br />
<syntaxhighlight lang="python"><br />
def factorial(n):<br />
if n == 0:<br />
return 1<br />
else:<br />
return n * factorial(n - 1)<br />
</syntaxhighlight><br />
<br />
Notice that the <code>factorial</code> procedure is called only once in the body of the recursive procedure. However, it is possible for a call to the function to appear in multiple places in the function body — if only one of those calls is ever executed in each frame, the function still exhibits simple recursion. For example, consider the function that raises a base <code>b</code> to a power <code>p</code> through a recursive procedure called ''repeated squaring'':<br />
<br />
<syntaxhighlight lang="python"><br />
def pow(b, p):<br />
if p == 0:<br />
return 1<br />
elif p % 2 == 0:<br />
x = pow(b, p // 2)<br />
return x * x<br />
else:<br />
x = pow(b, p // 2)<br />
return b * x * x<br />
</syntaxhighlight><br />
<br />
Here, the recursive call to <code>pow</code> appears twice — once in the <code>elif</code> clause, once in the <code>else</code> clause. However, the whole procedure is still simply recursive, because only ''one'' of those else clauses is ever triggered in each recursive call, meaning the procedure can only ever call itself once per frame.<br />
<br />
==Tree recursion==<br />
A [[function]] is ''tree recursive'' if the recursive step contains more than one call to the same function. Tree recursive functions generally have more base cases than simply recursive functions as well, though this is not a necessary condition. If a tree recursive function makes repeated computations, it is more optimal to store previous return values rather than perform expensive recomputations. This technique can be implemented through [[memoization]].<br />
<br />
===Analogy===<br />
A tree recursive procedure can naturally be used to answer the question "How many ancestors do I have, up to a certain number of generations?" One natural way to answer this question is to say "I have a mother and a father, making two ancestors. Additionally, my mother's ancestors are my ancestors, and my father's ancestors are my ancestors." Consider the following pseudocode:<br />
<br />
<syntaxhighlight lang="python"><br />
def num_ancestors(you, num_gen):<br />
if num_gen == 0:<br />
return 0<br />
else:<br />
return 2 + num_ancestors(mom, num_gen - 1) + num_ancestors(dad, num_gen - 1)<br />
</syntaxhighlight><br />
<br />
The base case occurs when we only care about ancestors 0 generations up — that is, when we only care about <code>you</code>. Since you have no ancestors who are 0 generations older than you, we return 0. The recursive call then adds up your parents' ancestors, and adds 2 for your parents themselves. <br />
<br />
If we wanted to count up all your ancestors two generations up, we would start with a call to <code>num_ancestors(you, 2)</code>. In order to compute that, we need to computer <code>num_ancestors(your_mom, 1)</code> and <code>num_ancestors(your_dad, 1)</code>. In order to compute <code>num_ancestors(your_mom, 1)</code>, we must compute <code>num_ancestors(your_maternal_grandma, 0)</code> and <code>num_ancestors(your_maternal_grandpa, 0)</code>. Similarly, in order to compute your dad's call, we must make a call to each of your paternal grandparents.<br />
<br />
Until <code>num_gen</code> is equal to 0, each function call to a person produces ''two'' additional calls to the <code>num_ancestors</code> function. In general, tree recursive functions are distinguished from simply recursive functions by generating more than one call to the same function in the recursive step. If we draw a line from each frame to the frames it directly generates, the pattern of calls looks like a tree called the ''call tree'', with each "root" having two "branches." Here, the call tree mirrors the family tree.<br />
<br />
===Examples===<br />
==== Fibonacci numbers ====<br />
Consider this Python code for generating the nth Fibonacci number:<br />
<syntaxhighlight lang="python"><br />
def fib(n):<br />
if n == 0:<br />
return 1<br />
if n == 1:<br />
return 1<br />
return fib(n - 2) + fib(n - 1)<br />
</syntaxhighlight><br />
The call tree for the <code>fib</code> function looks similar to the call tree for the <code>num_ancestors</code> function, with each function call that was not a base case generating two more calls to <code>fib</code>.<br />
[[File:Fib call tree.png|thumb|left|300px|Call tree for <code>fib</code>]]<br />
{{clear}}<br />
<br />
==== Towers of Hanoi ====<br />
{{Main|Towers of Hanoi}}<br />
<br />
==== Power set ====<br />
{{Main|Power set}}<br />
<br />
==Mutual recursion==<br />
<br />
==Tail recursion==<br />
A function is ''tail recursive'' if the result of any recursive calls made in a function is immediately returned. Tail recursive functions do not make further calculations after a recursive call.<br />
<br />
In [[Scheme]], tail recursion is considered [[iteration]]. Scheme also supports tail call optimization, which will get rid of the frames that are no longer necessary, making the procedure more space efficient.<br />
<br />
=== Example ===<br />
The following factorial function is not tail recursive because the result from the recursive call still needs to be multiplied by <code>n</code>:<br />
<syntaxhighlight lang="scheme"><br />
(define (fact n)<br />
(if (= n 0)<br />
1<br />
(* n (fact (- n 1)))))<br />
</syntaxhighlight><br />
<br />
<code>(fact 2)</code> would execute as follows:<br />
<syntaxhighlight lang="scheme"><br />
(fact 2)<br />
(* 2 (fact 1))<br />
(* 2 (* 1 (fact 0)))<br />
(* 2 (* 1 1))<br />
(* 2 1)<br />
2<br />
</syntaxhighlight><br />
<br />
To make <code>fact</code> tail recursive, we use a helper function that has an extra parameter that keeps track of the running product:<br />
<syntaxhighlight lang="scheme"><br />
(define (fact n)<br />
(define (fact-tail n curr-product)<br />
(if (= n 0)<br />
curr-product<br />
(fact-tail (- n 1) (* curr-product n))))<br />
(helper n 1))<br />
</syntaxhighlight><br />
<code>(fact 2)</code> would execute as follows:<br />
<syntaxhighlight lang="scheme"><br />
(fact 2)<br />
(fact-tail 2 1)<br />
(fact-tail 1 2)<br />
(fact-tail 0 2)<br />
2<br />
</syntaxhighlight><br />
<br />
==See also==<br />
* [[Iteration vs. recursion]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Iteration_vs._recursionIteration vs. recursion2014-08-11T23:17:24Z<p>Axis: fix link</p>
<hr />
<div>{{Sufficient-class}}<br />
[[Iteration]] and [[recursion]] are both ways to achieve repetition in programs. One can be converted to the other:<br />
* All iterative functions can be converted to recursion because iteration is just a special case of recursion (tail recursion). In functional languages like [[Scheme]], iteration is defined as tail recursion.<br />
* All recursive functions can be converted to iteration by simulating the stack to store state.<br />
<br />
However, recursion is usually slower and uses more memory because of the overhead of creating and maintaining stack frames. This doesn't mean never use recursion though. Recursion is the better choice when:<br />
* the code is clearer, more concise, and more intuitive<br />
* exploring/manipulating recursive data structures like [[linked list]]s and [[tree]]s or parsing expressions (e.g., Scheme [[interpreter]])<br />
<br />
For example, a recursive function on a tree can be converted into an iterative one, but the iterative one is harder to understand. Compare the following recursive and iterative implementations of finding the number of nodes in a binary tree:<br />
<syntaxhighlight lang="python"><br />
def size_recur(t):<br />
"""Returns the number of nodes in binary tree T.<br />
>>> t = Tree(10, Tree(4, Tree(1), Tree(7)), Tree(16, Tree(13), Tree(19)))<br />
>>> size_recur(t)<br />
7<br />
"""<br />
if t is None:<br />
return 0<br />
return 1 + size_recur(t.left) + size_recur(t.right)<br />
<br />
def size_iter(t):<br />
"""Returns the number of nodes in binary tree T.<br />
>>> t = Tree(10, Tree(4, Tree(1), Tree(7)), Tree(16, Tree(13), Tree(19)))<br />
>>> size_iter(t)<br />
7<br />
"""<br />
count = 0<br />
nodes = [] # unprocessed nodes<br />
if t is not None:<br />
nodes.append(t)<br />
while nodes: # while nodes is not empty<br />
u = nodes.pop() # get an unprocessed node<br />
count += 1 # increment counter<br />
if u.left:<br />
nodes.append(u.left) # add left child<br />
if u.right:<br />
nodes.append(u.right) # add right child<br />
return count<br />
</syntaxhighlight> In this case, the recursive version is more intuitive and concise.<br />
<br />
== Iteration → recursion ==<br />
An iterative function can be converted to a tail recursive function by using the loop condition as the base case and the body of the loop as the recursive step. The local variables in the iterative version turn into parameters in the recursive version.<br />
<br />
Example 1:<br />
<syntaxhighlight lang="python"><br />
def max_iter(lst):<br />
"""Returns the maximum element of LST.<br />
>>> max_iter([3, 7, 2, 5])<br />
7<br />
"""<br />
x = lst[0]<br />
i = 1<br />
while i < len(lst):<br />
if lst[i] > x:<br />
x = lst[i]<br />
i += 1<br />
return x<br />
<br />
def max_recur(lst):<br />
"""Returns the maximum element of LST.<br />
>>> max_recur([3, 7, 2, 5])<br />
7<br />
"""<br />
def helper(i, x):<br />
if i == len(lst):<br />
return x<br />
if lst[i] > x:<br />
x = lst[i]<br />
return helper(i + 1, x)<br />
return helper(1, lst[0])<br />
</syntaxhighlight><br />
<br />
Example 2:<br />
<syntaxhighlight lang="python"><br />
def fib_iter(n):<br />
prev, curr = 0, 1<br />
for k in range(2, n):<br />
prev, curr = curr, prev + curr<br />
return curr<br />
<br />
def fib_tail_recur(n):<br />
def helper(k, prev, curr):<br />
if k == n:<br />
return curr<br />
return helper(k + 1, curr, prev + curr)<br />
return helper(2, 0, 1)<br />
</syntaxhighlight><br />
<br />
== Recursion → iteration ==<br />
A tail recursive function can be converted to an iterative function using the same idea as [[#Iteration → recursion|above]]. A more complicated recursive function will require a stack to convert to an iterative function. This is outside the scope of 61A.<br />
<br />
== Sources ==<br />
* http://www.fbeedle.com/python/99-6ch13.pdf (section 13.2.7)<br />
* http://stackoverflow.com/questions/15688019/recursion-versus-iteration<br />
* http://pages.cs.wisc.edu/~vernon/cs367/notes/6.RECURSION.html#iter<br />
* http://math.scu.edu/~dsmolars/ma60/notesa3.html</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-11T18:29:04Z<p>Axis: copyedit; {{C-class}}</p>
<hr />
<div>{{C-class}}<br />
'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic</code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''the parent of barack is abraham.'''<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight><br />
<br />
The <code>fact</code> can be read as "?c is the child of ?p, provided that ?p is the parent of ?c."<br />
<br />
==Recursion==<br />
<code>Logic</code> also supports recursion, that is, the conclusion of a fact may depend on a hypothesis that contains the same symbols. <br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (ancestor ?a ?y) (parent ?a ?y))<br />
logic> (fact (ancestor ?a ?y) (parent ?a ?z) (ancestor ?z ?y))<br />
<br />
logic> (query (ancestor ?a herbert))<br />
Success!<br />
a: delano<br />
a: fillmore<br />
a: eisenhower<br />
</syntaxhighlight><br />
<br />
==Hierarchical facts==<br />
Fact and query lists can also contain lists, providing a way to represent hierarchical data. For example, we can assign colors to dog names.<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (dog (name abraham) (color white)))<br />
logic> (fact (dog (name barack) (color tan)))<br />
logic> (fact (dog (name clinton) (color white)))<br />
logic> (fact (dog (name delano) (color white)))<br />
logic> (fact (dog (name eisenhower) (color tan)))<br />
logic> (fact (dog (name fillmore) (color brown)))<br />
logic> (fact (dog (name grover) (color tan)))<br />
logic> (fact (dog (name herbert) (color brown)))<br />
<br />
logic> (query (dog (name clinton) (color ?color)))<br />
Success!<br />
color: white<br />
<br />
logic> (query (dog (name clinton) ?info))<br />
Success!<br />
info: (color white)<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
* [http://composingprograms.com/pages/43-declarative-programming.html Declarative Programming]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Talk:LogicTalk:Logic2014-08-11T18:28:14Z<p>Axis: {{Talk page guidelines}}</p>
<hr />
<div>{{Talk page guidelines}}</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-11T18:26:58Z<p>Axis: restructure; add</p>
<hr />
<div>{{C-class}}<br />
'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. To make it seem that programs are running concurrently, the CPU rapidly switches between each program, doing some work for each process before switching to the next.<br />
<br />
Parallel computing is used to increase the speed of processors, but due to physical heat and energy limitations, CPU manufacturers have turned to multiple processors (multicore) to achieve more processing power.<br />
<br />
==Parallelism in [[Python]]==<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data.<br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes'', each of which runs independently without sharing data. Shared data must be communicated explicitly between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Shared state and synchronization==<br />
Problems can arise when multiple threads manipulate and access shared data. A ''race condition'' occurs when multiple threads access the same data and at least one mutates it. This causes unpredictable behavior. Access to shared data in the presence of mutation must be synchronized to prevent other threads from accessing the data while it is being mutated.<ref name="su13_lec">http://inst.eecs.berkeley.edu/~cs61a/su13/slides/27-Parallelism_6pp.pdf</ref><br />
<br />
For example, if <code>x = 1</code> and we run the following lines in parallel in separate threads:<br />
* <code>x = x * 2</code><br />
* <code>x = x + 10</code><br />
the possible final values of <code>x</code> are 12, 11, 22, and 2.<br />
<br />
=== Techniques ===<br />
<br />
====Synchronized data structures====<br />
Some data structures provide synchronized operations. For example, a <code>Queue</code> provides synchronized first-in, first-out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (from the end of the Queue). The methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
from queue import Queue<br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
====Locks====<br />
A ''lock'' ensures that only one thread at a time can hold it. Once it is ''acquired'', no other threads may acquire it until it is ''released''.<ref name="su13_lec"/> For a lock to protect a set of variables, all code blocks that deal with those variables should be surrounded by <code>acquire</code> and <code>release</code> calls.<ref name="disc">http://inst.eecs.berkeley.edu/~cs61a/su13/disc/disc07b.pdf</ref><br />
<br />
====Barriers====<br />
Another way to avoid conflicting access to shared data is to divide a program into phases, ensuring that shared data is mutated in a phase in which no other thread accesses it. ''Barriers'' divide a program into phases by requiring all threads to reach it before any of them can proceed. Code that is executed after a barrier cannot be concurrent with code executed before the barrier.<br />
<br />
====Message passing====<br />
Another way is to entirely avoid concurrent access to the same data. Let computations behave independently, but give them a way to send messages to each other to coordinate.<ref name="disc"/><br />
<br />
===Pitfalls===<br />
Incorrectly used synchronization methods can result in the following pitfalls.<br />
<br />
====Under-synchronization====<br />
Neglecting to properly synchronize shared accesses.<br />
<br />
====Over-synchronization====<br />
Over-synchronizing a program means that non-conflicting operations cannot occur concurrently, reducing the program's efficiency.<br />
<br />
====Deadlock====<br />
Deadlock is a situation in which two or more threads or processes are stuck, waiting for each other to finish. No process can continue because it is waiting for other processes that are waiting for it to complete.<br />
<br />
==Sources==<br />
<references/><br />
* [http://composingprograms.com/pages/47-parallel-computing.html Parallel Computing]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Talk:ConcurrencyTalk:Concurrency2014-08-11T16:29:19Z<p>Axis: {{Talk page guidelines}}</p>
<hr />
<div>{{Talk page guidelines}}</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-11T16:28:47Z<p>Axis: copyedit; {{C-class}}</p>
<hr />
<div>{{C-class}}<br />
'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. To make it seem that programs are running concurrently, the CPU rapidly switches between each program, doing work in one process before switching to the next. Parallel computing is used to increase the speed of processors, but due to physical heat and energy limitations, CPU manufacturers utilize the idea of multi-core processors to achieve more processing power. <br />
<br />
==Parallelism in [[Python]]==<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data.<br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes'', each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized data structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==<br />
===Locks===<br />
When a synchronized version of a particular data structure is not available, we have to provide our own synchronization. A solution to this is a ''lock'', which allows a data structure to be acquired by at most one thread, after which no other thread may acquire it until it is ''released'' by the thread that previously acquired it.<br />
<br />
===Barriers===<br />
Another way to avoid conflicting access to shared data is to divide a program into phases, ensuring that shared data is mutated in a phase in which no other thread accesses it. '''Barriers''' divide a program into phases by requiring all threads to reach it before any of them can proceed. Code that is executed after a barrier cannot be concurrent with code executed before the barrier.<br />
<br />
===Message Passing===<br />
Another way is to entirely avoid concurrent access to the same data. Using multiprocessing in Python rather than threading naturally results in this, since processes run in separate interpreters with their own data.<br />
<br />
==Synchronization Pitfalls==<br />
Incorrectly used synchronization methods can result in the following pitfalls.<br />
<br />
===Under-synchronization===<br />
Neglecting to properly synchronize shared accesses.<br />
<br />
===Over-synchronization===<br />
Over-synchronizing a program means that non-conflicting operations cannot occur concurrently.<br />
<br />
===Deadlock===<br />
Deadlock is a situation in which two or more threads or processes are stuck, waiting for each other to finish. No process can continue because it is waiting for other processes that are waiting for it to complete.<br />
<br />
==Sources==<br />
[http://composingprograms.com/pages/47-parallel-computing.html Parallel Computing]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-11T16:22:16Z<p>Axis: /* Useful stream functions */ use stream-null?</p>
<hr />
<div>{{C-class}}<br />
A '''stream''' is a [[Lazy evaluation|lazily evaluated]] [[linked list]]. That is, a stream has ''first'' and ''rest'' fields, where the ''first'' is anything and the ''rest'' is a stream or the empty stream. The rest of the list is computed only when requested, and once it is computed, it will be saved and returned the next time we request it. Because of the lazy evaluation, streams allow us to create infinite sequences without running out of memory.<br />
<br />
==ADT==<br />
* <code>cons-stream</code> – makes a new stream<br />
* <code>stream-car</code> – returns the ''first'' of a given stream.<br />
* <code>stream-cdr</code> – returns the ''rest'' of a given stream.<br />
* <code>the-empty-stream</code> – an empty stream; for finite streams, it serves as the last element<br />
* <code>stream-null?</code> – returns whether the argument is <code>the-empty-stream</code><br />
<br />
==Examples==<br />
A finite stream containing the values 1, 2, 3:<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's:<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
</syntaxhighlight><br />
<br />
An infinite stream of the natural numbers (1, 2, 3, ...):<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
In STk, streams that have an unevaluated rest have a "not forced" promise to evaluate the rest:<br />
<syntaxhighlight lang='scheme'><br />
STk> nats<br />
(1 . #[promise 23b018 (not forced)])<br />
</syntaxhighlight><br />
<br />
Once the rest is evaluated, the stream has a "forced" promise to evaluate the rest:<br />
<syntaxhighlight lang='scheme'><br />
STk> (stream-cdr nats) ; force the promise / evaluate the rest<br />
(2 . #[promise 23c688 (not forced)])<br />
STk> nats<br />
(1 . #[promise 23b018 (forced)])<br />
</syntaxhighlight><br />
<br />
==Useful stream functions==<br />
<code>stream-add</code>:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (stream-null? a)<br />
a<br />
(if (stream-null? b)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight><br />
<br />
<code>ss</code> (show stream): outputs the first 10 elements of a stream<br />
<syntaxhighlight lang='scheme'><br />
STK> (ss (add-streams ones twos))<br />
(3 3 3 3 3 3 3 3 3 3 ...)<br />
</syntaxhighlight><br />
<br />
<code>stream-ref</code>: takes in a stream and an index and outputs the element<br />
<syntaxhighlight lang='scheme'><br />
STK> (stream-ref nats 1378)<br />
1378<br />
</syntaxhighlight><br />
<br />
== Writing functions on streams ==<br />
Streams are recursively defined like linked lists, so stream manipulation will be accomplished through recursion. For example, here is <code>stream-map</code>:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-map f stream)<br />
(if (stream-null? stream)<br />
the-empty-stream<br />
(cons-stream (f (stream-car stream)) (stream-map f (stream-cdr stream)))))<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
[https://docs.google.com/presentation/d/1sm8o5VlVUsVkFT4kQpONLbCmCp_DaaMoQvUvoeZbwMA/edit#slide=id.p Streams, su14 lecture 25]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-11T16:20:46Z<p>Axis: add more explanation; copyedit lead; {{C-class}}</p>
<hr />
<div>{{C-class}}<br />
A '''stream''' is a [[Lazy evaluation|lazily evaluated]] [[linked list]]. That is, a stream has ''first'' and ''rest'' fields, where the ''first'' is anything and the ''rest'' is a stream or the empty stream. The rest of the list is computed only when requested, and once it is computed, it will be saved and returned the next time we request it. Because of the lazy evaluation, streams allow us to create infinite sequences without running out of memory.<br />
<br />
==ADT==<br />
* <code>cons-stream</code> – makes a new stream<br />
* <code>stream-car</code> – returns the ''first'' of a given stream.<br />
* <code>stream-cdr</code> – returns the ''rest'' of a given stream.<br />
* <code>the-empty-stream</code> – an empty stream; for finite streams, it serves as the last element<br />
* <code>stream-null?</code> – returns whether the argument is <code>the-empty-stream</code><br />
<br />
==Examples==<br />
A finite stream containing the values 1, 2, 3:<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's:<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
</syntaxhighlight><br />
<br />
An infinite stream of the natural numbers (1, 2, 3, ...):<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
In STk, streams that have an unevaluated rest have a "not forced" promise to evaluate the rest:<br />
<syntaxhighlight lang='scheme'><br />
STk> nats<br />
(1 . #[promise 23b018 (not forced)])<br />
</syntaxhighlight><br />
<br />
Once the rest is evaluated, the stream has a "forced" promise to evaluate the rest:<br />
<syntaxhighlight lang='scheme'><br />
STk> (stream-cdr nats) ; force the promise / evaluate the rest<br />
(2 . #[promise 23c688 (not forced)])<br />
STk> nats<br />
(1 . #[promise 23b018 (forced)])<br />
</syntaxhighlight><br />
<br />
==Useful stream functions==<br />
<code>stream-add</code>:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (equal? a the-empty-stream)<br />
a<br />
(if (equal? b the-empty-stream)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight><br />
<br />
<code>ss</code> (show stream): outputs the first 10 elements of a stream<br />
<syntaxhighlight lang='scheme'><br />
STK> (ss (add-streams ones twos))<br />
(3 3 3 3 3 3 3 3 3 3 ...)<br />
</syntaxhighlight><br />
<br />
<code>stream-ref</code>: takes in a stream and an index and outputs the element<br />
<syntaxhighlight lang='scheme'><br />
STK> (stream-ref nats 1378)<br />
1378<br />
</syntaxhighlight><br />
<br />
== Writing functions on streams ==<br />
Streams are recursively defined like linked lists, so stream manipulation will be accomplished through recursion. For example, here is <code>stream-map</code>:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-map f stream)<br />
(if (stream-null? stream)<br />
the-empty-stream<br />
(cons-stream (f (stream-car stream)) (stream-map f (stream-cdr stream)))))<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
[https://docs.google.com/presentation/d/1sm8o5VlVUsVkFT4kQpONLbCmCp_DaaMoQvUvoeZbwMA/edit#slide=id.p Streams, su14 lecture 25]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Talk:Lazy_evaluationTalk:Lazy evaluation2014-08-11T15:44:42Z<p>Axis: {{Talk page guidelines}}</p>
<hr />
<div>{{Talk page guidelines}}</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-11T15:35:03Z<p>Axis: copyedit</p>
<hr />
<div>A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty and '''is never evaluated unless we need it.''' Because of this, streams allow us to create an infinite sequence.<br />
<br />
==ADT==<br />
* <code>cons-stream</code> – makes a new stream<br />
<br />
* <code>stream-car</code> – returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> – returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> – an empty stream; for finite streams, it serves as the last element<br />
<br />
==Examples==<br />
A finite stream containing the values 1, 2, 3:<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's:<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
</syntaxhighlight><br />
<br />
An infinite stream of the natural numbers (1, 2, 3, ...):<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
==Useful stream functions==<br />
Stream addition:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (equal? a the-empty-stream)<br />
a<br />
(if (equal? b the-empty-stream)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight><br />
<br />
Show stream: outputs the first 10 elements of a stream<br />
<syntaxhighlight lang='scheme'><br />
STK> (ss (add-streams ones twos))<br />
(3 3 3 3 3 3 3 3 3 3 ...)<br />
</syntaxhighlight><br />
<br />
Takes in a stream and an index and outputs the element<br />
<syntaxhighlight lang='scheme'><br />
STK> (stream-ref nats 1378)<br />
1378<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
[https://docs.google.com/presentation/d/1sm8o5VlVUsVkFT4kQpONLbCmCp_DaaMoQvUvoeZbwMA/edit#slide=id.p Streams]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Talk:StreamTalk:Stream2014-08-11T15:25:58Z<p>Axis: {{Talk page guidelines}}</p>
<hr />
<div>{{Talk page guidelines}}</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Summer_2014_FinalSummer 2014 Final2014-08-11T01:45:29Z<p>Axis: /* Topics */ refine links</p>
<hr />
<div>== Logistics ==<br />
Changes from Exam 2 are in '''bold'''.<br />
<br />
2050 VLSB, '''5pm - 8pm on Thursday, August, 14 2014'''.<br />
There will be exactly one alternate exam on Friday.<br />
<br />
Bring<br />
* pencil and eraser<br />
* '''three''' front and back 8.5x11" cheatsheets (the idea is you bring your old cheatsheets and one new one)<br />
* a copy of [http://ocf.berkeley.edu/~shidi/cs61a/guerrilla/env.txt The Rules]<br />
** You can write on your copy of The Rules (8.5x11"), giving you '''4''' cheatsheets total.<br />
<br />
Don't bring<br />
* Any sort of electronics<br />
** Cell phones are okay, but must be turned off for the duration of the exam<br />
<br />
== Topics ==<br />
The Final is cummulative and will test the material from weeks 1-7. We expect about 75% (or 60 points) of the exam to focus on the first 6 weeks of class (exam 1 and 2 material). The remaining 25% (20 points) will focus on the material after Exam 2. This includes:<br />
<br />
{| class="wikitable"<br />
! Final Exam Topics<br />
|-<br />
| Tail Recursion<br />
|-<br />
| [[Stream]]s<br />
|-<br />
| [[Logic | Logic Programming]]<br />
|-<br />
| [[Concurrency]]<br />
|}<br />
<br />
'''Topics for Exam 2 (fair game)'''<br />
{| class="wikitable mw-collapsible mw-collapsed"<br />
! Exam 2 Topics<br />
|-<br />
| [[nonlocal]] and functions using nonlocal<br />
|-<br />
| Mutable Python data structures and functions on them ([[Sequence#Mutable_sequences|List]], [[Dictionary]])<br />
|-<br />
| [[Environment diagram|Environment diagrams]] on the above<br />
|-<br />
| [[Object-oriented programming|Object Oriented Programming]]<br />
|-<br />
| Interfaces and [[Magic method|'Magic' methods]]<br />
|-<br />
| [[Linked_list#OOP_ADT | Linked Lists]] (Known as Rlists in previous semesters)<br />
|-<br />
| [[Tree#Mutable Tree (OOP)|(Mutable) Trees]] (the kind with datum and children attributes)<br />
|-<br />
| [[Tree#Python_2|Binary Trees]] (the kind with entry, left, and right)<br />
|-<br />
| [[Iterator]]s, [[Iterable]]s and [[Generator]]s<br />
|-<br />
| [[Generic function]]s<br />
|-<br />
| [[Interpreter]]s<br />
|-<br />
| [[Scheme]]<br />
|}<br />
<br />
'''Topics from Exam 1 (fair game)'''<br />
{| class="wikitable mw-collapsible mw-collapsed"<br />
! Exam 1 Topics<br />
|-<br />
| [[Python]] Basics<br />
* [[expression]]s<br />
* [[Statement#Conditional_statements|if statement]]<br />
* [[Iteration#While_loop | while statement]]<br />
* [[Statement#Assignment_statement | assignment statement]]<br />
* [[Statement#Function_definition | def statement]]<br />
* [[Boolean#Boolean | booleans]]<br />
* [[Number#Number | numbers]]<br />
* [[String#String | strings]]<br />
* [[Function]]s<br />
* [[Expression#Call_expressions | Function Call Evaluation]]<br />
|-<br />
| [[Higher-order function]]s and [[Lambda | Lambda expressions]]<br />
|-<br />
| [[ Recursion ]]<br />
|-<br />
| [[Linked list]]s (ignore tuples and OOP); Also known as <code>rlists</code> in other semesters.<br />
|-<br />
| [[Recursion#Tree recursion|Tree Recursion]]<br />
|-<br />
| [[Environment]]s / [[Environment diagram]]s (Note that our Env. Diagrams are compatible with Fall 2012 and onward.)<br />
|-<br />
| [[Sequence]]s<br />
|-<br />
| [[Abstract data type]]s<br />
|-<br />
| [[Trees]] (We haven't covered BSTs or Trees in Scheme)<br />
|-<br />
| [[Linked list#Types | Deep lists]]<br />
|-<br />
| [[Orders of growth]]<br />
|-<br />
| [[Newton's method]]<br />
|-<br />
| [[Halting problem]] (Extra Credit)<br />
|}<br />
<br />
== Other skills ==<br />
* '''Writing out streams'''<br />
* "What will Logic output?"<br />
* Enumerating invalid output from poorly parallized code<br />
* Writing correct concurrent code<br />
<br />
All the skills from Exam 2 still apply:<br />
<br />
* '''Draw Box and pointer diagrams for mutable data structures'''<br />
* '''Drawing Environment diagrams with nonlocal'''<br />
* '''Reading the problem critically/figuring out what the problem is asking'''<br />
* '''Understanding doctests'''<br />
* Designing classes for Object Oriented Programming problems<br />
<br />
All the skills from Exam 1 still apply:<br />
<br />
* Identifying the Operator and Operands<br />
* Drawing Function Boxes<br />
* '''Identifying Domain and Range'''<br />
* '''Drawing Box and Pointers'''<br />
* '''Environment Diagrams'''<br />
* Identifying the Theta of a function<br />
<br />
== Practice Problems ==<br />
Start with the ones from from [[Summer 2014 Exam 1 | Exam 1]] and [[Summer 2014 Exam 2 | Exam 2]]. We'll add more soon.<br />
<br />
== How to study ==<br />
<pre>Here is an old algorithm for studying for tests:<br />
For each topic on the exam, find problems on them and do them.<br />
START ON THE TOPICS YOU'RE MOST UNFAMILIAR WITH!<br />
If you can solve them on your own, move on.<br />
Else if you are stuck, look at the solution and figure out if you<br />
are missing a trick or if you do not understand the concepts.<br />
If the problem is that you are stuck on some random trick,<br />
just learn the trick.<br />
Stare at the solutions, ask Piazza, your TA, etc.<br />
Questions you should ask at this stage:<br />
What is the problem asking me to do?<br />
How was I suppose to follow the instructions<br />
to solve the problem?<br />
What part of the problem do I not understand?<br />
What is the fastest way to clear up that misunderstanding?<br />
Then if you think you are still stuck conceptually, review<br />
and learn the concept, however you learn best.<br />
<br />
Suggestions for picking up concepts quickly (~1-2 hours):<br />
Discussion notes typically have a very concise recap of the<br />
thing they are going over.<br />
There are guides for particularly tricky things on the wiki,<br />
like Hanoi, powerset, etc.<br />
Find them and go over them.<br />
Ask a TA: "what is the best way to learn X?"<br />
If these do not work and you are still shaky after an hour<br />
or two, it might be worth watching a lecture or reading<br />
the notes. Be sure to try out some more problems as you're learning!</pre></div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-11T01:44:44Z<p>Axis: Axis moved page Streams to Stream: singular</p>
<hr />
<div>A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty and '''is never evaluated unless we need it.''' Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see '''Examples''' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
==Useful Stream Functions==<br />
Stream addition:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (equal? a the-empty-stream)<br />
a<br />
(if (equal? b the-empty-stream)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight><br />
<br />
Show stream: outputs the first 10 elements of a stream<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (ss (add-streams ones twos))<br />
(3 3 3 3 3 3 3 3 3 3 ...)<br />
</syntaxhighlight><br />
<br />
Takes in a stream and an index and outputs the element<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (stream-ref nats 1378)<br />
1378<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
[https://docs.google.com/presentation/d/1sm8o5VlVUsVkFT4kQpONLbCmCp_DaaMoQvUvoeZbwMA/edit#slide=id.p Streams]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamsStreams2014-08-11T01:44:44Z<p>Axis: Axis moved page Streams to Stream: singular</p>
<hr />
<div>#REDIRECT [[Stream]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/TreeTree2014-07-31T17:08:50Z<p>Axis: /* Functional ADT */ fix error</p>
<hr />
<div>{{C-class}}<br />
{{purge}}<br />
A '''tree''' is an abstract model of a hierarchical structure. It consists of nodes with a parent-child relationship. Its name comes from the fact that when drawn, it resembles an upside-down real tree — the root at the top and the leaves at the bottom. A tree is a recursive data structure; it is either the empty tree or a node that contains a label and references to subtrees. The label can be any data type.<br />
<br />
In computer science, there are many different types of trees. In 61A, we will look at general trees and binary trees.<br />
<br />
== Terminology ==<br />
Here is a tree:<br />
<span id="binary_img"></span><br />
[[File:Binary tree.png|250px|left]]<br />
{{clear}}<br />
<br />
* '''node''': a point in the tree. Each node has a label (value at each node). In the figure, each circle represents a node.<br />
* '''root''': the node at the top. Every tree has one root. In the figure, node F is the root.<br />
* '''parent''': the node that is directly above a node. In the figure, node D is the parent of nodes C and E.<br />
* '''children''': the nodes directly beneath a node. In the figure, nodes C and E are the children of node D.<br />
* '''inner node''': a node with children. In the figure, nodes B, D, F, G, and I are inner nodes.<br />
* '''leaf''': a node with no children. In the figure, nodes A, C, E, and H are leaves.<br />
* '''subtree''': a node and all its descendants. In the figure, the tree rooted at node B is a subtree of node F.<br />
* '''depth''': how far away a node is from the root. The root of a tree has depth 0. In the figure, node D has depth 2.<br />
* '''height''': the depth of the lowest leaf. In other words, the length of the longest path from the root to a leaf. An empty tree has height 0. In the figure, the height is 3.<br />
{{clear}}<br />
<br />
== Applications ==<br />
Here are some applications of trees:<br />
* hierarchical organization of real-world data<br />
** family trees, taxonomies<br />
** filesystem tree – used by operating systems to maintain the filesystem. A directory is the parent of the enclosed files/directories. Here is a UNIX filesystem tree:<br />
::[[File:Filesystem tree.png|left|300px]]<br />
{{clear}}<br />
:* inheritance tree – the relationship between classes and subclasses in [[object-oriented programming]]<br />
* data structures for efficiently storing and retrieving data<br />
** [[#Binary search tree (BST)|binary search tree]] – store objects in a sorted structure that allows for fast searching<br />
* decision trees – diagram a branching algorithmic process. Each node is a question, each branch is an answer to a question, and each leaf is an outcome. Here is an example:<br />
:[[File:Decision tree.png|left|350px]]<br />
{{clear}}<br />
* parse tree – shows the structure of source code. Here is the parse tree for <code>(2 + 6) / (9 % 5)</code>:<br />
:[[File:Expression tree.gif|left|200px]]<br />
{{clear}}<br />
<br />
== Operations ==<br />
The recursive structure of a tree suggests recursive algorithms for operations. Generally, the base case will be if the current node is a leaf. The recursive step will involve recursing on each subtree.<br />
<br />
== General tree ==<br />
In a general tree, each node has a label and list of children. An empty list of children means that node is a leaf.<br />
<br />
=== Python ===<br />
==== Functional ADT ====<br />
<syntaxhighlight lang="python"><br />
def tree(datum, children=[]):<br />
# YOU DON'T KNOW THE IMPLEMENTATION<br />
<br />
def datum(tree):<br />
# YOU DON'T KNOW THE IMPLEMENTATION<br />
<br />
def children(tree):<br />
# YOU DON'T KNOW THE IMPLEMENTATION<br />
</syntaxhighlight><br />
<br />
<span id="python_example"></span><br />
Example:<br />
<syntaxhighlight lang="python"><br />
def leaf_count(t):<br />
"""Returns the number of leaves in tree T.<br />
>>> t = tree(6, [tree(9), tree(8, [tree(4)]), tree(7)])<br />
# 6<br />
# +-----+-----+<br />
# | | |<br />
# 9 8 7<br />
# |<br />
# 4<br />
>>> leaf_count(t)<br />
3<br />
"""<br />
if children(t) == []: # if t is a leaf<br />
return 1<br />
return sum(leaf_count(child) for child in children(t))<br />
</syntaxhighlight><br />
<br />
==== Mutable Tree (OOP) ====<br />
Note that a tree is constructed using the <code>Tree()</code> constructor, and its datum and Python list of children can be accessed via the Tree instance's [[Attribute|attributes]].<ref>http://inst.eecs.berkeley.edu/~cs61a/su14/discussion/discussion10/discussion10.pdf</ref><br />
<syntaxhighlight lang="python"><br />
class Tree:<br />
def __init__(self, datum, *args):<br />
self.datum = datum<br />
self.children = list(args)<br />
</syntaxhighlight><br />
<br />
=== Scheme ===<br />
Implementation:<br />
<syntaxhighlight lang="scheme"><br />
(define (make-tree entry children)<br />
(cons entry children))<br />
(define (entry tree)<br />
(car tree))<br />
(define (children tree)<br />
(cdr tree))<br />
</syntaxhighlight><br />
<br />
When working with general trees in Scheme, it is often necessary to write two [[mutual recursion|mutually recursive]] functions: one that handles a single tree and one that handles a forest. In the Python example [[#python_example|above]], we were able to loop through each tree in the forest to recurse on it. In Scheme, we have to write a function specifically to operate on the forest. This is a common structure:<br />
<syntaxhighlight lang="scheme"><br />
; handles a tree<br />
(define (foo-tree tree)<br />
...<br />
(foo-forest (children tree)))<br />
<br />
; handles a forest<br />
(define (foo-forest forest)<br />
...<br />
(foo-tree (car forest))<br />
...<br />
(foo-forest (cdr forest)))<br />
</syntaxhighlight><br />
Example:<br />
<syntaxhighlight lang="scheme"><br />
(define (leaf-count-tree t)<br />
(if (null? (children t)) ; t is a leaf<br />
1<br />
(leaf-count-forest (children t))))<br />
<br />
(define (leaf-count-forest forest)<br />
(if (null? forest)<br />
0<br />
(+ (leaf-count-tree (car forest)) (leaf-count-forest (cdr forest)))))<br />
</syntaxhighlight><br />
<code>leaf-count-tree</code> relies on <code>leaf-count-forest</code> to count the leaves from the children of the current node and <code>leaf-count-forest</code> relies on <code>leaf-count-tree</code> to count the leaves in each tree in the forest.<br />
<br />
Note that this method still works in Python:<br />
<syntaxhighlight lang="python"><br />
def leaf_count_tree(t):<br />
if not t.children: # t is a leaf<br />
return 1<br />
return leaf_count_forest(t.children)<br />
<br />
def leaf_count_forest(forest):<br />
if not forest:<br />
return 0<br />
return leaf_count_tree(forest[0]) + leaf_count_forest(forest[1:])<br />
</syntaxhighlight><br />
<br />
== Binary tree ==<br />
A ''binary tree'' is a tree where each node has at most two children. Each child is called a left or right child. For example, the tree [[#binary_img|above]] is a binary tree. Node A is the left child of node B, and node D is the right child.<br />
<br />
=== Python ===<br />
Implementation (includes a function that pretty-prints a binary tree):<br />
{{scroll box<br />
|width=40%<br />
|height=235px<br />
|text=<br />
<syntaxhighlight lang="python"><br />
class BinTree:<br />
"""<br />
>>> t = BinTree(6, BinTree(2, BinTree(0), BinTree(4)), BinTree(10, BinTree(8), BinTree(12)))<br />
>>> t<br />
BinTree(6, BinTree(2, BinTree(0), BinTree(4)), BinTree(10, BinTree(8), BinTree(12)))<br />
>>> print(t)<br />
-6- <br />
/ \ <br />
2 10<br />
/ \ / \<br />
0 4 8 12<br />
"""<br />
def __init__(self, entry, left=None, right=None):<br />
self.entry = entry<br />
self.left = left<br />
self.right = right<br />
<br />
def __repr__(self): # used by the interpreter<br />
args = repr(self.entry)<br />
if self.left or self.right:<br />
args += ', {0}, {1}'.format(repr(self.left), repr(self.right))<br />
return 'BinTree({0})'.format(args)<br />
<br />
def __str__(self): # used by print() and str()<br />
return tree_string(self)<br />
<br />
# Tree printing functions, kindly provided by Joseph Hui. #<br />
<br />
def tree_string(tree):<br />
return "\n".join(tree_block(tree)[0])<br />
<br />
def tree_block(tree):<br />
"""Returns a list of strings, each string being<br />
one line in a rectangle of text representing the<br />
tree.<br />
Also returns the index in the string which is<br />
centered above the tree's root.<br />
<br />
num_width: The width of the widest number in the tree (100 => 3)<br />
"""<br />
#If no children, just return string<br />
if tree.left is None and tree.right is None:<br />
return [str(tree.entry)], len(str(tree.entry))//2<br />
num_width = len(str(tree.entry)) #Width of this tree's entry<br />
#If only right child:<br />
if tree.left is None:<br />
r_block, r_cent = tree_block(tree.right)<br />
#Add left padding if necessary<br />
if r_cent < num_width*3/2:<br />
padding = ' '*((num_width*3)//2-r_cent)<br />
r_cent += ((num_width*3)//2-r_cent) #Record new center<br />
for line_index in range(len(r_block)):<br />
r_block[line_index] = padding+r_block[line_index]<br />
<br />
#Generate top two lines<br />
t_line = str(tree.entry)<br />
t_line += '-'*(r_cent-len(t_line))<br />
t_line += ' '*(len(r_block[0])-len(t_line))<br />
m_line = ' '*r_cent + '\\'<br />
m_line += ' '*(len(r_block[0])-len(m_line))<br />
<br />
return [t_line, m_line]+r_block, num_width//2<br />
#If only left child:<br />
if tree.right is None:<br />
l_block, l_cent = tree_block(tree.left)<br />
#Add right padding if necessary<br />
if len(l_block[0]) < l_cent+1+num_width:<br />
padding = ' '*(l_cent+1+num_width-len(l_block[0]))<br />
for line_index in range(len(l_block)):<br />
l_block[line_index] = l_block[line_index]+padding<br />
#Generate lines<br />
t_line = ' '*(l_cent+1)<br />
t_line += '-'*(len(l_block[0])-l_cent-1-num_width)<br />
t_line += str(tree.entry)<br />
m_line = ' '*l_cent+'/'<br />
m_line += ' '*(len(l_block[0]) - len(m_line))<br />
return [t_line, m_line]+l_block, len(t_line)-num_width//2<br />
#Otherwise, has both<br />
l_block, l_cent = tree_block(tree.left)<br />
r_block, r_cent = tree_block(tree.right)<br />
<br />
#Pad left block<br />
spacing = r_cent+len(l_block)-l_cent-2<br />
padding = ' '*max(1, (spacing-num_width))<br />
for line_index in range(len(l_block)):<br />
l_block[line_index] = l_block[line_index]+padding<br />
<br />
#Add left and right blocks<br />
new_block = []<br />
for line_index in range(max(len(l_block), len(r_block))):<br />
new_line = l_block[line_index] if line_index < len(l_block) else ' '*len(l_block[0])<br />
new_line += r_block[line_index] if line_index < len(r_block) else ' '*len(r_block[0])<br />
new_block.append(new_line)<br />
r_cent += len(l_block[0])<br />
<br />
#Generate top lines<br />
my_cent = (l_cent+r_cent)//2<br />
t_line = ' '*(l_cent+1)<br />
t_line += '-'*(my_cent-num_width//2-len(t_line))<br />
t_line += str(tree.entry)<br />
t_line += '-'*(r_cent-len(t_line))<br />
t_line += ' '*(len(new_block[0])-len(t_line))<br />
<br />
m_line = ' '*l_cent + '/'<br />
m_line += ' '*(r_cent-len(m_line)) + '\\'<br />
m_line += ' '*(len(new_block[0])-len(m_line))<br />
<br />
return [t_line, m_line]+new_block, my_cent<br />
</syntaxhighlight><br />
}}<br />
An empty tree is represented by <code>None</code>.<br />
<br />
Here is a function that searches a binary tree for an element:<br />
<syntaxhighlight lang="python"><br />
def find(t, elem):<br />
"""Returns true if ELEM is an entry in binary tree T."""<br />
if not t: # t is an empty tree<br />
return False<br />
if elem == t.entry:<br />
return True<br />
return find(t.left, elem) or find(t.right, elem) # look in both subtrees<br />
</syntaxhighlight><br />
<br />
=== Scheme ===<br />
Implementation:<br />
<syntaxhighlight lang="scheme"><br />
(define (tree entry left right)<br />
(list entry left right))<br />
<br />
(define (entry tree)<br />
(car tree))<br />
<br />
(define (left tree)<br />
(car (cdr tree)))<br />
<br />
(define (right tree)<br />
(car (cdr (cdr tree))))<br />
</syntaxhighlight><br />
An empty tree is represented by <code>nil</code> or <code>'()</code>.<br />
<br />
Here is a function that searches a binary tree for an element:<br />
<syntaxhighlight lang="scheme"><br />
(define (find t elem)<br />
(cond ((null? t) #f)<br />
((= elem (entry t)) #t)<br />
(else (or (find (left t) elem) (find (right t) elem)))))<br />
</syntaxhighlight><br />
<br />
=== Binary search tree (BST) ===<br />
The ''binary search tree'' (BST) is a special type of binary tree that satisfies the ''BST property'': for any node <code>n</code>, every key in <code>n</code>'s left subtree is less than <code>n</code>'s key, and every key in <code>n</code>'s right subtree is greater than <code>n</code>’s. No duplicate keys are allowed. Here is an example of a BST:<br />
[[File:BST example.png|left|200px]]<br />
{{clear}}<br />
<br />
[[File:Balanced vs unbalanced BST.png|thumb|right|350px|Balanced vs. unbalanced BST]]<br />
The advantage of the BST is that the major operations (search, insert, and remove) run in [[Order of growth|$\Theta(\log n)$ time]] if the BST is balanced, where $n$ is the number of nodes in the BST.<ref>A balanced BST has $\Theta(\log n)$ height. Searching, insertion, and removal are operations that traverse the BST's height, so these operations have a runtime of $\Theta(\log n)$.</ref> A BST is balanced if:<br />
# the number of nodes in its left branch differs from the number of nodes in its right branch by at most 1<br />
# its non-empty branches are also balanced trees<br />
<br />
However, if the BST is imbalanced (e.g., every node has only 1 child), the runtime of search, insert, and remove is $\Theta(n)$ at worst.<br />
<br />
Because of their efficiency as a data repository, BSTs are used to implement data structures such as [[set]]s or [[dictionary|dictionaries]]. For sets, the elements would be keys. For dictionaries, the key-value pairs would be keys.<br />
<br />
Here is a Python function for searching a BST for an element:<br />
<syntaxhighlight lang="python"><br />
def find(t, elem):<br />
"""Returns true if ELEM is an entry in BST T."""<br />
if not t: # t is an empty tree<br />
return False<br />
if elem == t.entry:<br />
return True<br />
if elem < t.entry:<br />
return find(t.left, elem) # look in left subtree<br />
return find(t.right, elem) # look in right subtree<br />
</syntaxhighlight><br />
Notice that we take advantage of the BST property by recursing only on one subtree instead of both.<br />
<br />
== Footnotes ==<br />
<references/><br />
<br />
== Sources ==<br />
* http://inst.eecs.berkeley.edu/~cs61a/sp14/lab/lab06/starter/trees.py<br />
* http://inst.eecs.berkeley.edu/~cs61a/sp14/lab/lab06/lab06.php<br />
* http://inst.eecs.berkeley.edu/~cs61a/sp14/disc/discussion07.pdf<br />
* http://inst.eecs.berkeley.edu/~cs61a/fa13/slides/17-Structure_6pp.pdf<br />
* http://www.cs.jhu.edu/~cohen/CS226/Lectures/Trees.pdf<br />
* https://inst.eecs.berkeley.edu/~cs61b/sp06/labs/s9-1-1.html<br />
* http://pages.cs.wisc.edu/~vernon/cs367/notes/8.TREES.html<br />
* http://www.openbookproject.net/thinkcs/python/english2e/ch21.html<br />
* http://mad-2victory.blogspot.com/2011/11/introduction-to-data-abstraction-and.html<br />
* http://www.eecs.berkeley.edu/~bh/ssch18/trees.html<br />
* http://www-inst.eecs.berkeley.edu/~cs61a/su11/disc/notes05.pdf<br />
* http://stackoverflow.com/questions/2130416/what-are-the-applications-of-binary-trees<br />
* http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html<br />
* http://inst.eecs.berkeley.edu/~cs61b/su06/lecnotes/lec17.pdf<br />
* http://ww0.java4.datastructures.net/handouts/Trees.pdf<br />
* http://www.cs.uiuc.edu/~mfleck/building-blocks/version-1.0/trees.pdf</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Summer_2014_Exam_2Summer 2014 Exam 22014-07-28T03:56:43Z<p>Axis: /* Topics */ link</p>
<hr />
<div>{{purge}}<br />
<br />
== Logistics ==<br />
Changes from Exam 1 are in '''bold'''.<br />
<br />
2050 VLSB, 7pm - 9pm on Thursday, '''July 31, 2014'''. Fill out the [https://docs.google.com/forms/d/15EC0TjCmun27Kp-w2i6Nz0IisUmRoStpUnzXeqhamgg/viewform?usp=send_form Exam 2 Conflict Form] if you have a conflict.<br />
<br />
Bring<br />
* pencil and eraser<br />
* '''two''' front and back 8.5x11" cheatsheet'''s (the idea is you bring your old cheatsheet and one new one)'''<br />
* a copy of [http://ocf.berkeley.edu/~shidi/cs61a/guerrilla/env.txt The Rules]<br />
** You can write on your copy of The Rules (8.5x11"), giving you '''3''' cheatsheets total.<br />
<br />
Don't bring<br />
* Any sort of electronics<br />
** Cell phones are okay, but must be turned off for the duration of the exam<br />
<br />
== Topics ==<br />
<br />
New topics for Exam 2:<br />
{| class="wikitable"<br />
! Exam 2 Topics<br />
|-<br />
| [[nonlocal]] and functions using nonlocal<br />
|-<br />
| Mutable Python data structures and functions on them ([[Sequence#Mutable_sequences|List]], [[Dictionary]])<br />
|-<br />
| [[Environment diagram|Environment diagrams]] on the above<br />
|-<br />
| [[Object-oriented programming|Object Oriented Programming]]<br />
|-<br />
| Interfaces and [[Magic method|'Magic' methods]]<br />
|-<br />
| [[Linked_list#OOP_ADT | Linked Lists]] (Known as Rlists in previous semesters)<br />
|-<br />
| [[Tree#Mutable Tree (OOP)|(Mutable) Trees]] (the kind with datum and children attributes)<br />
|-<br />
| [[Tree#Python_2|Binary Trees]] (the kind with entry, left, and right)<br />
|-<br />
| [[Iterator]]s, [[Iterable]]s and [[Generator]]s<br />
|-<br />
| [[Generic function]]s<br />
|-<br />
| [[Interpreter]]s<br />
|-<br />
| [[Scheme]]<br />
|}<br />
<br />
Topics from Exam 1 (you are expected to know these, but they will not be the focus of the exam):<br />
{| class="wikitable mw-collapsible mw-collapsed"<br />
! Exam 1 Topics<br />
|-<br />
| [[Python]] Basics<br />
* [[expression]]s<br />
* [[Statement#Conditional_statements|if statement]]<br />
* [[Iteration#While_loop | while statement]]<br />
* [[Statement#Assignment_statement | assignment statement]]<br />
* [[Statement#Function_definition | def statement]]<br />
* [[Boolean#Boolean | booleans]]<br />
* [[Number#Number | numbers]]<br />
* [[String#String | strings]]<br />
* [[Function]]s<br />
* [[Expression#Call_expressions | Function Call Evaluation]]<br />
|-<br />
| [[Higher-order function]]s and [[Lambda | Lambda expressions]]<br />
|-<br />
| [[ Recursion ]]<br />
|-<br />
| [[Linked list]]s (ignore tuples and OOP); Also known as <code>rlists</code> in other semesters.<br />
|-<br />
| [[Recursion#Tree recursion|Tree Recursion]]<br />
|-<br />
| [[Environment]]s / [[Environment diagram]]s (Note that our Env. Diagrams are compatible with Fall 2012 and onward.)<br />
|-<br />
| [[Sequence]]s<br />
|-<br />
| [[Abstract data type]]s<br />
|-<br />
| [[Trees]] (We haven't covered BSTs or Trees in Scheme)<br />
|-<br />
| [[Linked list#Types | Deep lists]]<br />
|-<br />
| [[Orders of growth]]<br />
|-<br />
| [[Newton's method]]<br />
|-<br />
| [[Halting problem]] (Extra Credit)<br />
|}<br />
<br />
== Other skills ==<br />
* '''Draw Box and pointer diagrams for mutable data structures'''<br />
* '''Drawing Environment diagrams with nonlocal'''<br />
* '''Reading the problem critically/figuring out what the problem is asking'''<br />
* '''Understanding doctests'''<br />
* Designing classes for Object Oriented Programming problems<br />
<br />
All the skills from Exam 1 still apply:<br />
<br />
* Identifying the Operator and Operands<br />
* Drawing Function Boxes<br />
* '''Identifying Domain and Range'''<br />
* '''Drawing Box and Pointers'''<br />
* '''Environment Diagrams'''<br />
* Identifying the Theta of a function<br />
<br />
== Practice Problems ==<br />
* [https://docs.google.com/document/d/1Zi-IM4Ptq2ymN0qtM6axqWryQpLLNthMZNoXKZBuu2E/edit?usp=sharing Andrew's Midterm 2 Warmup Questions]<br />
* [https://d1b10bmlvqabco.cloudfront.net/attach/hv3d500fcvs4d8/hktwxogd3mt47t/hxtvand63zl7/midtermdisc01.pdf Matthew's Week 4 Practice Problems] ([https://d1b10bmlvqabco.cloudfront.net/attach/hv3d500fcvs4d8/hktwxogd3mt47t/hxxzmp0tdtiv/midtermdisc01_sol.pdf solutions])<br />
*[https://d1b10bmlvqabco.cloudfront.net/attach/hv3d500fcvs4d8/hktwxogd3mt47t/hy3yuivujmg9/week05review.pdf Matthew's Week 5 Practice Problems]<br />
* [http://tinyurl.com/q5c7cnl Youri/Beth's Review ]<br />
* [[Practice problems]] from previous semesters, especially...<br />
** [https://www.dropbox.com/s/z6nlsgp0chfd6fc/environment_review.pdf Environment Diagram Review]<br />
** [http://albertwu.org/cs61a/review/ Albert's website]<br />
** [http://markmiyashita.com/cs61a/ Mark's website]<br />
<br />
=== Guerrilla 61A ===<br />
* [https://piazza.com/class/hv3d500fcvs4d8?cid=1114 Object Oriented Programming and Recursive Objects]<br />
* [https://piazza.com/class/hv3d500fcvs4d8?cid=977 Sequences, nonlocal and Objects]<br />
<br />
=== Staff Guides and Websites ===<br />
* [http://youripark.github.io/practice.html Youri's website]<br />
* [http://www.dicksontsai.com/cs61a/practiceproblems.html Dickson's website]<br />
* [https://d1b10bmlvqabco.cloudfront.net/attach/hoxc5uu6sud761/gozdkhgdUbT/htdlpko411i0/Python__Immutable_vs_Mutable.pdf Quick Guide on Mutability]<br />
* [http://www.ocf.berkeley.edu/~shidi/cs61a/wiki/For_Loops_and_Iterators Rohin's Guide on For Loops and Iterators]<br />
* [https://piazza.com/class/hv3d500fcvs4d8?cid=109 Piazza's Useful posts and guides ]<br />
<br />
=== Weekend Review ===<br />
* [http://tinyurl.com/kxvgnsk Week 1-3 stuff] '''This is LOW priority! The other questions above and below are a better use of your time.'''<br />
<br />
===Problems to Focus on from [[Past exams]]===<br />
Can be sorted by year or by Topic! (Default is by topic)<br />
<strong>Note: Replace Rlist with Link</strong><br />
{| class="wikitable sortable"<br />
! Question<br />
! Topic<br />
|-<br />
| Summer 2013 Midterm 2 (3a)<br />
| Environment Diagrams with Mutable Objects<br />
|-<br />
| Fall 2013 Midterm 2 (2b)<br />
| Environment Diagrams with Mutable Objects<br />
|-<br />
| Summer 2013 Final (3a)<br />
| Environment Diagrams with Mutable Objects<br />
|-<br />
| Spring 2013 Midterm 2 (1a)<br />
| Environment Diagrams with Mutable Objects<br />
|-<br />
| Spring 2013 Final (2)<br />
| Environment Diagrams with Mutable Objects<br />
|-<br />
| Fall 2012 Midterm 2 (2b)<br />
| Environment Diagrams with Mutable Objects<br />
|-<br />
| Summer 2013 Midterm 2 (3b)<br />
| Environment Diagrams with Nonlocal<br />
|-<br />
| Summer 2013 Final (3a)<br />
| Environment Diagrams with Nonlocal<br />
|-<br />
| Fall 2013 Midterm 2 (2a)<br />
| Environment Diagrams with Nonlocal<br />
|-<br />
| Spring 2013 Midterm 2 (2a)<br />
| Environment Diagrams with Nonlocal<br />
|-<br />
| Fall 2012 Midterm 2 (2a)<br />
| Environment Diagrams with Nonlocal<br />
|-<br />
| Fall 2012 Final (2b)<br />
| Environment Diagrams with Nonlocal<br />
|-<br />
| Summer 2012 Final (8)<br />
| Environment Diagrams with Nonlocal<br />
|-<br />
| Fall 2011 Midterm 2 (1b)<br />
| Environment Diagrams with Nonlocal<br />
|-<br />
| Fall 2011 Final (2a)<br />
| Environment Diagrams with Nonlocal<br />
|-<br />
| Summer 2012 Midterm 2 (2)<br />
| Using Nonlocal<br />
|-<br />
| Fall 2011 Midterm 2 (1a)<br />
| Using Nonlocal<br />
|-<br />
| Fall 2013 Midterm 2 (1)<br />
| Python Lists<br />
|-<br />
| Summer 2013 Midterm 2 (1)<br />
| Python Lists<br />
|-<br />
| Fall 2013 Final (2a)<br />
| Python Lists<br />
|-<br />
| Fall 2012 Midterm 2 (1a, 4b)<br />
| Python Lists<br />
|-<br />
| Fall 2012 Final (1a)<br />
| Python Lists<br />
|-<br />
| Summer 2012 Midterm 2 (1)<br />
| Python Lists<br />
|-<br />
| Fall 2011 Midterm 2 (2)<br />
| Python Lists<br />
|-<br />
| Summer 2013 Midterm 2 (4)<br />
| Dictionaries<br />
|-<br />
| Summer 2012 Final (11)<br />
| Dictionaries<br />
|-<br />
| Summer 2013 Midterm 2 (5, 6)<br />
| Trees<br />
|-<br />
| Fall 2013 Midterm 2 (3c)<br />
| Trees<br />
|-<br />
| Fall 2013 Final (4c, see r_list object in 4b)<br />
| Trees<br />
|-<br />
| Spring 2013 Final (1)<br />
| Trees<br />
|-<br />
| Fall 2012 Midterm 2 (3b)<br />
| Trees<br />
|-<br />
| Fall 2012 Final (3b, 3d)<br />
| Trees<br />
|-<br />
| Fall 2011 Midterm 2 (4e)<br />
| Trees<br />
|-<br />
| Summer 2013 Final (2, 6)<br />
| Object Oriented Programming<br />
|-<br />
| Spring 2013 Midterm 2 (1b, 5)<br />
| Object Oriented Programming<br />
|-<br />
| Fall 2013 Midterm 2 (3a, 4)<br />
| Object Oriented Programming<br />
|-<br />
| Fall 2013 Final (4b)<br />
| Object Oriented Programming<br />
|-<br />
| Spring 2013 Final (5)<br />
| Object Oriented Programming<br />
|-<br />
| Fall 2012 Midterm 2 (1b, 3a)<br />
| Object Oriented Programming<br />
|-<br />
| Fall 2012 Final (3a)<br />
| Object Oriented Programming<br />
|-<br />
| Summer 2012 Midterm 2 (4, 5)<br />
| Object Oriented Programming<br />
|-<br />
| Summer 2012 Final (9)<br />
| Object Oriented Programming<br />
|-<br />
| Fall 2011 Midterm 2 (3)<br />
| Object Oriented Programming<br />
|-<br />
| Fall 2011 Final (1)<br />
| Object Oriented Programming<br />
|-<br />
| Spring 2013 Midterm 2 (4)<br />
| Iterators and Generators<br />
|-<br />
| Summer 2013 Final (9b)<br />
| Iterators and Generators<br />
|-<br />
| Fall 2011 Final (6a)<br />
| Iterators and Generators<br />
|-<br />
| Summer 2013 Final (4)<br />
| Generic Functions<br />
|-<br />
| Summer 2013 Midterm 2 (2)<br />
| Orders of Growth<br />
|-<br />
| Summer 2012 Final (2)<br />
| Orders of Growth<br />
|-<br />
| Fall 2013 Final (3e)<br />
| Calculator<br />
|-<br />
| Summer 2013 Midterm 2 (7)<br />
| Scheme<br />
|-<br />
| Fall 2013 Final (1c)<br />
| Scheme<br />
|-<br />
|}<br />
<br />
== How to study ==<br />
<pre>Here is an old algorithm for studying for tests:<br />
For each topic on the exam, find problems on them and do them.<br />
START ON THE TOPICS YOU'RE MOST UNFAMILIAR WITH!<br />
If you can solve them on your own, move on.<br />
Else if you are stuck, look at the solution and figure out if you<br />
are missing a trick or if you do not understand the concepts.<br />
If the problem is that you are stuck on some random trick,<br />
just learn the trick.<br />
Stare at the solutions, ask Piazza, your TA, etc.<br />
Questions you should ask at this stage:<br />
What is the problem asking me to do?<br />
How was I suppose to follow the instructions<br />
to solve the problem?<br />
What part of the problem do I not understand?<br />
What is the fastest way to clear up that misunderstanding?<br />
Then if you think you are still stuck conceptually, review<br />
and learn the concept, however you learn best.<br />
<br />
Suggestions for picking up concepts quickly (~1-2 hours):<br />
Discussion notes typically have a very concise recap of the<br />
thing they are going over.<br />
There are guides for particularly tricky things on the wiki,<br />
like Hanoi, powerset, etc.<br />
Find them and go over them.<br />
Ask a TA: "what is the best way to learn X?"<br />
If these do not work and you are still shaky after an hour<br />
or two, it might be worth watching a lecture or reading<br />
the notes. Be sure to try out some more problems as you're learning!</pre></div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/NonlocalNonlocal2014-07-28T03:56:13Z<p>Axis: Redirected page to Statement#global and nonlocal</p>
<hr />
<div>#REDIRECT [[Statement#global and nonlocal]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/TryTry2014-07-25T23:00:09Z<p>Axis: Redirected page to Exception#Handling an exception</p>
<hr />
<div>#REDIRECT [[Exception#Handling an exception]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Generic_functionGeneric function2014-07-25T06:42:44Z<p>Axis: {{C-class}}</p>
<hr />
<div>{{C-class}}<br />
A '''generic function''' is a function that can operate on multiple types of data. This is especially useful when the objects we are working with have multiple representations. A good example is [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.g3901816cf_022 the variety of number representations] we learned in lecture.<br />
<br />
== Techniques ==<br />
The following are techniques for creating generic functions:<br />
<br />
=== Interfaces ===<br />
An interface manipulates different data types with the same function. For example, the <code>+</code> operator works with numbers, strings, and lists:<br />
<syntaxhighlight lang="python"><br />
>>> 1 + 2<br />
3<br />
>>> 'hi ' + 'there'<br />
'hi there'<br />
>>> [1, 2] + [3, 4]<br />
[1, 2, 3, 4]<br />
</syntaxhighlight><br />
<br />
=== Type dispatching ===<br />
''Type dispatching'' is a technique in which a function checks the type of the argument passed in and then executes code that is appropriate for the type. To accomplish this, we define a function for each type-operation combination.<br />
<br />
For example, consider the following <code>drive</code> function, which takes in a variety of <code>car</code> types and returns the correct <code>drive</code> method depending on the type given:<br />
<syntaxhighlight lang="python"><br />
def drive(car):<br />
if type(car) == SportsCar:<br />
return car.drive_sportscar()<br />
elif type(car) == Van:<br />
return car.drive_van()<br />
elif type(car) == SemiTruck:<br />
return car.drive_semitruck()<br />
elif type(car) == Tractor:<br />
return car.drive_tractor()<br />
</syntaxhighlight><br />
<br />
==== Tag-based ====<br />
We can implement type dispatching using dictionaries. We define a function <code>type_tag</code> that returns a "tag" representing the type of the argument (the tag is stored in the <code>tags</code> dictionary):<br />
<syntaxhighlight lang="python"><br />
def type_tag(x):<br />
return tags[type(x)]<br />
<br />
tags = {<br />
<type1> : <tag1><br />
<type2> : <tag2><br />
...<br />
}<br />
</syntaxhighlight><br />
<br />
We also define a dictionary <code>implementations</code> that maps from a tuple of the two types to the function that carries out the operation on those types.<br />
<syntaxhighlight lang="python"><br />
implementations = {<br />
(<tag1>, <tag1>): <fn1>,<br />
(<tag1>, <tag2>): <fn2>,<br />
(<tag2>, <tag2>): <fn3><br />
}<br />
</syntaxhighlight><br />
<br />
Then we can write a generic function as follows:<br />
<syntaxhighlight lang="python"><br />
def op(a, b):<br />
return implementations[(type_tag(a),type_tag(b))](a, b)<br />
</syntaxhighlight><br />
<br />
For example, here is a generic function to combine two lists (the two possible types are [[Linked list|<code>Link</code>]] and the built-in <code>[[list]]</code>):<ref>https://inst.eecs.berkeley.edu/~cs61a/sp13/labs/lab08/lab08.php</ref><br />
<syntaxhighlight lang="python"><br />
def type_tag(x):<br />
return tags[type(x)]<br />
<br />
tags = {<br />
list : 'list'<br />
Link : 'Link'<br />
}<br />
<br />
implementations = {<br />
('list', 'list'): lambda a, b: a.extend(b),<br />
('list', 'Link'): extend_list_with_link,<br />
('Link', 'Link'): extend_link_with_link,<br />
('Link', 'list'): extend_link_with_list<br />
}<br />
<br />
def extend(lst1, lst2):<br />
implementations[(type_tag(lst1), type_tag(lst2))](lst1, lst2)<br />
</syntaxhighlight><br />
<br />
<code>extend_list_with_link</code>, <code>extend_link_with_link</code>, and <code>extend_link_with_list</code> are not shown.<br />
<br />
=== Coercion ===<br />
''Coercion'' is converting object A into object B so that A can use B's methods. The general process is:<ref>http://inst.eecs.berkeley.edu/~cs61a/fa12/slides/19-Generics_1pps.pdf</ref><br />
# Attempt to coerce arguments into values of the same type<br />
# Apply type-specific operations<br />
<br />
Example:<ref>http://shire.keeganmann.com/~ta/review-typedispatch.html</ref> we have a class representing metric distances:<br />
<syntaxhighlight lang="python"><br />
class MetricDistance:<br />
def __init__(self, x):<br />
self.dist = x # assume x is in meters<br />
<br />
def compare(self, other):<br />
"""Returns '<', '>' or '=' when comparing self to other."""<br />
if self.dist < other.dist:<br />
return '<'<br />
elif self.dist == other.dist:<br />
return '='<br />
else:<br />
return '>'<br />
</syntaxhighlight><br />
<br />
We also have a class representing imperial distances:<br />
<syntaxhighlight lang="python"><br />
class ImperialDistance:<br />
def __init__(self, x):<br />
self.dist = x # assume x is in feet<br />
</syntaxhighlight><br />
<br />
We want to write a function to compare a <code>MetricDistance</code> and an <code>ImperialDistance</code>. Since <code>MetricDistance</code> already has a <code>compare</code> function, we coerce <code>ImperialDistance</code> to a <code>MetricDistance</code> so we can compare them:<br />
<syntaxhighlight lang="python"><br />
def coerce_imperial_to_metric(imperial):<br />
return MetricDistance(imperial.dist * 0.3048)<br />
<br />
def compare_imperial_and_metric(imperial, metric):<br />
return coerce_imperial_to_metric(imperial).compare(metric)<br />
</syntaxhighlight><br />
<br />
== Sources ==<br />
<references/><br />
* [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.p CS61A Su14 Lecture 17]<br />
* [http://inst.eecs.berkeley.edu/~cs61a/su14/discussion/discussion09/discussion09.pdf CS61A Su14 Discussion 9]<br />
* [http://wla.berkeley.edu/~cs61a/fa11/lectures/objects.html#generic-operations CS61A Fa11 2.7.3]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Generic_functionGeneric function2014-07-25T06:40:31Z<p>Axis: add examples</p>
<hr />
<div>{{Start-class}}<br />
A '''generic function''' is a function that can operate on multiple types of data. This is especially useful when the objects we are working with have multiple representations. A good example is [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.g3901816cf_022 the variety of number representations] we learned in lecture.<br />
<br />
== Techniques ==<br />
The following are techniques for creating generic functions:<br />
<br />
=== Interfaces ===<br />
An interface manipulates different data types with the same function. For example, the <code>+</code> operator works with numbers, strings, and lists:<br />
<syntaxhighlight lang="python"><br />
>>> 1 + 2<br />
3<br />
>>> 'hi ' + 'there'<br />
'hi there'<br />
>>> [1, 2] + [3, 4]<br />
[1, 2, 3, 4]<br />
</syntaxhighlight><br />
<br />
=== Type dispatching ===<br />
''Type dispatching'' is a technique in which a function checks the type of the argument passed in and then executes code that is appropriate for the type. To accomplish this, we define a function for each type-operation combination.<br />
<br />
For example, consider the following <code>drive</code> function, which takes in a variety of <code>car</code> types and returns the correct <code>drive</code> method depending on the type given:<br />
<syntaxhighlight lang="python"><br />
def drive(car):<br />
if type(car) == SportsCar:<br />
return car.drive_sportscar()<br />
elif type(car) == Van:<br />
return car.drive_van()<br />
elif type(car) == SemiTruck:<br />
return car.drive_semitruck()<br />
elif type(car) == Tractor:<br />
return car.drive_tractor()<br />
</syntaxhighlight><br />
<br />
==== Tag-based ====<br />
We can implement type dispatching using dictionaries. We define a function <code>type_tag</code> that returns a "tag" representing the type of the argument (the tag is stored in the <code>tags</code> dictionary):<br />
<syntaxhighlight lang="python"><br />
def type_tag(x):<br />
return tags[type(x)]<br />
<br />
tags = {<br />
<type1> : <tag1><br />
<type2> : <tag2><br />
...<br />
}<br />
</syntaxhighlight><br />
<br />
We also define a dictionary <code>implementations</code> that maps from a tuple of the two types to the function that carries out the operation on those types.<br />
<syntaxhighlight lang="python"><br />
implementations = {<br />
(<tag1>, <tag1>): <fn1>,<br />
(<tag1>, <tag2>): <fn2>,<br />
(<tag2>, <tag2>): <fn3><br />
}<br />
</syntaxhighlight><br />
<br />
Then we can write a generic function as follows:<br />
<syntaxhighlight lang="python"><br />
def op(a, b):<br />
return implementations[(type_tag(a),type_tag(b))](a, b)<br />
</syntaxhighlight><br />
<br />
For example, here is a generic function to combine two lists (the two possible types are [[Linked list|<code>Link</code>]] and the built-in <code>[[list]]</code>):<ref>https://inst.eecs.berkeley.edu/~cs61a/sp13/labs/lab08/lab08.php</ref><br />
<syntaxhighlight lang="python"><br />
def type_tag(x):<br />
return tags[type(x)]<br />
<br />
tags = {<br />
list : 'list'<br />
Link : 'Link'<br />
}<br />
<br />
implementations = {<br />
('list', 'list'): lambda a, b: a.extend(b),<br />
('list', 'Link'): extend_list_with_link,<br />
('Link', 'Link'): extend_link_with_link,<br />
('Link', 'list'): extend_link_with_list<br />
}<br />
<br />
def extend(lst1, lst2):<br />
implementations[(type_tag(lst1), type_tag(lst2))](lst1, lst2)<br />
</syntaxhighlight><br />
<br />
<code>extend_list_with_link</code>, <code>extend_link_with_link</code>, and <code>extend_link_with_list</code> are not shown.<br />
<br />
=== Coercion ===<br />
''Coercion'' is converting object A into object B so that A can use B's methods. The general process is:<ref>http://inst.eecs.berkeley.edu/~cs61a/fa12/slides/19-Generics_1pps.pdf</ref><br />
# Attempt to coerce arguments into values of the same type<br />
# Apply type-specific operations<br />
<br />
Example:<ref>http://shire.keeganmann.com/~ta/review-typedispatch.html</ref> we have a class representing metric distances:<br />
<syntaxhighlight lang="python"><br />
class MetricDistance:<br />
def __init__(self, x):<br />
self.dist = x # assume x is in meters<br />
<br />
def compare(self, other):<br />
"""Returns '<', '>' or '=' when comparing self to other."""<br />
if self.dist < other.dist:<br />
return '<'<br />
elif self.dist == other.dist:<br />
return '='<br />
else:<br />
return '>'<br />
</syntaxhighlight><br />
<br />
We also have a class representing imperial distances:<br />
<syntaxhighlight lang="python"><br />
class ImperialDistance:<br />
def __init__(self, x):<br />
self.dist = x # assume x is in feet<br />
</syntaxhighlight><br />
<br />
We want to write a function to compare a <code>MetricDistance</code> and an <code>ImperialDistance</code>. Since <code>MetricDistance</code> already has a <code>compare</code> function, we coerce <code>ImperialDistance</code> to a <code>MetricDistance</code> so we can compare them:<br />
<syntaxhighlight lang="python"><br />
def coerce_imperial_to_metric(imperial):<br />
return MetricDistance(imperial.dist * 0.3048)<br />
<br />
def compare_imperial_and_metric(imperial, metric):<br />
return coerce_imperial_to_metric(imperial).compare(metric)<br />
</syntaxhighlight><br />
<br />
== Sources ==<br />
<references/><br />
* [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.p CS61A Su14 Lecture 17]<br />
* [http://inst.eecs.berkeley.edu/~cs61a/su14/discussion/discussion09/discussion09.pdf CS61A Su14 Discussion 9]<br />
* [http://wla.berkeley.edu/~cs61a/fa11/lectures/objects.html#generic-operations CS61A Fa11 2.7.3]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Generic_functionGeneric function2014-07-25T05:11:13Z<p>Axis: copyedit; reword</p>
<hr />
<div>{{Start-class}}<br />
A '''generic function''' is a function that can operate on multiple types of data. This is especially useful when the objects we are working with have multiple representations. A good example is [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.g3901816cf_022 the variety of number representations] we learned in lecture.<br />
<br />
== Techniques ==<br />
The following are techniques for creating generic functions:<br />
<br />
=== Interfaces ===<br />
An interface manipulates different data types with the same function. For example, the <code>+</code> operator works with numbers, strings, and lists:<br />
<syntaxhighlight lang="python"><br />
>>> 1 + 2<br />
3<br />
>>> 'hi ' + 'there'<br />
'hi there'<br />
>>> [1, 2] + [3, 4]<br />
[1, 2, 3, 4]<br />
</syntaxhighlight><br />
<br />
=== Type dispatching ===<br />
''Type dispatching'' does exactly as its name suggests: depending on the type of the arguments passed in, the function will proceed in different ways. We create a function for each different combination of valid input types and then choose one to use by checking the types of arguments passed in.<br />
<br />
For example, consider the following <code>drive</code> function, which takes in a variety of <code>car</code> types and returns the correct <code>drive</code> method depending on the type given:<br />
<syntaxhighlight lang="python"><br />
def drive(car):<br />
if type(car) == SportsCar:<br />
return car.drive_sportscar()<br />
elif type(car) == Van:<br />
return car.drive_van()<br />
elif type(car) == SemiTruck:<br />
return car.drive_semitruck()<br />
elif type(car) == Tractor:<br />
return car.drive_tractor()<br />
</syntaxhighlight><br />
<br />
=== Coercion ===<br />
''Coercion'' is converting object A into object B so that A can use B's methods. This is useful when the two different objects have some similar properties and when the original object can be seen as the new type with certain modifications.<br />
<br />
Example:<br />
<br />
== Sources ==<br />
* [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.p CS61A Su14 Lecture 17]<br />
* [http://inst.eecs.berkeley.edu/~cs61a/su14/discussion/discussion09/discussion09.pdf CS61A Su14 Discussion 9]<br />
* [http://wla.berkeley.edu/~cs61a/fa11/lectures/objects.html#generic-operations CS61A Fa11 2.7.3]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Magic_methodMagic method2014-07-25T00:24:43Z<p>Axis: /* __getitem__ and __len__ */ add StopIteration</p>
<hr />
<div>{{Sufficient-class}}<br />
In [[Python]], a '''magic method''' is a special method surrounded by double underscores that is invoked when you use certain syntax.<br />
<br />
== <code>__init__</code> ==<br />
<code>[[init|__init__]]</code> is called when you call a class to create an instance.<br />
<br />
== <code>__iter__</code> and <code>__next__</code> ==<br />
<code>__iter__</code> and <code>__next__</code> implement the [[iterator]] protocol.<br />
<br />
== <code>__getitem__</code> and <code>__len__</code> ==<br />
<code>__getitem__</code> and <code>__len__</code> implement the [[sequence]] protocol.<br />
<br />
<code>__len__</code> is called by <code>len</code>, and <code>__getitem__</code> is called when you index into a sequence. Example:<br />
<syntaxhighlight lang="python"><br />
class Link:<br />
"""<br />
>>> lst = Link(1, Link(2, Link(3)))<br />
>>> lst[1] # calls lst.__getitem__(1)<br />
2<br />
>>> len(lst) # calls lst.__len__()<br />
3<br />
"""<br />
empty = None<br />
<br />
def __init__(self, first, rest=empty):<br />
self.first = first<br />
self.rest = rest<br />
<br />
def __len__(self):<br />
if self.rest is not Link.empty:<br />
return 1 + len(self.rest)<br />
return 1<br />
<br />
def __getitem__(self, i):<br />
if i == 0:<br />
return self.first<br />
elif self.rest is not Link.empty:<br />
return self.rest[i - 1]<br />
else:<br />
raise StopIteration<br />
</syntaxhighlight><br />
<br />
== <code>__str__</code> and <code>__repr__</code> ==<br />
<code>__str__</code> and <code>__repr__</code> implement the string representation protocol.<br />
<br />
The <code>repr</code> string is Python-readable, while the <code>str</code> string is human-readable. <code>repr</code> is what Python displays in an interactive session, and <code>str</code> is what Python prints using the <code>print</code> function.<ref>http://inst.eecs.berkeley.edu/~cs61a/su14/lecture/15/without_animation.pdf</ref><br />
<br />
Example:<br />
<syntaxhighlight lang="python"><br />
class Link:<br />
"""<br />
>>> lst = Link(1, Link(2, Link(3)))<br />
>>> lst # calls lst.__repr__()<br />
Link(1, Link(2, Link(3)))<br />
>>> print(lst) # calls lst.__str__()<br />
< 1 2 3 ><br />
"""<br />
empty = None<br />
<br />
def __init__(self, first, rest=empty):<br />
self.first = first<br />
self.rest = rest<br />
<br />
def __repr__(self):<br />
if self.rest is Link.empty:<br />
rest = ''<br />
else:<br />
rest = ', ' + repr(self.rest)<br />
return 'Link({}{})'.format(self.first, rest)<br />
<br />
def __str__(self):<br />
if self.rest is Link.empty:<br />
rest = ''<br />
else:<br />
rest = ' ' + str(self.rest)[2:-2]<br />
return '< {}{} >'.format(self.first, rest)<br />
</syntaxhighlight><br />
<br />
== Sources ==<br />
<references><br />
<br />
== External links ==<br />
* http://www.diveintopython3.net/special-method-names.html</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Talk:Magic_methodTalk:Magic method2014-07-25T00:22:46Z<p>Axis: {{Talk page guidelines}}</p>
<hr />
<div>{{Talk page guidelines}}</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Magic_methodMagic method2014-07-25T00:22:31Z<p>Axis: {{Sufficient-class}}</p>
<hr />
<div>{{Sufficient-class}}<br />
In [[Python]], a '''magic method''' is a special method surrounded by double underscores that is invoked when you use certain syntax.<br />
<br />
== <code>__init__</code> ==<br />
<code>[[init|__init__]]</code> is called when you call a class to create an instance.<br />
<br />
== <code>__iter__</code> and <code>__next__</code> ==<br />
<code>__iter__</code> and <code>__next__</code> implement the [[iterator]] protocol.<br />
<br />
== <code>__getitem__</code> and <code>__len__</code> ==<br />
<code>__getitem__</code> and <code>__len__</code> implement the [[sequence]] protocol.<br />
<br />
<code>__len__</code> is called by <code>len</code>, and <code>__getitem__</code> is called when you index into a sequence. Example:<br />
<syntaxhighlight lang="python"><br />
class Link:<br />
"""<br />
>>> lst = Link(1, Link(2, Link(3)))<br />
>>> lst[1] # calls lst.__getitem__(1)<br />
2<br />
>>> len(lst) # calls lst.__len__()<br />
3<br />
"""<br />
empty = None<br />
<br />
def __init__(self, first, rest=empty):<br />
self.first = first<br />
self.rest = rest<br />
<br />
def __len__(self):<br />
if self.rest is not Link.empty:<br />
return 1 + len(self.rest)<br />
return 1<br />
<br />
def __getitem__(self, i):<br />
if i == 0:<br />
return self.first<br />
return self.rest[i - 1]<br />
</syntaxhighlight><br />
<br />
== <code>__str__</code> and <code>__repr__</code> ==<br />
<code>__str__</code> and <code>__repr__</code> implement the string representation protocol.<br />
<br />
The <code>repr</code> string is Python-readable, while the <code>str</code> string is human-readable. <code>repr</code> is what Python displays in an interactive session, and <code>str</code> is what Python prints using the <code>print</code> function.<ref>http://inst.eecs.berkeley.edu/~cs61a/su14/lecture/15/without_animation.pdf</ref><br />
<br />
Example:<br />
<syntaxhighlight lang="python"><br />
class Link:<br />
"""<br />
>>> lst = Link(1, Link(2, Link(3)))<br />
>>> lst # calls lst.__repr__()<br />
Link(1, Link(2, Link(3)))<br />
>>> print(lst) # calls lst.__str__()<br />
< 1 2 3 ><br />
"""<br />
empty = None<br />
<br />
def __init__(self, first, rest=empty):<br />
self.first = first<br />
self.rest = rest<br />
<br />
def __repr__(self):<br />
if self.rest is Link.empty:<br />
rest = ''<br />
else:<br />
rest = ', ' + repr(self.rest)<br />
return 'Link({}{})'.format(self.first, rest)<br />
<br />
def __str__(self):<br />
if self.rest is Link.empty:<br />
rest = ''<br />
else:<br />
rest = ' ' + str(self.rest)[2:-2]<br />
return '< {}{} >'.format(self.first, rest)<br />
</syntaxhighlight><br />
<br />
== Sources ==<br />
<references><br />
<br />
== External links ==<br />
* http://www.diveintopython3.net/special-method-names.html</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Magic_methodMagic method2014-07-25T00:22:07Z<p>Axis: created</p>
<hr />
<div>In [[Python]], a '''magic method''' is a special method surrounded by double underscores that is invoked when you use certain syntax.<br />
<br />
== <code>__init__</code> ==<br />
<code>[[init|__init__]]</code> is called when you call a class to create an instance.<br />
<br />
== <code>__iter__</code> and <code>__next__</code> ==<br />
<code>__iter__</code> and <code>__next__</code> implement the [[iterator]] protocol.<br />
<br />
== <code>__getitem__</code> and <code>__len__</code> ==<br />
<code>__getitem__</code> and <code>__len__</code> implement the [[sequence]] protocol.<br />
<br />
<code>__len__</code> is called by <code>len</code>, and <code>__getitem__</code> is called when you index into a sequence. Example:<br />
<syntaxhighlight lang="python"><br />
class Link:<br />
"""<br />
>>> lst = Link(1, Link(2, Link(3)))<br />
>>> lst[1] # calls lst.__getitem__(1)<br />
2<br />
>>> len(lst) # calls lst.__len__()<br />
3<br />
"""<br />
empty = None<br />
<br />
def __init__(self, first, rest=empty):<br />
self.first = first<br />
self.rest = rest<br />
<br />
def __len__(self):<br />
if self.rest is not Link.empty:<br />
return 1 + len(self.rest)<br />
return 1<br />
<br />
def __getitem__(self, i):<br />
if i == 0:<br />
return self.first<br />
return self.rest[i - 1]<br />
</syntaxhighlight><br />
<br />
== <code>__str__</code> and <code>__repr__</code> ==<br />
<code>__str__</code> and <code>__repr__</code> implement the string representation protocol.<br />
<br />
The <code>repr</code> string is Python-readable, while the <code>str</code> string is human-readable. <code>repr</code> is what Python displays in an interactive session, and <code>str</code> is what Python prints using the <code>print</code> function.<ref>http://inst.eecs.berkeley.edu/~cs61a/su14/lecture/15/without_animation.pdf</ref><br />
<br />
Example:<br />
<syntaxhighlight lang="python"><br />
class Link:<br />
"""<br />
>>> lst = Link(1, Link(2, Link(3)))<br />
>>> lst # calls lst.__repr__()<br />
Link(1, Link(2, Link(3)))<br />
>>> print(lst) # calls lst.__str__()<br />
< 1 2 3 ><br />
"""<br />
empty = None<br />
<br />
def __init__(self, first, rest=empty):<br />
self.first = first<br />
self.rest = rest<br />
<br />
def __repr__(self):<br />
if self.rest is Link.empty:<br />
rest = ''<br />
else:<br />
rest = ', ' + repr(self.rest)<br />
return 'Link({}{})'.format(self.first, rest)<br />
<br />
def __str__(self):<br />
if self.rest is Link.empty:<br />
rest = ''<br />
else:<br />
rest = ' ' + str(self.rest)[2:-2]<br />
return '< {}{} >'.format(self.first, rest)<br />
</syntaxhighlight><br />
<br />
== Sources ==<br />
<references><br />
<br />
== External links ==<br />
* http://www.diveintopython3.net/special-method-names.html</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Linked_listLinked list2014-07-25T00:18:27Z<p>Axis: /* OOP ADT */ fix __str__ method; copyedit</p>
<hr />
<div>{{Start-class}}<br />
A '''linked list''' is a recursive data structure that represents a sequence of elements. It consists of a series of nodes. Each node contains a piece of data, as well as a pointer to the next node. The last element in the list is the empty linked list. The piece of data is called the "first" field of that linked list, and the pointer to the next node is called the "rest" field.<br />
<br />
== Types ==<br />
In a ''straight-forward'' linked list, a node's first field contains a value (string, number, etc.), while the second field will contain another linked list. Using this structure, a series of nested linked lists can form a list of values.<br />
<br />
A ''deep'' linked list is slightly different. The first and second fields contain another linked list. A good way to visualize linked lists is to draw them out. <!-- add example --><br />
<br />
[[File:Deep_list.png|alt=A deep list is a linked list with possibly another linked list as an element of the linked list. We have a deep list in this picture because the third (and final) element of this list is another linked list: <code>link(3, link(4, empty))</code>]]<br />
<br />
== ADT and implementations ==<br />
The ADT of a linked list is independent of its implementation.<br />
<br />
=== Functional ADT ===<br />
The ADT of a linked list is independent of its implementation. The functions are:<br />
* <code>link(elem, list)</code> – returns a linked list with <code>elem</code> as the first item and <code>list</code> as the rest of the list<br />
* <code>first(list)</code> – returns the first field of linked list <code>list</code><br />
* <code>rest(list)</code> – returns the rest field of linked list <code>list</code><br />
* <code>empty</code> – the empty linked list<br />
<br />
The following are implementations of the ADT:<br />
* with tuples:<br />
<blockquote style="margin: 1em 1.6em;"><syntaxhighlight lang="python"><br />
empty = lambda: 42<br />
<br />
def link(element, list=empty):<br />
return (element, list)<br />
<br />
def first(list):<br />
return list[0]<br />
<br />
def rest(list):<br />
return list[1]<br />
</syntaxhighlight></blockquote><br />
* with <code>cons</code>:<br />
<blockquote style="margin: 1em 1.6em;"><syntaxhighlight lang="python"><br />
empty = lambda: 42<br />
<br />
def link(element, list=empty):<br />
return cons(element, list)<br />
<br />
def first(list):<br />
return car(list)<br />
<br />
def rest(list):<br />
return cdr(list)<br />
</syntaxhighlight></blockquote><br />
<br />
=== OOP ADT ===<br />
The [[Object-oriented programming|OOP]] ADT is:<br />
* <code>Link(elem, list)</code> – returns a linked list with <code>elem</code> as the first item and <code>list</code> as the rest of the list<br />
* <code>list.first</code> – returns the first field of linked list <code>list</code><br />
* <code>list.rest</code> – returns the rest field of linked list <code>list</code><br />
* <code>Link.empty</code> – the empty linked list<br />
<br />
The basic code can be seen below. Note that <code>list.first</code> and <code>list.rest</code> are implemented as instance attributes, <code>Link.empty</code> as a class attribute, and <code>Link(first, rest)</code> via <code>__init__</code>:<br />
<syntaxhighlight lang="python"><br />
class Link:<br />
"""A recursive list, with Python integration."""<br />
empty = None<br />
<br />
def __init__(self, first, rest=empty):<br />
self.first = first<br />
self.rest = rest<br />
<br />
def __repr__(self):<br />
if self.rest is Link.empty:<br />
rest = ''<br />
else:<br />
rest = ', ' + repr(self.rest)<br />
return 'Link({}{})'.format(self.first, rest)<br />
<br />
def __str__(self):<br />
if self.rest is Link.empty:<br />
rest = ''<br />
else:<br />
rest = ' ' + str(self.rest)[2:-2]<br />
return '< {}{} >'.format(self.first, rest)<br />
</syntaxhighlight><br />
<br />
== Operations ==<br />
The recursive structure of a linked list suggests recursive algorithms for operations. Generally, the base case will be if the current node is the empty list. The recursive step will involve recursing on the rest of the list.<br />
<br />
A linked list can also be operated on using iteration: a while loop that continues until the current node is the empty list and repeatedly updating a variable to the rest of the list.<br />
<br />
==Examples==<br />
Here is a function that prints a linked list in a readable format:<br />
<syntaxhighlight lang="python"><br />
def print_linked_list(lst):<br />
"""Prints linked list LST.<br />
>>> lst = link(3, link(1, link(5, link(3))))<br />
>>> print_linked_list(lst)<br />
< 3 1 5 3 ><br />
"""<br />
s = '< '<br />
while lst != empty:<br />
s = s + repr(first(lst)) + ' '<br />
lst = rest(lst)<br />
print(s[:-1] + ' >')<br />
</syntaxhighlight><br />
<br />
Here is a function that searches a linked list for a given item:<br />
<syntaxhighlight lang="python"><br />
def contains(lst, elem):<br />
"""Returns True if linked list LST contains ELEM.<br />
>>> lst = link(3, link(1, link(5, link(3))))<br />
>>> contains(lst, 5)<br />
True<br />
>>> contains(lst, 4)<br />
False<br />
"""<br />
if lst == empty:<br />
return False<br />
return first(lst) == elem or contains(rest(lst), elem)<br />
</syntaxhighlight><br />
<br />
Here is a function that returns a new linked list that is the reverse of the one passed in:<br />
<syntaxhighlight lang="python"><br />
def reverse(lst):<br />
"""Returns a new list that is the reverse of LST.<br />
>>> print_linked_list(reverse(link(3, link(1, link(5, link(3))))))<br />
< 3 5 1 3 ><br />
"""<br />
reversed = empty<br />
while lst != empty:<br />
reversed = link(first(lst), reversed)<br />
lst = rest(lst)<br />
return reversed<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
* https://docs.google.com/presentation/d/1qqgY3wk5r0KFnVTjsP8R9dNNaXisGzljXwAaSza1948/edit</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Talk:ExceptionTalk:Exception2014-07-24T23:51:41Z<p>Axis: {{Talk page guidelines}}</p>
<hr />
<div>{{Talk page guidelines}}</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ExceptionException2014-07-24T23:51:27Z<p>Axis: {{Sufficient-class}}</p>
<hr />
<div>{{Sufficient-class}}<br />
An '''exception''' is an [[object]] that represents an error.<ref>https://docs.google.com/presentation/d/1j_a3kWQwnqyFRo5ud1iJUzVKPK37JkQna9_m9h2u7O0/edit#slide=id.g38ed26997_126</ref> Exceptions are ''raised'' either automatically by Python or explicitly by the programmer.<br />
<br />
This is a full list of exceptions: https://docs.python.org/3/library/exceptions.html#bltin-exceptions.<br />
<br />
== Types ==<br />
There are two different types of exceptions: ones that happen when the program is being parsed by Python (<code>SyntaxError</code>, <code>IndentationError</code>), and ones that happen when the program is running (runtime exceptions).<br />
<br />
== Raising an exception ==<br />
Use the <code>raise</code> statement. Example:<br />
<syntaxhighlight lang="python"><br />
>>> while True:<br />
... num = int(input("Enter a number between 1 and 10:\n"))<br />
... if not 1 <= num <= 10:<br />
... raise ValueError("Number out of range")<br />
... <br />
Enter a number between 1 and 10:<br />
5<br />
Enter a number between 1 and 10:<br />
0<br />
Traceback (most recent call last):<br />
...<br />
ValueError: Number out of range<br />
</syntaxhighlight><br />
<br />
== Handling an exception ==<br />
Runtime exceptions can be caught. We use the <code>try</code>-<code>except</code> construct to handle an exception. If an error is encountered in the <code>try</code> block, execution stops and is transferred to the except block. <br />
<br />
Example:<br />
<syntaxhighlight lang="python"><br />
>>> try:<br />
... print(1/0)<br />
... except ZeroDivisionError:<br />
... print("Can't divide by zero!")<br />
... <br />
Can't divide by zero!<br />
</syntaxhighlight><br />
<br />
There can be multiple <code>except</code> clauses for different types of exceptions. An <code>except</code> clause can also not have an exception specified, in which case it would handle all runtime exceptions. Example:<br />
<syntaxhighlight lang="python"><br />
>>> try:<br />
... lst = None<br />
... lst.append(2)<br />
... except:<br />
... print("Something bad happened!")<br />
... <br />
Something bad happened!<br />
</syntaxhighlight><br />
<br />
== Sources ==<br />
<references></div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StatementStatement2014-07-24T23:50:08Z<p>Axis: fix links</p>
<hr />
<div>{{C-class}} {{Basics sidebar}}<br />
A '''statement''' is an instruction that the [[Python]] interpreter executes. Statements do not return a value; they are simply executed. They change the state of or control the program.<br />
<br />
== Simple statements ==<br />
A simple statement fits on one line. Simple statements may occur on a single line separated by semicolons.<br />
<br />
=== Assignment statement ===<br />
An assignment statement is used to bind variable names to values and to modify attributes of mutable objects.<br />
<br />
The <code>=</code> operator is used:<br />
<syntaxhighlight lang="python"><br />
var = val<br />
</syntaxhighlight><br />
Python also supports multiple assignment:<br />
<syntaxhighlight lang="python"><br />
var1, var2 = val1, val2 # equivalent to:<br />
# var1 = val1<br />
# var2 = val2<br />
</syntaxhighlight><br />
<br />
An assignment is executed in the following way:<br />
* evaluate the right of the equals sign<br />
* bind the name(s) on the left to the resulting value<br />
<br />
If a name is already bound to a value, the old value is overwritten by the new value. Example:<br />
<syntaxhighlight lang="python"><br />
>>> a = 2; a = 3<br />
>>> a # a takes on the last value it was bound to<br />
3<br />
</syntaxhighlight><br />
<br />
Assignment statements in the form <code>x = x op y</code> can be shortened to <code>x op= y</code>, where <code>op</code> is an arithmetic operator. Example:<br />
<syntaxhighlight lang="python"><br />
>>> a = 2<br />
>>> a += 1 # equivalent to a = a + 1<br />
>>> a<br />
3<br />
</syntaxhighlight><br />
<br />
=== <code>assert</code> ===<br />
The assert statement is used as a debugging assertion. The syntax is <code>assert expr</code>, where <code>expr</code> is a boolean expression. If <code>expr</code> evaluates to <code>False</code> (i.e., the check fails), an <code>AssertionError</code> is thrown. Otherwise, nothing happens.<br />
<br />
Adding another argument allows you to specify a debugging message when the check fails: <code>assert expr, msg</code>.<br />
Examples:<br />
<syntaxhighlight lang="python"><br />
>>> x = -5<br />
>>> assert x == -5<br />
>>> assert x % 2 == 0, "x is not even"<br />
Traceback (most recent call last):<br />
...<br />
AssertionError: x is not even<br />
>>> assert x > 0<br />
Traceback (most recent call last):<br />
...<br />
AssertionError<br />
</syntaxhighlight><br />
<br />
=== <code>pass</code> ===<br />
<code>pass</code> is a null operation—when it is executed, nothing happens. It is useful as a placeholder when a statement is required syntactically, but no code needs to be executed.<br />
<br />
Examples:<br />
<syntaxhighlight lang="python"><br />
# a class with no methods or attributes<br />
class A:<br />
pass # omitting this would result in an IndentationError<br />
<br />
# complex conditional<br />
if condA and (condB or condC):<br />
pass # do nothing<br />
else:<br />
# ...<br />
</syntaxhighlight><br />
<br />
=== <code>return</code> ===<br />
<code>return expr</code> leaves the current function call with <code>expr</code> as a return value. If <code>expr</code> is omitted or there is no <code>return</code> statement in the function, the return value is <code>None</code>.<br />
<br />
<code>return</code> can occur only in a function definition.<br />
<br />
Example:<br />
<syntaxhighlight lang="python"><br />
>>> def fn():<br />
... return 3<br />
...<br />
>>> fn()<br />
3<br />
</syntaxhighlight><br />
<br />
=== <code>yield</code> ===<br />
{{Main|Generator#yield statement}}<br />
<br />
=== <code>raise</code> ===<br />
{{Main|Exception#Raising an exception}}<br />
<br />
=== <code>break</code> ===<br />
{{Main|Iteration#break statement}}<br />
<br />
=== <code>continue</code> ===<br />
{{Main|Iteration#continue statement}}<br />
<br />
=== <code>import</code> ===<br />
An import statement loads a module into the program. A module is a file containing Python definitions and statements.<br />
<br />
Examples:<br />
<syntaxhighlight lang="python"><br />
>>> from operator import add<br />
>>> add(2, 3)<br />
5<br />
>>> from functools import reduce<br />
>>> reduce(add, [1, 2, 3])<br />
6<br />
</syntaxhighlight><br />
<br />
=== <code>global</code> and <code>nonlocal</code> ===<br />
<code>global var</code> tells Python to modify the binding of <code>var</code> in the global frame if it exists instead of creating a new binding in the current frame. Example:<br />
<syntaxhighlight lang="python"><br />
>>> a = 0<br />
>>> def fn():<br />
... global a<br />
... a += 1<br />
...<br />
>>> a<br />
0<br />
>>> fn()<br />
>>> a<br />
1<br />
</syntaxhighlight><br />
<br />
<code>nonlocal var</code> behaves the same, except for <code>var</code> in a parent (but non-global) frame. Example:<br />
<syntaxhighlight lang="python"><br />
>>> def fn(x):<br />
... def inner():<br />
... nonlocal x<br />
... x += 1<br />
... inner()<br />
... return x<br />
...<br />
>>> fn(1)<br />
2<br />
</syntaxhighlight><br />
When a nonlocal variable is attempted to be rebound without using <code>nonlocal</code>, Python will raise the following exception: <code>UnboundLocalError: local variable referenced before assignment</code>. Example:<br />
<syntaxhighlight lang="python"><br />
>>> def fn(x):<br />
... def inner():<br />
... x += 1<br />
... return inner<br />
... <br />
>>> fn(1)()<br />
Traceback (most recent call last):<br />
...<br />
UnboundLocalError: local variable 'x' referenced before assignment<br />
</syntaxhighlight><br />
<br />
== Compound statements ==<br />
Compound statements contain groups of other statements. Compound statements generally provide ''control flow'' (controlling the execution of the enclosed statements) and span multiple lines.<br />
<br />
A compound statement consists of one or more ''clauses'', which consists of a ''header'' and a ''suite''. The header ends with a colon (:) and controls the suite that follows; the suite is a sequence of statements.<br />
[[File:Compound statement.png|thumb|300px|left|Anatomy of a compound statement]]<br />
{{clear}}<br />
<br />
=== Conditional statements ===<br />
Conditional statements are used to perform different actions depending on some boolean condition. The syntax is:<br />
<syntaxhighlight lang="python"><br />
if condition1:<br />
...<br />
elif condition2:<br />
...<br />
else:<br />
...<br />
</syntaxhighlight><br />
where <code>condition1</code> and <code>condition2</code> are boolean expressions. If <code>condition1</code> evaluates to <code>True</code>, its suite is executed and the rest of the compound statement is skipped. Otherwise, Python checks <code>condition2</code>. If that evaluates to <code>True</code>, the second suite is executed and the rest of the compound statement is skipped. Otherwise, the <code>else</code> suite is executed.<br />
<br />
The <code>elif</code> and <code>else</code> clauses are optional, and there may be more than one <code>elif</code> clause.<br />
<br />
Example:<br />
<syntaxhighlight lang="python"><br />
import datetime<br />
hour = datetime.datetime.now().hour # returns the current hour (24-hour clock)<br />
<br />
if hour < 10:<br />
print("Good morning")<br />
elif hour < 12:<br />
print("Soon time for lunch")<br />
elif hour < 18:<br />
print("Good day")<br />
elif x < 22:<br />
print("Good evening")<br />
else:<br />
print("Good night")<br />
</syntaxhighlight><br />
<br />
A conditional statement can be a one-liner through Python's version of the ''ternary operator''. The syntax is: <code>expression1 if condition else expression2</code>. If <code>condition</code> evaluates to <code>True</code>, <code>expression1</code> is returned, otherwise <code>expression2</code> is returned. Examples:<br />
<syntaxhighlight lang="python"><br />
>>> x = -3<br />
>>> "x is negative" if x < 0 else "x is nonnegative"<br />
'x is negative'<br />
>>> x = 0<br />
>>> "x is negative" if x < 0 else ("x is zero" if x == 0 else "x is positive") # chained<br />
'x is zero'<br />
</syntaxhighlight><br />
<br />
=== <code>while</code> ===<br />
{{Main|Iteration#While loop}}<br />
<br />
=== <code>for</code> ===<br />
{{Main|Iteration#For loop}}<br />
<br />
=== <code>try</code> ===<br />
{{Main|Exception#Handling an exception}}<br />
<br />
=== Function definition ===<br />
The syntax of a [[function]] definition is:<br />
<syntaxhighlight lang="python"><br />
def fn(param1, param2):<br />
...<br />
</syntaxhighlight><br />
where <code>param1</code> and <code>param2</code> are ''formal parameters''. They are the names that the passed in arguments will be bound to.<br />
<br />
If parameters are of the form <code>param = expression</code>, the function is said to have default parameter values. When the corresponding argument is omitted in a function call, the parameter's default value is used. Example:<br />
<syntaxhighlight lang="python"><br />
>>> def fn(a, b=2):<br />
... return a + b<br />
...<br />
>>> fn(1, 1)<br />
2<br />
>>> fn(1) # omitted b<br />
3<br />
</syntaxhighlight><br />
<br />
A function definition is executed in the following way:<br />
* create a function object with [[signature]] <code>name(formal parameters)</code><br />
* set the body of that function to be everything indented after the first line<br />
* bind the function name to the function object in the current frame<br />
<br />
=== Class definition ===<br />
{{Main|Object-oriented programming}}<br />
<br />
== Sources ==<br />
* https://docs.python.org/3/reference/simple_stmts.html<br />
* https://docs.python.org/3/reference/compound_stmts.html<br />
* http://inst.eecs.berkeley.edu/~cs61a/fa13/slides/03-Control_6pp.pdf<br />
* http://www.pythonforbeginners.com/basics/python-if-elif-else-statement<br />
* http://interactivepython.org/runestone/static/thinkcspy/SimplePythonData/simpledata.html#statements-and-expressions<br />
* https://docs.google.com/presentation/d/1FawPUGRd_0nR_bN5Ql3RQ4ziDC8mivXJv4j4V6AVI_U/edit#slide=id.g38bc39fb1_0110</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/RaiseRaise2014-07-24T23:48:14Z<p>Axis: Redirected page to Exception#Raising an exception</p>
<hr />
<div>#REDIRECT [[Exception#Raising an exception]]</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ExceptionException2014-07-24T23:47:44Z<p>Axis: created</p>
<hr />
<div>An '''exception''' is an object that represents an error.<ref>https://docs.google.com/presentation/d/1j_a3kWQwnqyFRo5ud1iJUzVKPK37JkQna9_m9h2u7O0/edit#slide=id.g38ed26997_126</ref> Exceptions are ''raised'' either automatically by Python or explicitly by the programmer.<br />
<br />
This is a full list of exceptions: https://docs.python.org/3/library/exceptions.html#bltin-exceptions.<br />
<br />
== Types ==<br />
There are two different types of exceptions: ones that happen when the program is being parsed by Python (<code>SyntaxError</code>, <code>IndentationError</code>), and ones that happen when the program is running (runtime exceptions).<br />
<br />
== Raising an exception ==<br />
Use the <code>raise</code> statement. Example:<br />
<syntaxhighlight lang="python"><br />
>>> while True:<br />
... num = int(input("Enter a number between 1 and 10:\n"))<br />
... if not 1 <= num <= 10:<br />
... raise ValueError("Number out of range")<br />
... <br />
Enter a number between 1 and 10:<br />
5<br />
Enter a number between 1 and 10:<br />
0<br />
Traceback (most recent call last):<br />
...<br />
ValueError: Number out of range<br />
</syntaxhighlight><br />
<br />
== Handling an exception ==<br />
Runtime exceptions can be caught. We use the <code>try</code>-<code>except</code> construct to handle an exception. If an error is encountered in the <code>try</code> block, execution stops and is transferred to the except block. <br />
<br />
Example:<br />
<syntaxhighlight lang="python"><br />
>>> try:<br />
... print(1/0)<br />
... except ZeroDivisionError:<br />
... print("Can't divide by zero!")<br />
... <br />
Can't divide by zero!<br />
</syntaxhighlight><br />
<br />
There can be multiple <code>except</code> clauses for different types of exceptions. An <code>except</code> clause can also not have an exception specified, in which case it would handle all runtime exceptions. Example:<br />
<syntaxhighlight lang="python"><br />
>>> try:<br />
... lst = None<br />
... lst.append(2)<br />
... except:<br />
... print("Something bad happened!")<br />
... <br />
Something bad happened!<br />
</syntaxhighlight><br />
<br />
== Sources ==<br />
<references></div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Talk:Python_installationTalk:Python installation2014-07-24T23:27:43Z<p>Axis: {{Talk page guidelines}}</p>
<hr />
<div>{{Talk page guidelines}}</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Python_installationPython installation2014-07-24T23:27:34Z<p>Axis: {{Sufficient-class}}</p>
<hr />
<div>{{Sufficient-class}}<br />
{{Workflow sidebar}}<br />
In CS61A, '''Python installation''' involves downloading, installing, and configuring the latest version of [[Python]] 3.x onto one's personal computer so that one can run Python 3.x from a command prompt that is not the built-in IDLE program.<br />
<br />
== Mac OS X ==<br />
Python 2.7 should be built-in to Macs (and accessible with <code>python</code>) but the latest version of Python 3.x, which we use for this class, may not be built-in. You may have to install it separately.<br />
* [http://www.youtube.com/watch?v=smHuBHxJdK8 Keegan Mann's video on installing Python for Mac OS X]<br />
<br />
== Windows ==<br />
* [http://www.youtube.com/watch?v=54-wuFsPi0w Video for installing Python for Windows]<br />
* [https://docs.google.com/document/d/1-GwB7qbN-lVowAer6EP-htfFYcuSPBNxPOnRivHTmBg/edit?usp=sharing How to Python on Windows 7, guide with screenshots by Alana Tran]<br />
The staff will assume that you can invoke Python from the Command Prompt, so please be sure to bind a command such as <code>python3</code>, <code>python</code>, or <code>py</code> to the Python program.<br />
== Completion: Next Steps ==<br />
After Python now works on your computer, you may want to [[Connecting from home|set up the connection]] between your computer and UC Berkeley CS's servers. In addition, navigating your class account in UC Berkeley CS's servers involves knowing [[Basic Unix|basic Unix]].</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Talk:GlookupTalk:Glookup2014-07-24T23:25:29Z<p>Axis: {{Talk page guidelines}}</p>
<hr />
<div>{{Talk page guidelines}}</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/GlookupGlookup2014-07-24T23:25:18Z<p>Axis: fix capitalization</p>
<hr />
<div>{{DISPLAYTITLE:glookup}}<br />
{{Start-class}}<br />
{{Workflow sidebar}}<br />
'''glookup''' is a program that manages student submissions and grades on the EECS Instructional UNIX systems. This program can only be accessed through an instructional class account (e.g. <code>cs61a-xx@cory.eecs.berkeley.edu</code>). It was written by Professor Paul Hilfinger in 1998 <ref>http://inst.eecs.berkeley.edu/pub/glookup.help</ref>.<br />
<br />
<br />
==Submitting assignments==<br />
<ol><br />
<li>[[Basic Unix#Directories|Navigate to the directory]] in which the files to be submitted are located.<br />
<li>Run <code>submit</code> with the name of the assignment, not the name of the files. One can run <code>glookup</code> to look at the list of assignments.<br />
<blockquote style="margin: 0;"><syntaxhighlight lang="bash"><br />
submit hw5<br />
</syntaxhighlight></blockquote><br />
<li>The program will ask for the files required to be submitted. Once the process is complete, one can run <code>glookup -t</code> to view the timestamps for the submissions.<br />
<blockquote style="margin: 0;"><syntaxhighlight lang="bash"><br />
glookup -t hw5<br />
</syntaxhighlight></blockquote><br />
</ol><br />
<br />
==Viewing grades==<br />
===Total grade===<br />
<syntaxhighlight lang="bash"><br />
glookup<br />
</syntaxhighlight><br />
<br />
===Grade for assignment===<br />
<syntaxhighlight lang="bash"><br />
glookup hw2<br />
</syntaxhighlight><br />
<br />
===Statistics===<br />
For statistics about the course total:<br />
<syntaxhighlight lang="bash"><br />
glookup -s Total<br />
</syntaxhighlight><br />
<br />
For statistics about a specific assignment:<br />
<syntaxhighlight lang="bash"><br />
glookup -s assignment<br />
</syntaxhighlight><br />
Add -F to filter out the records that also have a grade for that assignment. This is useful to exclude the class accounts of students that have dropped the course.<br />
<syntaxhighlight lang="bash"><br />
glookup -s proj3 -F midterm1<br />
</syntaxhighlight><br />
Add -b to change the bucket size of the histogram.<br />
<syntaxhighlight lang="bash"><br />
glookup -s midterm2 -b 5<br />
</syntaxhighlight><br />
<br />
==References==<br />
<references></div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/GlookupGlookup2014-07-24T23:24:03Z<p>Axis: /* Statistics */ add</p>
<hr />
<div>{{Start-class}}<br />
{{Workflow sidebar}}<br />
'''glookup''' is a program that manages student submissions and grades on the EECS Instructional UNIX systems. This program can only be accessed through an instructional class account (e.g. cs61a-xx@cory.eecs.berkeley.edu). It was written by Professor Paul Hilfinger in 1998 <ref>http://inst.eecs.berkeley.edu/pub/glookup.help</ref>.<br />
<br />
<br />
==Submitting Assignments==<br />
<ol><br />
<li>[[Basic Unix#Directories|Navigate to the directory]] in which the files to be submitted are located.<br />
<li>Run <code>submit</code> with the name of the assignment, not the name of the files. One can run <code>glookup</code> to look at the list of assignments.<br />
<blockquote style="margin: 0;"><syntaxhighlight lang="bash"><br />
submit hw5<br />
</syntaxhighlight></blockquote><br />
<li>The program will ask for the files required to be submitted. Once the process is complete, one can run <code>glookup -t</code> to view the timestamps for the submissions.<br />
<blockquote style="margin: 0;"><syntaxhighlight lang="bash"><br />
glookup -t hw5<br />
</syntaxhighlight></blockquote><br />
</ol><br />
<br />
==Viewing Grades==<br />
===Total grade===<br />
<syntaxhighlight lang="bash"><br />
glookup<br />
</syntaxhighlight><br />
<br />
===Grade for assignment===<br />
<syntaxhighlight lang="bash"><br />
glookup hw2<br />
</syntaxhighlight><br />
<br />
===Statistics===<br />
For statistics about the course total:<br />
<syntaxhighlight lang="bash"><br />
glookup -s Total<br />
</syntaxhighlight><br />
<br />
For statistics about a specific assignment:<br />
<syntaxhighlight lang="bash"><br />
glookup -s assignment<br />
</syntaxhighlight><br />
Add -F to filter out the records that also have a grade for that assignment. This is useful to exclude the class accounts of students that have dropped the course.<br />
<syntaxhighlight lang="bash"><br />
glookup -s proj3 -F midterm1<br />
</syntaxhighlight><br />
Add -b to change the bucket size of the histogram.<br />
<syntaxhighlight lang="bash"><br />
glookup -s midterm2 -b 5<br />
</syntaxhighlight><br />
<br />
==References==<br />
<references></div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/GlookupGlookup2014-07-24T23:22:52Z<p>Axis: /* Submitting Assignments */ fix formatting</p>
<hr />
<div>{{Start-class}}<br />
{{Workflow sidebar}}<br />
'''glookup''' is a program that manages student submissions and grades on the EECS Instructional UNIX systems. This program can only be accessed through an instructional class account (e.g. cs61a-xx@cory.eecs.berkeley.edu). It was written by Professor Paul Hilfinger in 1998 <ref>http://inst.eecs.berkeley.edu/pub/glookup.help</ref>.<br />
<br />
<br />
==Submitting Assignments==<br />
<ol><br />
<li>[[Basic Unix#Directories|Navigate to the directory]] in which the files to be submitted are located.<br />
<li>Run <code>submit</code> with the name of the assignment, not the name of the files. One can run <code>glookup</code> to look at the list of assignments.<br />
<blockquote style="margin: 0;"><syntaxhighlight lang="bash"><br />
submit hw5<br />
</syntaxhighlight></blockquote><br />
<li>The program will ask for the files required to be submitted. Once the process is complete, one can run <code>glookup -t</code> to view the timestamps for the submissions.<br />
<blockquote style="margin: 0;"><syntaxhighlight lang="bash"><br />
glookup -t hw5<br />
</syntaxhighlight></blockquote><br />
</ol><br />
<br />
==Viewing Grades==<br />
===Total grade===<br />
<syntaxhighlight lang="bash"><br />
glookup<br />
</syntaxhighlight><br />
<br />
===Grade for assignment===<br />
<syntaxhighlight lang="bash"><br />
glookup hw2<br />
</syntaxhighlight><br />
<br />
===Statistics===<br />
<syntaxhighlight lang="bash"><br />
glookup -s assignment<br />
</syntaxhighlight><br />
Add -F to filter out the records that also have a grade for that assignment. This is useful to exclude the class accounts of students that have dropped the course.<br />
<syntaxhighlight lang="bash"><br />
glookup -s proj3 -F midterm1<br />
</syntaxhighlight><br />
Add -b to change the bucket size of the histogram.<br />
<syntaxhighlight lang="bash"><br />
glookup -s midterm2 -b 5<br />
</syntaxhighlight><br />
<br />
==References==<br />
<references></div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/GeneratorGenerator2014-07-24T23:20:14Z<p>Axis: /* Generator expression */ link</p>
<hr />
<div>{{C-class}}<br />
In [[Python]], a '''generator''' is a built-in object that satisfies the [[iterator]] interface. Specialized syntax such as generator expressions and the <code>yield</code> keyword makes generator objects a concise way of creating an iterator. A generator is lazy, producing an item only when asked for it, so it is memory efficient. As such, generators can also represent infinite sequences.<br />
<br />
== <code>yield</code> statement ==<br />
When a function body contains a <code>yield</code> statement, the function will then output a generator object when called. <br />
<syntaxhighlight lang="python"><br />
def double_iter():<br />
curr = 1<br />
while True:<br />
yield curr<br />
curr *= 2<br />
</syntaxhighlight> <br />
Now, each time that <code>__next__</code> is invoked on the generator (e.g. through the <code>next</code> function or a <code>for</code> loop), code from the function will be executed up through the yield statement. The expression next to the yield statement will then be yielded as the result of invoking <code>__next__</code> on the generator object.<br />
<syntaxhighlight lang="python"><br />
>>> a = double_iter()<br />
>>> a<br />
<generator object double_iter at 0x10f14e678><br />
>>> next(a)<br />
1<br />
>>> next(a)<br />
2<br />
>>> next(a)<br />
4<br />
</syntaxhighlight> <br />
<br />
== Generator expression ==<br />
A generator can also be created directly via a ''[[generator expression]]'', which uses the same syntax as a list comprehension but evaluates to a generator object instead of a list.<br />
<syntaxhighlight lang="python"><br />
>>> a = (i*2 for i in range(5))<br />
>>> a<br />
<generator object <genexpr> at 0x109d90558><br />
>>> next(a)<br />
0<br />
>>> next(a)<br />
2<br />
>>> for elem in a:<br />
... print(elem)<br />
4<br />
6<br />
8<br />
</syntaxhighlight></div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Talk:IteratorTalk:Iterator2014-07-24T23:19:38Z<p>Axis: {{Talk page guidelines}}</p>
<hr />
<div>{{Talk page guidelines}}</div>Axishttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/IteratorIterator2014-07-24T23:19:26Z<p>Axis: {{C-class}}</p>
<hr />
<div>{{C-class}}<br />
An '''iterator''' is an object that allows for the traversal of datasets that can be sequentially indexed. Iterators generally use ''lazy computation'' so that its ranges of elements are not necessarily stored in memory but rather obtained from computation when necessary. Iterators also have a ''next'' component to get the next item in the dataset series and have a means to stop iteration if there are no more elements to be computed. Because elements in a series are lazily computed by an iterator, the iterator is a mutable object that only keeps track of its current position as it advances through the series.<br />
<br />
==Python==<br />
In Python, iterators have built-in interfaces that form the ''iterator protocol''. An iterator is an object with both a __next__ method that returns the next sequential value or stops iteration upon ending and a __iter__() method that returns itself (the iterator object is self-iterable).<br />
<br />
==Examples==<br />
<br />
Here is an example of an iterator that iterates over a decreasing series of integers from ''start'' to ''end''. When the ''next()'' method returns its last value and the number it currently tracks is less than ''end'', then it will raise a ''StopIteration'' exception that can then be handled.<br />
<br />
<syntaxhighlight lang="python"><br />
>>> class Countdown:<br />
def __init__(self, start=3, end=0):<br />
self.next_num = start<br />
self.end = end<br />
def __next__(self):<br />
if self.next_num < self.end: raise StopIteration<br />
num = self.next_num<br />
self.next_num -= 1<br />
return num<br />
def __iter__(self):<br />
return self<br />
>>> count_iter = Countdown()<br />
>>> count_iter.__next__()<br />
3<br />
>>> next(count_iter)<br />
2<br />
>>> count_iter.__next__()<br />
1<br />
>>> next(count_iter)<br />
0<br />
>>> count_iter.__next__()<br />
Traceback (most recent call last):<br />
File "<stdin>", line 1, in <module><br />
File "<stdin>", line 6, in __next__<br />
StopIteration<br />
</syntaxhighlight><br />
<br />
This ''FibIter'' class, which uses an iterative algorithm to compute the next number in the Fibonacci sequence, is an example of an iterator that represents an infinite dataset. The ''StopIteration'' exception is never called as there will always be further items. <br />
<br />
<syntaxhighlight lang="python"><br />
>>> class FibIter:<br />
def __init__(self):<br />
self.curr = 0<br />
self.next = 1<br />
def __next__(self):<br />
num = self.curr<br />
self.curr, self.next = self.next, self.curr + self.next<br />
return num<br />
def __iter__(self):<br />
return self<br />
>>> fib_iter = FibIter()<br />
>>> fib_iter.__next__()<br />
0<br />
>>> next(fib_iter)<br />
1<br />
>>> fib_iter.__next__()<br />
1<br />
>>> next(fib_iter)<br />
2<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
* https://docs.python.org/2/library/stdtypes.html</div>Axis