homework #3 solution set

Homework 3 Solution Set

Related documents.

Add this document to collection(s)

You can add this document to your study collection(s)

Add this document to saved

You can add this document to your saved list

Suggest us how to improve StudyLib

(For complaints, use another form )

Input it if you want to receive answer

Please ensure that your password is at least 8 characters and contains each of the following:

• a special character: @$#!%*?&

Homework 3 Solutions hw03.zip

Solution files.

You can find the solutions in hw03.py .

Required Questions

Getting started videos.

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Tree Recursion

Q1: pascal's triangle.

Pascal's triangle gives the coefficients of a binomial expansion; if you expand the expression (a + b) ** n , all coefficients will be found on the n th row of the triangle, and the coefficient of the i th term will be at the i th column.

Here's a part of the Pascal's trangle:

Every number in Pascal's triangle is defined as the sum of the item above it and the item above and to the left of it. Rows and columns are zero-indexed; that is, the first row is row 0 instead of 1 and the first column is column 0 instead of column 1. For example, the item at row 2, column 1 in Pascal's triangle is 2.

Now, define the procedure pascal(row, column) which takes a row and a column, and finds the value of the item at that position in Pascal's triangle. Note that Pascal's triangle is only defined at certain areas; use 0 if the item does not exist. For the purposes of this question, you may also assume that row >= 0 and column >= 0 .

Hint : Pascal's Triangle can be visualized as a grid rather than a geometric, three-sided triangle. With this in mind, how does the position of the value you are trying to find relate to the positions of the two numbers that add up to it? At what coordinates of the "grid" do we find out the value and don't need further calculations? Remember that the positions are 0-indexed!

Here is a visualization of the grid:

Use Ok to test your code:

Sequences and Mutability

Q2: insert items.

Write a function which takes in a list s , a value before , and a value after . It inserts after just after each value equal to before in s . It returns s .

Important: No new lists should be created or returned.

Note: If the values passed into before and after are equal, make sure you're not creating an infinitely long list while iterating through it. If you find that your code is taking more than a few seconds to run, the function may be in an infinite loop of inserting new values.

Data Abstraction

Acknowledgements

This problem is based on one from Structure and Interpretation of Computer Programs Section 2.2.2 .

We are making a planetarium mobile. A mobile is a type of hanging sculpture. A binary mobile consists of two arms. Each arm is a rod of a certain length, from which hangs either a planet or another mobile. For example, the below diagram shows the left and right arms of Mobile A, and what hangs at the ends of each of those arms.

We will represent a binary mobile using the data abstractions below.

• A mobile must have both a left arm and a right arm .
• An arm has a positive length and must have something hanging at the end, either a mobile or planet .
• A planet has a positive mass, and nothing hanging from it.

Below are the various constructors and selectors for the mobile and arm data abstraction. They have already been implemented for you, though the code is not shown here. As with any data abstraction, you should focus on what the function does rather than its specific implementation. You are free to use any of their constructor and selector functions in the Mobiles coding exercises.

Mobile Data Abstraction ( for your reference, no need to do anything here ):

Implement the planet data abstraction by completing the planet constructor and the mass selector. A planet should be represented using a two-element list where the first element is the string 'planet' and the second element is the planet's mass. The mass function should return the mass of the planet object that is passed as a parameter.

The total_mass function demonstrates the use of the mobile, arm, and planet abstractions. It has been implemented for you. You may use the total_mass function in the following questions.

Run the ok tests for total_mass to make sure that your planet and mass functions are implemented correctly.

Q4: Balanced

Implement the balanced function, which returns whether m is a balanced mobile. A mobile is balanced if both of the following conditions are met:

• The torque applied by its left arm is equal to the torque applied by its right arm. The torque of the left arm is the length of the left rod multiplied by the total mass hanging from that rod. Likewise for the right. For example, if the left arm has a length of 5 , and there is a mobile hanging at the end of the left arm of total mass 10 , the torque on the left side of our mobile is 50 .
• Each of the mobiles hanging at the end of its arms is itself balanced .

Planets themselves are balanced, as there is nothing hanging off of them.

Reminder: You may use the total_mass function above. Don't violate abstraction barriers. Instead, use the selector functions that have been defined.

The fact that planets are balanced is important, since we will be solving this recursively like many other tree problems (even though this is not explicitly a tree).

Base case: if we are checking a planet, then we know that this is balanced. Why is this an appropriate base case? There are two possible approaches to this:

• Because we know that our data structures so far are trees, planets are the simplest possible tree since we have chosen to implement them as leaves.
• We also know that from a data abstraction standpoint, planets are the terminal item in a mobile. There can be no further mobile structures under this planet, so it makes sense to stop check here.
• Otherwise: note that it is important to do a recursive call to check if both arms are balanced. However, we also need to do the basic comparison of looking at the total mass of both arms as well as their length. For example if both arms are a planet, trivially, they will both be balanced. However, the torque must be equal in order for the entire mobile to balanced (i.e. it's insufficient to just check if the arms are balanced).

Q5: Finding Berries!

The squirrels on campus need your help! There are a lot of trees on campus and the squirrels would like to know which ones contain berries. Define the function berry_finder , which takes in a tree and returns True if the tree contains a node with the value 'berry' and False otherwise.

Hint : To iterate through each of the branches of a particular tree, you can consider using a for loop to get each branch.

Q6: Maximum Path Sum

Write a function that takes in a tree and returns the maximum sum of the values along any root-to-leaf path in the tree. A root-to-leaf path is a sequence of nodes starting at the root and proceeding to some leaf of the tree. You can assume the tree will have positive numbers for its labels.

Check Your Score Locally

You can locally check your score on each question of this assignment by running

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

Exam Practice

Homework assignments will also contain prior exam-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!

• Fall 2017 MT1 Q4a: Digital
• Summer 2018 MT1 Q5a: Won't You Be My Neighbor?
• Fall 2019 Final Q6b: Palindromes

Just For Fun Questions

The questions below are out of scope for 61A. You can try them if you want an extra challenge, but they're just puzzles that are not required for the course. Almost all students will skip them, and that's fine. We will not be prioritizing support for these questions on Ed or during Office Hours.

Q7: Towers of Hanoi

This problem was covered in lecture, but feel free to use this question to test your understanding and re-implement the problem. -->

• Only one disk may be moved at a time.
• Each move consists of taking the top (smallest) 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.
• No disk may be placed on top of a smaller disk.

Hint: Draw out a few games with various n on a piece of paper and try to find a pattern of disk movements that applies to any n . In your solution, take the recursive leap of faith whenever you need to move any amount of disks less than n from one rod to another. If you need more help, see the following hints.

See the following animation of the Towers of Hanoi, found on Wikimedia by user Trixx .

The strategy used in Towers of Hanoi is to move all but the bottom disc to the second peg, then moving the bottom disc to the third peg, then moving all but the second disc from the second to the third peg.

One thing you don't need to worry about is collecting all the steps. print effectively "collects" all the results in the terminal as long as you make sure that the moves are printed in order.

To solve the Towers of Hanoi problem for n disks, we need to do three steps:

• Move everything but the last disk ( n-1 disks) to someplace in the middle (not the start nor the end rod).
• Move the last disk (a single disk) to the end rod. This must occur after step 1 (we have to move everything above it away first)!
• Move everything but the last disk (the disks from step 1) from the middle on top of the end rod.

We take advantage of the fact that the recursive function move_stack is guaranteed to move n disks from start to end while obeying the rules of Towers of Hanoi. The only thing that remains is to make sure that we have set up the playing board to make that possible.

Since we move a disk to end rod, we run the risk of move_stack doing an improper move (big disk on top of small disk). But since we're moving the biggest disk possible, nothing in the n-1 disks above that is bigger. Therefore, even though we do not explicitly state the Towers of Hanoi constraints, we can still carry out the correct steps.

Q8: Anonymous Factorial

This question demonstrates that it's possible to write recursive functions without assigning them a name in the global frame.

The recursive factorial function can be written as a single expression by using a conditional expression .

However, this implementation relies on the fact (no pun intended) that fact has a name, to which we refer in the body of fact . To write a recursive function, we have always given it a name using a def or assignment statement so that we can refer to the function within its own body. In this question, your job is to define fact recursively without giving it a name!

Write an expression that computes n factorial using only call expressions, conditional expressions, and lambda expressions (no assignment or def statements).

Note: You are not allowed to use make_anonymous_factorial in your return expression.

The sub and mul functions from the operator module are the only built-in functions required to solve this problem.

Homework 3 Solution Set (continued)

• Solve equations and inequalities
• Simplify expressions
• Factor polynomials
• Graph equations and inequalities
• Advanced solvers
• All solvers
• Arithmetics
• Determinant
• Percentages
• Scientific Notation
• Inequalities

What can QuickMath do?

QuickMath will automatically answer the most common problems in algebra, equations and calculus faced by high-school and college students.

• The algebra section allows you to expand, factor or simplify virtually any expression you choose. It also has commands for splitting fractions into partial fractions, combining several fractions into one and cancelling common factors within a fraction.
• The equations section lets you solve an equation or system of equations. You can usually find the exact answer or, if necessary, a numerical answer to almost any accuracy you require.
• The inequalities section lets you solve an inequality or a system of inequalities for a single variable. You can also plot inequalities in two variables.
• The calculus section will carry out differentiation as well as definite and indefinite integration.
• The matrices section contains commands for the arithmetic manipulation of matrices.
• The graphs section contains commands for plotting equations and inequalities.
• The numbers section has a percentages command for explaining the most common types of percentage problems and a section for dealing with scientific notation.

Math Topics

More solvers.

• Add Fractions
• Simplify Fractions

Snapsolve any problem by taking a picture. Try it in the Numerade app?

Automata and Computability undergraduate texts in computer science

Dexter c. kozen, homework 3 - all with video answers.

Chapter Questions

Give regular expressions for each of the following subsets of $\{a, b\}^{*}$. (a) $\{x \mid x$ contains an even number of $a$ 's $\}$ (b) $\{x \mid x$ contains an odd number of $b$ 's $\}$ (c) $\{x \mid x$ contains an even number of $a$ 's or an odd number of $b$ 's $\}$ (d) $\{x \mid x$ contains an even number of $a$ 's and an odd number of $b$ 's $\}$ Try to simplify the expressions as much as possible using the algebraic laws of Lecture 9. Recall that regular expressions over $\{a, b\}$ may use $\epsilon, \emptyset, a, b$, and operators $+,^{*}$, and $\cdot$ only; the other pattern operators are not allowed.

Give deterministic finite automata accepting the sets of strings matching the following regular expressions. (a) $\left(000^{*}+111^{*}\right)^{*}$ (b) $(01+10)(01+10)(01+10)$ (c) $\left(0+1\left(01^{*} 0\right)^{*} 1\right)^{*}$ Try to simplify as much as possible.

For any set of strings $A$, define the set MiddleThirds $A=\{y|\exists x, z| x|=| y|=| z \mid$ and $x y z \in A\}$. For example, MiddleThirds $\{\epsilon, a, a b, b a b, b b a b, a a b b a b\}=\{\epsilon, a, b b\}$. Show that if $A$ is regular, then so is MiddleThirds $A$.

ECE 313, University of Illinois at Urbana-Champaign

ECE 313 Homework, Problem Sets and Solutions

Summer 2013

Homeworks are selected from "Short Answer Questions" in the course notes . The answer of each short answer question is provided at the back of the course notes. You are required to provide detailed solutions. You must drop your homework into the ECE 313 lockbox (#20) in the Everitt Laboratory basement (east side) by this deadline. Late homeworks will not be accepted without prior permission from the instructor. All assignments must be submitted stapled if they consist of more than one sheet.

We have quizzes beside homework. Problem sets are posted with solutions. There will be an in-class quiz each week, almost all quizzes will be selected from problem sets provided in that week on the specified date below.

The following information should be clearly written on the right corner of the first papge of each Homework, or on quiz papers:

• NAME AS IT APPEARS ON COMPASS
• PROBLEM SET #_ or QUIZ #_

Notes on event and probability axioms

Homework 3 – Process Synchronization - Solutions

Cop 4610/cgs5765, introduction to operating systems, fall 2003, florida state university.

¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾ ¾

Points : 100 points

Due : Week 9, Tuesday, October 21, 2003

Special Note: This assignment is due at the beginning of the class. No late submission for this assignment will be accepted as the solution will be made available during the class time.

1.       (15 pnts) Problem 4 in the textbook on pages 322 and 323.

a.        This solution forces the two cooperating processes to alternate visits to the critical section. Thus, there is an implicit timing dependency between the two processes, e.g., if one is much slower than the other, then the fast process will have to synchronize with the slow process on each cycle through the loop. Also, if either stops then the other can also only run through the critical section at most one more time

b.       This algorithm does not solve the problem since it might allow both processes to be in the critical section at the same time. Suppose that the two processes "simultaneously" execute the while -test; they will both pass the test, set their respective flag and enter the critical section. The algorithm is not safe.

c.        This algorithm attempts to resolve the problem described in part (b) by setting the flag before attempting to test the opposite flag. Now, if both processes set their respective flag variables "simultaneously," then the two processes are deadlocked.

2.       (15 pnts) Problem 5 in the textbook on page 323.

Then, if all the buffers were to become empty at one time, the consumer would obtain the mutex semaphore and block on the full semaphore, while holding the mutex semaphore. This is a deadlock situation because the consumer holds all the empty buffers and requests a full one, but the producer cannot create a full buffer without first obtaining an empty buffer. The order of appearance of the P operations is significant.

3.       (20 pnts) Problem 6 in the textbook on page 323.

      Here is a solution:

4.       (15 pnts) Problem 8 in the textbook on pages 323 and 324.

This is Peterson's software solution ( Information Processing Letters , vol. 12, pp. 115-116, 1981) to the critical section problem. The argument for its correctness is paraphrased from the original paper as follows:

First, only one process at a time should be allowed to enter its critical section (mutual exclusion).

For both processes to be in their critical sections, then they would have had to simultaneously set their own flag to TRUE, that is, flag[0] = flag[1] = TRUE. Thus, the two processes are simultaneously attempting to enter their critical section. Also, process 0 (process 1) only enters its critical section after it has set the turn variable to 1 (0) and if flag[1] (flag[0]) is FALSE or turn is 0 (1 in the case of process 1). But only one of the processes could have last set the value of turn, so it is either 0 or 1 at any instant. Suppose turn is 0; then process 1 will pass the while test and continue to evaluate the expression; process 0 will set turn to 1 (if it had not yet executed the statement, which means that process 1 will evaluate the expression FALSE on its next attempt), or it will evaluate the expression FALSE and will enter the critical section. Only one of the processes will be allowed to enter its critical section.

Second, once a process indicates a need to enter into its critical section, it cannot be postponed indefinitely.

A process can only be blocked from entering its critical section at the while loop. Thus, if process 0 is blocked, then it finds flag[1] TRUE and turn set to 1. Process 1 must be in its critical section, otherwise flag[1] would be FALSE. If process 1 is attempting to enter its critical section, then either turn is 0 or 1, thus one or the other is allowed to proceed. If it is 1, then process 1 will enter the critical section (or it is already in its critical section). In either case, process 1 will eventually exit its critical section and set flag[1] to FALSE. Process 0 will then fail the while test and enter the critical section. Notice that if process 1 exits the critical section and then attempts to reenter it it will block itself from competing with process 0 by setting turn to 0.

Third, after a process requests entry into its critical section, a bounded number of other processes may be allowed to enter before the original process enters the critical section. This follows by the same argument used for condition (2).

5.       (20 pnts) Problem 10 in the textbook on pages 324 and 325.

6.       (15 pnts) Problem 3 in the textbook on page 360.