https://www.ocf.berkeley.edu/~shidi/cs61a/w/api.php?action=feedcontributions&user=Acotra&feedformat=atomCS 61A Wiki - User contributions [en]2022-01-26T08:38:37ZUser contributionsMediaWiki 1.22.6https://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Past_examsPast exams2014-07-16T19:32:13Z<p>Acotra: </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 />
|<br />
|}<br />
<br />
[[Category:Logistical articles]]</div>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Past_examsPast exams2014-07-16T19:30:42Z<p>Acotra: </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 />
|<br />
|}<br />
<br />
[[Category:Logistical articles]]</div>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Summer_2014_Exam_1Summer 2014 Exam 12014-07-10T05:44:07Z<p>Acotra: </p>
<hr />
<div>{{purge}}<br />
<br />
<br />
== Logistics ==<br />
'''2050 VLSB, 7pm Thursday (July 10, 2014)'''<br />
<br />
Bring<br />
* pencil and eraser<br />
* one front and back 8.5x11" cheatsheet<br />
* a copy of [http://ocf.berkeley.edu/~shidi/cs61a/guerrilla/env.txt The Rules]<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 />
<br />
== Topics ==<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 />
* '''[[Higher-order function]]s'''<br />
* '''[[ Recursion ]]'''<br />
* [[Linked list]]s (ignore tuples and OOP); Also known as <code>rlists</code> in other semesters.<br />
* '''[[Recursion#Tree recursion|Tree Recursion]]'''<br />
* '''[[Environment]]s / [[Environment diagram]]s''' (Note that our Env. Diagrams are compatible with Fall 2012 and onward.)<br />
* [[Sequence]]s<br />
* [[Abstract data type]]s<br />
* [[Trees]] (We haven't covered BSTs or Trees in Scheme)<br />
* [[Linked list#Types | Deep lists]]<br />
* [[Orders of growth]]<br />
* [[Newton's method]]<br />
* [[Halting problem]] (Extra Credit)<br />
'''Bolded''' topics are going to have in-depth questions.<br />
<br />
<br />
== Side skills ==<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 />
<br />
== Practice Problems ==<br />
[https://docs.google.com/document/d/1zNMhevz0tuQXJA3xPgzm-VbES5D83Qgb_C7fzJOQJf4/edit?usp=sharing Summer 2014 Exam 1 Warmup Questions]<br />
<br />
[[Practice problems]] (From previous semesters. Easier than exam questions usually.)<br />
<br />
[https://docs.google.com/document/d/1GO2Ic2cK1wgcEv2rtm6eWxBu0pVCmphaCuu0-y1WyEA/edit?usp=sharing Guerrilla #1 - Higher Order Functions]<br />
([https://docs.google.com/document/d/1LidSsQm09e0fenbGOnpjujptGLSl--jA23aOQ5AjR24/edit?usp=sharing Solutions])<br />
<br />
[https://docs.google.com/document/d/1P0CZXh0AQR-5SpQupNk_7tmfzG63sFhKN3BYtZTZjtY/edit?usp=sharing Guerrilla #2 - Recursion]<br />
([https://docs.google.com/document/d/1MljYxhKLWQgh9sq387i1XGXROSJYEwCZIdJ6mWyhbJ8/edit?usp=sharing Solutions])<br />
<br />
('''Guerrilla section go from fundamental questions to midterm level and beyond.''')<br />
<br />
===Problems to Focus on from [[Past exams]]===<br />
<br />
* '''Fall 2011'''<br />
** Midterm 1: <br />
*** 4 (Data Abstraction)<br />
** Midterm 2: <br />
*** 4b (Overlap - string processing and recursion)<br />
* '''Summer 2012'''<br />
** Midterm 1:<br />
*** 1 (Order of evaluation)<br />
*** 2a, 2b (Order of evaluation and lambdas)<br />
*** 3a, 3c (Orders of growth: '''replace O with $\Theta$''')<br />
*** 6 (deep linked_lists and tree recursion: '''replace deep_irlist with a deep linked_list''')<br />
** Final:<br />
*** 2c (Orders of growth and recursion)<br />
* '''Fall 2012'''<br />
** Midterm 1: <br />
*** 1 (Functional calls and What Would Python Do?)<br />
*** 2 (Environment diagrams and lambdas)<br />
** Midterm 2:<br />
*** 4b (Strings and tree recursion)<br />
** Final:<br />
*** 2a (Environment diagram)<br />
* '''Spring 2013'''<br />
** Midterm 1:<br />
*** 2 (Environment diagrams, lambdas)<br />
*** 3 (Higher-order functions)<br />
** Midterm 2:<br />
*** 2b (Environment Diagram)<br />
** Final:<br />
*** 4a (HOF and lambdas)<br />
<br />
* '''Summer 2013'''<br />
** Midterm 1:<br />
*** 1 (Function calls and What Would Python Do?)<br />
*** 2 (Lambda functions)<br />
** Final:<br />
*** 3b (Environment diagram)<br />
* '''Fall 2013'''<br />
** Midterm 1:<br />
*** 1 (Function calls and What Would Python Do?)<br />
*** 2 (Environment diagrams)<br />
*** 3b, 3c (HOF and lambdas)<br />
*** 3d (Strings and iteration)<br />
** Final:<br />
*** 3a, 3c (Tree recursion)<br />
* '''Spring 2014'''<br />
** Midterm 1:<br />
*** 1 (HOF and What Would Python Do?)<br />
*** 2 (Environment Diagram)<br />
*** 3d (Tree recursion)<br />
** Midterm 2:<br />
*** 3 (Data Abstraction)<br />
<br />
== Staff Guides and Websites ==<br />
[http://youri.us/ Guides by Youri]<br />
<br />
[https://docs.google.com/document/d/1-klw_UtTGtR7dwQo1aQOKpPPKtzfSmkhvmNmiTKSiPY/edit?usp=sharing Jessica's Domain/Range guide to cons, car, and cdr on Discussion 3]<br />
<br />
[https://piazza.com/class/hv3d500fcvs4d8?cid=109 Piazza's Useful posts and guides ]<br />
<br />
[[ Guides#Andrew_Huang.27s_tips | Andrew's tips that apply for this midterm ]]<br />
<br />
[https://www.youtube.com/watch?v=ia60GQNKChI Andrew draws an environment diagram] ([https://docs.google.com/document/d/1RPUfcOggSXdEWeYptXgCVwDQF08JNbuOhd9qmDfEPhc/edit?usp=sharing original problem (and solutions)])<br />
<br />
[https://docs.google.com/document/d/1TxfKmM3MlH032hjSUh92I0kQDVcvmitTSzYObGMr8Bk/edit?usp=sharing Orders of Growth and Function Runtime guide]<br />
<br />
[https://docs.google.com/a/berkeley.edu/document/d/1PBf2TknXmDivPV3qbnKRUDvuj-0W6LkMFGDRlWoFu3s/edit Ajeya's Guide to Approaching Recursion Problems]<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>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ExpressionExpression2014-07-09T20:24:53Z<p>Acotra: /* More complicated example */</p>
<hr />
<div>{{C-class}}<br />
An '''expression''' describes a computation and evaluates to a value. {{Basics sidebar}}<br />
== Primitive expressions ==<br />
A primitive expression is a single evaluation step: you either look up the value of a name, or take the literal value. For example, variable names, numbers, and strings are primitive expressions.<br />
<br />
The following are all primitive expressions: <code>1</code>, <code>1.2</code>, <code>'test'</code>, <code>True</code>, <code>x</code>.<br />
<br />
=== Variable lookup ===<br />
A name evaluates to the value bound to that name in the earliest [[frame]] of the current [[environment]] in which that name is found. In other words, to lookup a name in an environment, start looking in the local frame, then in the parent frame (if it exists), until you get to the global frame. Example:<br />
<syntaxhighlight lang="python" highlight=4><br />
x = 1<br />
def outer():<br />
def inner():<br />
return x<br />
return inner<br />
outer()()<br />
</syntaxhighlight><br />
to lookup <code>x</code>, look in the local frame <code>inner</code>. Since it is not there, look in the parent frame <code>outer</code>. Since it is not there, look in the parent frame (the global frame) and find <code>x = 1</code>.<br />
<br />
== Call expressions ==<br />
A call expression is an expression that involves a function call. A call expression invokes a function and evaluates to the function's return value. To evaluate a function call:<br />
* evaluate the operator, then from left to right the operands<br />
* apply the function (the value of the operator) to the arguments (the values of the operands)<br />
In general, the operator is the stuff before the set of matching parentheses, and the operands are the stuff inside the set of matching parentheses.<br />
<br />
=== Simple example ===<br />
<syntaxhighlight lang="python" highlight=2><br />
>>> from operator import add, mul<br />
>>> add(mul(2, 3), 1)<br />
7<br />
</syntaxhighlight><br />
Here is the full list of steps:<br />
# evaluate operator of <code>add(mul(2, 3), 1)</code> and find that it is function <code>add</code><br />
# evaluate operand <code>mul(2, 3)</code><br />
## evaluate operator <code>mul</code> and find that it is function <code>mul</code><br />
## evaluate operand <code>2</code> (primitive)<br />
## evaluate operand <code>3</code> (primitive)<br />
## apply function <code>mul</code> to <code>2</code> and <code>3</code>, returns 6<br />
# evaluate operand <code>1</code> (primitive)<br />
# apply function <code>add</code> to <code>6</code> and <code>1</code>, returns 7<br />
<br />
=== More complicated example ===<br />
<syntaxhighlight lang="python" highlight=3><br />
>>> from operator import add<br />
>>> curry = lambda f: lambda x: lambda y: f(x, y)<br />
>>> curry(add)(1)(2)<br />
3<br />
</syntaxhighlight><br />
Here is the full list of steps:<br />
# evaluate operator <code>curry(add)(1)</code><br />
## evaluate operator <code>curry(add)</code><br />
### evaluate operator <code>curry</code> and find that it is <code>func λ(f)</code><br />
### evaluate operand <code>add</code> and find that it is a function<br />
### apply <code>func λ(f)</code> to <code>add</code>, returns <code>func λ(x)</code><br />
## evaluate operand <code>1</code> (primitive)<br />
## apply <code>func λ(x)</code> to <code>1</code>, returns <code>func λ(y)</code><br />
# evaluate operand <code>2</code> (primitive)<br />
# apply <code>func λ(y)</code> to <code>2</code>, returns 3<br />
<br />
== Sources ==<br />
* http://inst.eecs.berkeley.edu/~cs61a/fa13/disc/discussion01.pdf</div>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Summer_2014_Exam_1Summer 2014 Exam 12014-07-09T07:42:41Z<p>Acotra: /* Practice Problems */</p>
<hr />
<div>== Time and Location ==<br />
'''2050 VLSB, 7pm Thursday (July 10, 2014)'''<br />
<br />
== Topics ==<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 />
* '''[[Higher-order function]]s'''<br />
* '''[[ Recursion ]]'''<br />
* [[Linked list]]s (ignore tuples and OOP); Also known as <code>rlists</code> in other semesters.<br />
* '''[[Recursion#Tree recursion|Tree Recursion]]'''<br />
* '''[[Environment]]s / [[Environment diagram]]s''' (Note that our Env. Diagrams are compatible with Fall 2012 and onward.)<br />
* [[Sequence]]s<br />
* [[Abstract data type]]s<br />
* [[Trees]] (We haven't covered BSTs or Trees in Scheme)<br />
* [[Deep lists]]<br />
* [[Orders of growth]]<br />
* [[Newton's method]]<br />
* [[Halting problem]] (Extra Credit)<br />
'''Bolded''' topics are going to have in-depth questions.<br />
<br />
== Side skills ==<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/1zNMhevz0tuQXJA3xPgzm-VbES5D83Qgb_C7fzJOQJf4/edit?usp=sharing Summer 2014 Exam 1 Warmup Questions]<br />
<br />
[https://docs.google.com/document/d/1GO2Ic2cK1wgcEv2rtm6eWxBu0pVCmphaCuu0-y1WyEA/edit?usp=sharing Guerrilla #1 - Higher Order Functions]<br />
([https://docs.google.com/document/d/1LidSsQm09e0fenbGOnpjujptGLSl--jA23aOQ5AjR24/edit?usp=sharing Solutions])<br />
<br />
[https://docs.google.com/document/d/1P0CZXh0AQR-5SpQupNk_7tmfzG63sFhKN3BYtZTZjtY/edit?usp=sharing Guerrilla #2 - Recursion]<br />
([https://docs.google.com/document/d/1MljYxhKLWQgh9sq387i1XGXROSJYEwCZIdJ6mWyhbJ8/edit?usp=sharing Solutions])<br />
<br />
===Problems to Focus on from [[Past exams]]===<br />
<br />
'''Fall 2011'''<br />
<br />
* Midterm 1: <br />
** 4 (Data Abstraction)<br />
* Midterm 2: <br />
** 4b (Overlap - string processing and recursion)<br />
<br />
'''Summer 2012'''<br />
<br />
* Midterm 1:<br />
** 1 (Order of evaluation)<br />
** 2a, 2b (Order of evaluation and lambdas)<br />
** 3a, 3c (Orders of growth: '''replace O with $\Theta$''')<br />
** 6 (deep linked_lists and tree recursion: '''replace deep_irlist with a deep linked_list''')<br />
* Final:<br />
** 2c (Orders of growth and recursion)<br />
<br />
'''Fall 2012'''<br />
<br />
* Midterm 1: <br />
** 1 (Functional calls and What Would Python Do?)<br />
** 2 (Environment diagrams and lambdas)<br />
* Midterm 2:<br />
** 4b (Strings and tree recursion)<br />
* Final:<br />
** 2a (Environment diagram)<br />
<br />
'''Spring 2013'''<br />
<br />
* Midterm 1:<br />
** 2 (Environment diagrams, lambdas)<br />
** 3 (Higher-order functions)<br />
* Midterm 2:<br />
** 2b (Environment Diagram)<br />
* Final:<br />
** 4a (HOF and lambdas)<br />
<br />
<br />
'''Summer 2013'''<br />
<br />
* Midterm 1:<br />
** 1 (Function calls and What Would Python Do?)<br />
** 2 (Lambda functions)<br />
* Midterm 2:<br />
** 4 (Environment diagrams)<br />
** 6 (Recursion and helper functions)<br />
* Final:<br />
** 3b (Environment diagram)<br />
<br />
'''Fall 2013'''<br />
<br />
* Midterm 1:<br />
** 1 (Function calls and What Would Python Do?)<br />
** 2 (Environment diagrams)<br />
** 3b, 3c (HOF and lambdas)<br />
** 3d (Strings and iteration)<br />
* Final:<br />
** 3a, 3c (Tree recursion)<br />
<br />
'''Spring 2014'''<br />
<br />
* Midterm 1:<br />
** 1 (HOF and What Would Python Do?)<br />
** 2 (Environment Diagram)<br />
** 3d (Tree recursion)<br />
* Midterm 2:<br />
** 3 (Data Abstraction)<br />
<br />
== Staff Guides and Websites ==<br />
[http://youri.us/ Guides by Youri]<br />
<br />
[https://docs.google.com/document/d/1-klw_UtTGtR7dwQo1aQOKpPPKtzfSmkhvmNmiTKSiPY/edit?usp=sharing Jessica's Domain/Range guide to cons, car, and cdr on Discussion 3]<br />
<br />
[https://piazza.com/class/hv3d500fcvs4d8?cid=109 Piazza's Useful posts and guides ]<br />
<br />
[[ Guides#Andrew_Huang.27s_tips | Andrew's tips that apply for this midterm ]]<br />
<br />
[https://www.youtube.com/watch?v=ia60GQNKChI Andrew draws an environment diagram] ([https://docs.google.com/document/d/1RPUfcOggSXdEWeYptXgCVwDQF08JNbuOhd9qmDfEPhc/edit?usp=sharing original problem (and solutions)])<br />
<br />
[https://docs.google.com/document/d/1TxfKmM3MlH032hjSUh92I0kQDVcvmitTSzYObGMr8Bk/edit?usp=sharing Orders of Growth and Function Runtime guide]<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 />
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>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Towers_of_HanoiTowers of Hanoi2014-07-06T04:48:51Z<p>Acotra: </p>
<hr />
<div>{{Purge}}<br />
<br />
'''Tower of Hanoi''' is a puzzle that involves three pegs and <code>n</code> disks. The each disk is of a unique size, with smaller disks always going on top of larger disks on a peg. At the beginning of the puzzle, all the disks are stacked on one starting peg from smallest (on the top) to the largest (on the bottom). The goal is to make the necessary valid moves to move the disks from the <code>start</code> peg to the desired <code>end</code> peg.<br />
<br />
Valid moves are such that<br />
* Only one disk may be moved at a time.<br />
* Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.<br />
* No disk may be placed on top of a smaller disk.<br />
<br />
<br />
== Problem ==<br />
The problem can be stated as such:<br />
<blockquote>Complete the definition of <code>towers_of_hanoi</code> which prints out the steps to solve this puzzle for any number of <code>n</code> disks starting from the <code>start</code> rod and moving them to the <code>end</code> rod:<br />
<source lang="python"><br />
def towers_of_hanoi(n, start, end):<br />
"""Print the moves required to solve the towers of hanoi game if we start<br />
with n disks on the start pole and want to move them all to the end pole.<br />
<br />
The game is to assumed to have 3 poles (which is traditional).<br />
<br />
>>> towers_of_hanoi(1, 1, 3)<br />
Move 1 disk from rod 1 to rod 3<br />
>>> towers_of_hanoi(2, 1, 3)<br />
Move 1 disk from rod 1 to rod 2<br />
Move 1 disk from rod 1 to rod 3<br />
Move 1 disk from rod 2 to rod 3<br />
>>> towers_of_hanoi(3, 1, 3)<br />
Move 1 disk from rod 1 to rod 3<br />
Move 1 disk from rod 1 to rod 2<br />
Move 1 disk from rod 3 to rod 2<br />
Move 1 disk from rod 1 to rod 3<br />
Move 1 disk from rod 2 to rod 1<br />
Move 1 disk from rod 2 to rod 3<br />
Move 1 disk from rod 1 to rod 3<br />
"""<br />
"*** YOUR CODE HERE ***"<br />
<br />
<br />
def move_disk(start, end):<br />
print("Move 1 disk from rod", start, "to rod", end)<br />
</source></blockquote><br />
<br />
== Approach ==<br />
=== Overview ===<br />
When we approach a problem recursively, we need to try and break it down into a smaller version of the same problem. Just like a recursive <code>factorial</code> function utilizes the fact that $n!=n\cdot(n-1)!$ to make recursive calls, our approaches to other recursive problems should do something similar. We need a recursive definition, which tells Python how to recurse through this problem, and a base case, which tells Python where to stop recursing.<br />
<br />
=== Base Case ===<br />
So let's start with the base case. The base case should be a case where we do not need to make recursive calls to know what the answer is (<math>1!=1</math>, for <code>factorial</code>). In <code>towers_of_hanoi</code>, what is the easiest base case to solve? What should the function do in that case?<br />
<br />
=== Recursive Case ===<br />
Now what about the recursive case? Trying to figure out the algorithm to correctly move each disk is a bit difficult, so let's only deal with the nth disk, or the bottom-most one, and somehow have recursion deal with the other <code>n - 1</code> disks. Here, we have the start of the problem:<br />
<br />
[[File:hanoi0.png]]<br />
<br />
To move all the disks from start to end we need to eventually move disk n. But since we can only move the top-most disk of any tower, we have to first move all the <code>n - 1</code> disks to the offset, so that later we can <br />
move disk <code>n</code> to the <code>end</code>:<br />
<br />
[[File:hanoi1.png]]<br />
<br />
At this point, disk <code>n</code> is free to move, so we can place it at the end:<br />
<br />
[[File:hanoi2.png]]<br />
<br />
And then, we just need to move the <code>n - 1</code> disks to the end as well:<br />
<br />
[[File:hanoi3.png]]<br />
<br />
At this point, the only thing that we may be unsure of is how to move the <code>n - 1</code> disks from the start to the offset. But note exactly what <code>towers_of_hanoi</code> does. The function <code>towers_of_hanoi</code> prints the procedure of how to move <code>n</code> disks from <code>start</code> to the <code>end</code>.<br />
<br />
And already, we've come across a smaller version of this problem! We need to move the n - 1 disks from start to the offset, which in itself is a towers_of_hanoi problem, only with a different destination, and one less disk. We encounter the problem again when after we move the nth disk, we need to move the n - 1 disks again to the end as well.<br />
<br />
=== The Trick ===<br />
Of course, we're not done defining towers_of_hanoi yet, but we know what the goal of it is anyways. Once we're finished, it should work as we had intended it to, so let's take a recursive leap of faith, and go ahead and make recursive calls to <code>towers_of_hanoi</code>to move the <code>n - 1</code> disks out of our way. The only thing that may be tricky is to figure out which peg is the "offset" peg. Consider the following:<br />
{|<br />
|-<br />
! start !! end !! offset<br />
|-<br />
| 1 || 3 || 2<br />
|-<br />
| 3 || 1 || 2<br />
|-<br />
| 1 || 2 || 3<br />
|-<br />
| 2 || 1 || 3<br />
|-<br />
| 2 || 3 || 1<br />
|-<br />
| 3 || 2 || 1<br />
|-<br />
|}<br />
<br />
After a lot of thought, one might come up with <code>offset = 6 - start - end</code>. This is just an expression that matches the table above, so don't worry if you didn't come up with this.</div>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/CS61A_Wiki:Front_page_linksCS61A Wiki:Front page links2014-06-30T07:01:45Z<p>Acotra: </p>
<hr />
<div>{| width="100%" border="0" cellspacing="20" cellpadding="5" <br />
| valign="top" rowspan="2" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #0099ff; width:50%; height:50%; border-left: 40px solid #0099ff;" | &nbsp;'''Topics'''<br />
*Abstraction: [[Abstraction]] · [[Data abstraction]]<br />
*Core articles: [[Expression]] · [[Statement]] · [[Function]] · [[Environment]]<br />
*Techniques: [[Iteration]] · [[Recursion]]<br />
*Structures: [[Dictionary]] · [[Sequence]] · [[Set]]<br />
| valign="top" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #eebb66; width:50%; height:50%; border-left: 40px solid #eebb66;" | &nbsp;'''Articles of the week'''<br />
*[[Environment diagram]] · [[Lambda function]] · [[Currying]] · [[Dispatch function]]<br />
|- <br />
| valign="top" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #ff7777; width:50%; height:50%; border-left: 40px solid #ff7777;" | &nbsp;'''Resources'''<br />
*[[Guides]] · [[Practice problems]] · [http://pythontutor.com/composingprograms.html#mode=edit Python Tutor]<br />
|-<br />
| valign="top" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #66cc66; width:50%; height:50%; border-left: 40px solid #66cc66;" | &nbsp;'''Getting Started'''<br />
*[[Basic Unix]] · [[Python]]<br />
| valign="top" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #ccaadd; width:50%; height:50%; border-left: 40px solid #ccaadd;" | &nbsp;'''Help The Wiki'''<br />
*[[CS61A Wiki:How-to guide|How-to guide]] · [[CS61A Wiki:Community guidelines|Community guidelines]] · [[CS61A Wiki:Requested articles|Requested articles]] · [[CS61A Wiki:Sandbox|Sandbox]] · [[CS 61A Wiki:Article rating system|Article rating system]]<br />
|-<br />
| valign="top" colspan=2 style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #0b5394; width:50%; height:50%; border-left: 40px solid #0b5394;" | &nbsp;'''Summer 2014 Specific Resources'''<br />
*Course sites: [http://cs61a.org Course Page] · [http://chat.cs61a.org IRC Chat] · <br />
*Asking Questions: [http://docs.google.com/a/berkeley.edu/document/d/1R4LeFokAcKTDnxF2xZPf9tnZ--PZOHxr791Fq-wG2wg/edit How to Get Help]<br />
*Guides: [http://docs.google.com/document/d/1Yw6wK6PPL7x7wJB6Wo9qkWz8rgJwo-t0cXU5pFstaVA/edit Quick Guide on Getting Unstuck] · [http://www-inst.eecs.berkeley.edu/~cs61a/su14/debugging.html Debugging Guide] · [http://inst.eecs.berkeley.edu/~cs61a/su14/composition.html Composition Guidelines]<br />
|}<br />
<!-- Adding a plain link (not part of this wiki) here:<br />
<span class="plainlinks">[google.com Suggestions]</span><br />
--></div>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/CS61A_Wiki:Front_page_linksCS61A Wiki:Front page links2014-06-30T04:28:09Z<p>Acotra: </p>
<hr />
<div>{| width="100%" border="0" cellspacing="20" cellpadding="5" <br />
| valign="top" rowspan="2" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #0099ff; width:50%; height:50%; border-left: 40px solid #0099ff;" | &nbsp;'''Topics'''<br />
*Abstraction: [[Abstraction]] · [[Data abstraction]]<br />
*Core articles: [[Expression]] · [[Statement]] · [[Function]] · [[Environment]]<br />
*Techniques: [[Iteration]] · [[Recursion]]<br />
*Structures: [[Dictionary]] · [[Sequence]] · [[Set]]<br />
| valign="top" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #eebb66; width:50%; height:50%; border-left: 40px solid #eebb66;" | &nbsp;'''Articles of the week'''<br />
*[[Environment diagram]] · [[Lambda function]] · [[Currying]] · [[Dispatch function]]<br />
|- <br />
| valign="top" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #ff7777; width:50%; height:50%; border-left: 40px solid #ff7777;" | &nbsp;'''Resources'''<br />
*[[Guides]] · [[Practice problems]]<br />
|-<br />
| valign="top" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #66cc66; width:50%; height:50%; border-left: 40px solid #66cc66;" | &nbsp;'''Getting Started'''<br />
*[[Basic Unix]] · [[Python]]<br />
| valign="top" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #ccaadd; width:50%; height:50%; border-left: 40px solid #ccaadd;" | &nbsp;'''Help The Wiki'''<br />
*[[CS61A Wiki:How-to guide|How-to guide]] · [[CS61A Wiki:Community guidelines|Community guidelines]] · [[CS61A Wiki:Requested articles|Requested articles]] · [[CS61A Wiki:Sandbox|Sandbox]] · [[CS 61A Wiki:Article rating system|Article rating system]]<br />
|-<br />
| valign="top" colspan=2 style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: small; padding:5px; background-color:#fcfcfc; border:2px solid #0b5394; width:50%; height:50%; border-left: 40px solid #0b5394;" | &nbsp;'''Summer 2014 Specific Resources'''<br />
*Course sites: [http://cs61a.org Course Page] · [http://chat.cs61a.org IRC Chat] · <br />
*Asking Questions: [http://docs.google.com/a/berkeley.edu/document/d/1R4LeFokAcKTDnxF2xZPf9tnZ--PZOHxr791Fq-wG2wg/edit How to Get Help]<br />
*Guides: [http://docs.google.com/document/d/1Yw6wK6PPL7x7wJB6Wo9qkWz8rgJwo-t0cXU5pFstaVA/edit Quick Guide on Getting Unstuck] · [http://www-inst.eecs.berkeley.edu/~cs61a/su14/debugging.html Debugging Guide] · [http://inst.eecs.berkeley.edu/~cs61a/su14/composition.html Composition Guidelines]<br />
|}<br />
<!-- Adding a plain link (not part of this wiki) here:<br />
<span class="plainlinks">[google.com Suggestions]</span><br />
--></div>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/RecursionRecursion2014-06-05T00:19:50Z<p>Acotra: </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 />
==Simple recursion==<br />
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 />
<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 />
<br />
A [[Function | 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.<br />
<br />
===Analogy===<br />
<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 />
<br />
Consider this Python code for generating the nth Fibonacci number:<br />
<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 />
<br />
The call tree for the <code>fib</code> function would look 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 />
<br />
==Mutual recursion==<br />
<br />
==Tail recursion==</div>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/RecursionRecursion2014-06-04T23:23:52Z<p>Acotra: /* Tree recursion */ I would really appreciate if someone could add a nice picture of the recursion tree! Thanks :)</p>
<hr />
<div>{{C-class}}<br />
'''Recursion''' is a technique for solving large computational problems by reducing them to successively smaller problems and repeatedly applying the same procedure(s). 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 />
==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 />
==Simple recursion==<br />
Simple recursion is a procedure much like the example given in the analogy — there is usually only one base case, and the recursive procedure calls itself only once in every function call. 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 />
<br />
A [[Function | function]] is ''tree recursive'' if the recursive step contains more than one call to the same function. For example, consider the function for generating Fibonacci numbers:<br />
<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 />
<br />
Let's consider how this algorithm would compute the 4th Fibonacci number. In order to compute <code>fib(4)</code>, we need to compute <code>fib(2)</code> and <code>fib(3)</code>. In order to compute <code>fib(2)</code>, we need to compute <code>fib(0)</code> and <code>fib(1)</code>. In order to compute <code>fib(3)</code>. we need to compute <code>fib(1)</code> and <code>fib(2)</code>. In order to compute <code>fib(2)</code> ''again'', we need to compute <code>fib(0)</code> and <code>fib(1)</code> again. Each frame creates two more until the base cases are reached, creating a call structure that looks like a tree, with every "root" having two "branches".<br />
<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 for your paternal grandparents). This is a tree recursive procedure whose call tree mirrors the family tree.<br />
<br />
==Mutual recursion==<br />
<br />
==Tail recursion==</div>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/RecursionRecursion2014-06-03T04:12:35Z<p>Acotra: Created page with "''Recursion'' is a technique for solving large computational problems by reducing them to successively smaller problems by repeatedly applying the same procedure(s). A recursi..."</p>
<hr />
<div>''Recursion'' is a technique for solving large computational problems by reducing them to successively smaller problems by repeatedly applying the same procedure(s). A recursive procedure has two parts, one or more ''base cases'' and a ''recursive step''. Base cases are pre-determined solutions for the simplest possible 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 />
==Analogy==<br />
<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 Diagrams | environment diagrams]]. 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 />
==Simple Recursion==<br />
<br />
Simple recursion is a procedure much like the example given in the analogy - there is usually only one base case, and the recursive procedure calls itself only once in every function call. 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 only called 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 />
<syntaxthighlight lang="python"><br />
def pow(b, p):<br />
if p == 0:<br />
return 1<br />
else if 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 each <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 />
<br />
==Mutual Recursion==<br />
<br />
==Tail Recursion==</div>Acotrahttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/SequenceSequence2014-06-02T22:52:06Z<p>Acotra: Created page with "A ''sequence'' is any object or data structure which stores and accesses elements in a ''fixed order''. Built-in sequence types include <code>list</code>, <code>tuple</code>, ..."</p>
<hr />
<div>A ''sequence'' is any object or data structure which stores and accesses elements in a ''fixed order''. Built-in sequence types include <code>list</code>, <code>tuple</code>, <code>string</code>, and <code>range</code>. By contrast, [[Sets | sets]] and [[Dictionaries | dictionaries]], while they share some common features with sequences, are ''not'' themselves sequences. Sequences always support [[Iteration | iteration]] (though not all iterable types are necessarily sequences) and a set of other basic operations.<br />
<br />
== Sequence Types ==<br />
<br />
A <code>string</code> is a sequence whose elements are ''characters'' (letters, symbols, or spaces) enclosed in quotation marks. <br />
<br />
A <code>tuple</code> is a sequence which stores elements of any type. Tuples are constructed by listing elements separated by commas, or by calling <code>tuple(s)</code> for some sequence <code>s</code>.<br />
<br />
A <code>list</code> also stores elements of any type. Lists behave much like tuples, except lists are mutable (see below). Lists are constructed by enclosing elements in square brackets and separating them by commas, or by calling <code>list(s)</code> for some sequence <code>s</code>. <br />
<br />
== Sequence Operations ==<br />
<br />
The number of elements in a sequence <code>s</code> is given by <code>len(s)</code>. <br />
<br />
Elements in a sequence are organized by ''index'', an integer denoting where that element is located in the ordering. The first element is at index 0, the second and index 1, and so on. This convention is called ''zero-based indexing''. Note that Python also allows ''negative'' indices for convenience. The last element is at -1, the second to last at -2, and so on.<br />
<br />
A particular element <code>x</code> in a sequence <code>s</code> can be retrieved with <code">s[i]</code>, where <code>i</code> is the index of <code>x</code>. Note that this returns, but does not remove, the element <code>x</code>. Negative indices are permissible.<br />
<br />
Indices are also used to return a ''slice'' of the sequence. For a sequence <code>s</code>, create a slice with the format <code>s[start:end:step]</code>. This will return a subsequence which begins with the element at index <code>start</code>, ends with the element at index <code>end - 1</code>, counting indices by <code>step</code>. If not specified <code>start</code> defaults to 0, <code>end</code> defaults to <code>len(s)</code>, and <code>step</code> defaults to 1. Negative indices and steps (indicating counting indices backwards) are permissible. For example,<br />
<br />
<syntaxhighlight lang="python"><br />
>>> s = "abababab"<br />
>>> s[:-2:2]<br />
"aaa"<br />
</syntaxhighlight><br />
<br />
Two sequences of the same type can be ''concatenated'' together with the addition operator, which returns a new sequence containing all the elements in the first sequence followed by all the elements in the second. For example, <code>(1, 2) + (3, 4)</code> returns <code>(1, 2, 3, 4)</code>. <br />
<br />
== Mutable Sequences ==<br />
<br />
The only built-in [[Mutable Types | mutable]] sequence type in Python is the <code>list</code>. In addition to the common sequence operations, lists can support internal modification. For example, <br />
<br />
<syntaxhighlight lang="python"><br />
>>> lst = [1, 2, 3]<br />
>>> lst[0] = 5<br />
>>> lst<br />
[5, 2, 3]<br />
</syntaxhighlight><br />
<br />
This piece of code creates <code>lst</code> and replaces its first element. As opposed to concatenation and slicing, which leave the original unchanged and create new sequence objects with the specified modification, this changes the original list object itself.<br />
<br />
Other operations which change the list object include <code>append</code>, which takes in one argument and inserts that at the end of the list,<br />
<br />
<syntaxhighlight lang="python"><br />
>>> lst.append(5)<br />
>>> lst<br />
[5, 2, 3, 5]<br />
</syntaxhighlight><br />
<br />
<code>remove</code>, which takes in one argument and removes the first instance of it from the list,<br />
<br />
<syntaxhighlight lang="python"><br />
>>> lst.remove(5)<br />
>>> lst<br />
[2, 3, 5]<br />
</syntaxhighlight><br />
<br />
and <code>pop</code>, which removes and returns the last element if it is not passed any additional arguments, or removes the element at index <code>i</code> for integer <code>i</code><br />
<br />
<syntaxhighlight lang="python"><br />
>>> lst.pop()<br />
5<br />
>>> lst<br />
[2, 3]<br />
>>> lst.pop(0)<br />
2<br />
>>> lst<br />
[3]<br />
</syntaxhighlight><br />
<br />
Other built-in methods which rely upon mutability include <code>sort</code> which sorts the given list object ''in-place'' (without having to return a copy), and <code>reverse</code>, which reverses a list object in-place.</div>Acotra