Quiz 0

Quiz 0 will include the material covered in the first two weeks of the semester (from the beginning of semester up to Monday preceding the quiz, inclusive), it will be paper-based, closed-books/closed-notes, and will be given in the beginning of your lab session (so please be on time for the lab). To prepare for the quiz, you should study your own lecture notes, and my lecture notes, and book chapters assigned for homework. For best results, study in groups and test each other on class material.

Please note that in this class the lowest quiz grade is dropped from final computation and no make-up quiz will be given for any reason.

Here’s a list of learning outcomes for the first two weeks; the quiz is constructed based on this list.

The successful CMPS 1500 students are able to:

1.       Describe the main questions studied by computer science and explain why computer science is not equivalent to programming.

2.       Given a formulation of a computational problem, identify the input data and the output (or outcome) required from a solution.

3.       Use the input() function to enter a string value and convert the input into appropriate data type for use in the program.

4.       Use the print() function to display text and values of variables.

5.       Use comments and docstrings in a Python program.

6.       Use decision structures (if-elif-else construct) to make decisions between actions.

7.       Use assignment statement in a program.

8.       Use variables in a program.

9.       Perform operations on numeric types, including division, and integer div and mod.

10.    Evaluate string and list expressions with concatenation (+), indexing and slices, use  len() function. Use the results of those operations in Python program.

11.  Write a short Python program containing all structures mentioned above (e.g. a program to get a number from keyboard and tell the user whether it is an even number).

 12. Manually trace the execution of a given Python program, illustrate the changes in values of the variables after each step (similar to what Pythontutor does with each step), and determine what is printed or accomplished by a Python program.

Discuss accumulation and use a variable as an accumulator variable in a Python program.

Explain the notion of sentinel value and use sentinel values in processing user input.

Write Python programs using for loops.

Write Python programs using while loops.

Define and use definite and indefinite iteration. Identify scenarios in which definite iteration (for loop) and indefinite/conditional (while loop) iteration is preferred.

Write        while True: loops and condition-based while loops, including loops for user input validation.

Use break statement in Python programs.

Write element-based for loops and index-based for loops.

Quiz 1

Quiz 1 will include all material covered, including Monday preceding the quiz. The format and rules will be similar to Quiz 0.

Here’s a list of learning outcomes for the material included in the quiz; the quiz is constructed based on this list.

The successful CMPS 1500 students are able to:

1. Write a Python function for a small problem (i.e. a function to compute factorial of a number).
2. Manually trace the execution of a given Python program and illustrate the changes in values of the variables after each step (similar to what Pythontutor does with each step).
3. Write element-base for loops and index-based for loops; write while loops, including infinite loops with break statements.
4. Manually trace        the execution of a given Python program, illustrate the changes in values  of the variables, and determine what is printed or accomplished by a Python program,  including the programs that contain  loops, function calls (including multiple functions that might call  other functions), file input and output.
5. Write Python programs that read input from file and write output to file.
6. Identify scenarios when Python dictionary type should be used. Write programs that use Python dictionaries.

Take time to review the topics of Quiz 0, as the above material builds on them. For instance, if you know well how indexing works on strings and lists, it is much easier for you to write an iterative program that processes the elements of the string or list one-by-one, using a loop structure.

Pay special attention to writing functions and tracing the steps of function execution. At this point, everyone should be able to solve the following exercise without using computer. If you  have questions about it,  review reading on functions, do the exercises, and resolve your questions before the quiz!

To prepare for the quiz, you should study your own lecture notes, and  my lecture notes, reading chapters,   and Python programs posted on Canvas. For best results, study in groups and test each other on class material.  

Quiz 2

Quiz 2 will include all material covered since Quiz 1, including that of Monday preceding the quiz.  

Review questions:

1. Write a  function to convert from base 10 to base 2.  And base 2 to base 10.
2. Perform binary addition, binary multiplication,  bit-wise AND, NOT, OR,  NOR, and bit-shift operations on paper.
3. Explain how any data can be represented using binary numbers.
4. Write Python code that performs bit-wise AND, NOT, OR,  NOR, and bit-shift operations.
5. Explain the notion of a bit. (And demonstrate familiarity with concept of byte, Kbyte, Mbyte, Gbyte, Tbyte).
6. Apply the rule: n bits can represent 2n distinct values.
7. Construct a truth table for a Boolean function.
8. Perform the minterm expansion for the output of a truth table.
9. Design a circuit for a minterm expansion.
10. Explain how any computable function can be computed using AND, OR, NOT gates only.  
11. Evaluate the circuit consisting of a combination of AND, OR, NOT, NOR gates, given the input signals to the circuit.
12. Construct a 1-bit adder and explain its operation.  Explain how a circuit for adding numbers with several bits can be constructed.
13. Construct a SR latch (1-bit memory) from two NOR gates.
14. Analyze performance of SR-latch under different inputs.
15. Explain how to read to and write from 1-bit memory.
16. Explain the notion of abstraction.
17. Explain the notion of von Neumann architecture, von Neumann bottleneck.
18.  Explain in your own words Moore’s law.  
19. Explain how machine code, assembly code, and high-level program code relate.

Quiz 3

Quiz 3 will include all material on recursion, search, sorting and asymptotic analysis. The tasks for  the quiz:

1. Perform a Big-Oh analysis on Python code containing assignment, math, selection (if, elif, else), repetition (for), functions
2. Explain the purpose and general working of recursion (break down problem into smaller version of itself)
3. Identify base cases and recursive cases
4. Read a recursive function and tell what prints when it runs
5. Explain how binary search and linear search work. Illustrate how each search would work on a given input list.
6. Read and explain code for performing binary search and  linear search.
7. State the asymptotic running time of binary search and linear search. Explain where log n value is coming from.
8. Explain how selection sort and merge sort work, state their running times, discuss their relative performance.

Quiz 4

Quiz 4 will include all OOP and recursion material.  

OOP and Recursion

1. Define the terms object, class, instance.

2. Describe the idea of object-oriented approach and its advantages.

3. Write the constructor ( __init__ method) for a class.

4. Write the __str__ method for a class.

5. Write methods that override standard Python operations. For instance, write “equals” method for a class or use __eq__ to override the == operator. Given a standard name for Python operator (__sub__, __gt__, etc) override that method for the objects of given class. If this question appears, the list of overridable operators will be provided.

6. Describe the purpose of attributes, i.e., instance variables, and methods in a class.

7. Explain the purpose of “self” in a class.

8. Use “self” inside a class for both calling methods and accessing attributes.

9. Given (full or partial) specifications of a class, write a short program that uses the class.

10. Write a Python class to model an everyday object or concept such as a digital clock, rational number.

       11. Read a recursive function and tell what prints when it runs

 12. Write a recursive function for a given task (possible problems: find max in a list recursively, find length of the string recursively, find vowels/numbers in a string or list recursively, raise number to a power, compute a product of numbers from a given range, compute a sum of numbers from a given range).

Quiz 5

Review questions:

Linked structures

1. Implement the a linked list using linked nodes (possibly using or not using head and tail nodes)

2. Draw memory pictures for some code which uses Python List and linked list (boxes with arrows connecting them or the contiguous boxes of an array)

3. Given a sample linked list or Python list, perform list operations  (find/insert/remove an element):  illustrate with drawings how the operations work,  write Python code for them and/or find Big-Oh run time.

4. Argue about strengths and weaknesses of linked list and Python list structures.

BST

1. Explain the concept of binary search tree and how they work.

2. Explain basic properties of a binary tree such as parent, child,  root, leaf, and interior nodes, height of a tree, depth of a node.

3. Explain and perform on a given input tree common tree operations such as pre-, post-, and inorder traversals.

4. Build a binary search tree from a sequence of inputs (BST insertion) - provide illustration on paper and trace provided code.

5. Same for searching a  key in a BST, finding minimum and maximum in a BST.

6. Generate a sorted sequence from a given BST.

7. Provide big-Oh running-time for insertion, search and traversal of BST.

8. Provide a real-life example when data has to be stored in a tree structure. Provide example scenario when binary search tree needs to be used.

Graph

1. Explain the term graph, how graph is represented/stored conceptually, and what Python constructs we can use to represent it.  

2. Compute how many edges can an undirected graph (with one edge per pair of vertices) can have; state the minimum  number of edges in a graph.

3. Explain what it means for a graph to be “connected”, and explain the term “connected component”.

4. Define a shortest path on graph.  

5. How are the problems of network routing  solved using graphs? Provide other real-life scenarios where graphs can be used, and were the two graph problems that we studied - computing the number of connected components and computing the shortest path in graph can be used.

Few more exercises:

• Draw an undirected graph G that has 8 vertices, 10 edges, and 3 connected components.

• If G is an undirected graph with 7 vertices and 3 connected components, what is the largest number of edges it might have?

• How will you represent this graph in Python code? Construct this representation (simliar to lab question)

• Given a dictionary containing graph G, write Python code for inserting a new edge into this graph, given two endpoints of the edge. Same for removing the edge.

Midterm Exam

Midterm exam will include all material covered in the first half of the semester, up to and including class on Mon, Oct.8. Exam is closed-books/closed-notes, no-electronics (including calculators; table of powers of 2 will be provided if necessary),  one hand-written letter-size double-sided helper sheet is allowed (you will be asked to put your name on the helper sheet and submit it with your exam).

Exam topics

Introduction to programming (in Python)

Programming basics

1. Describe the main questions studied by computer science and explain why computer science is not equivalent to programming.

2. Given a formulation of a computational problem, identify the input data and the output (or outcome) required from a solution. Provide an example  real-life application of the solution to this problem.

3. Use the input() function to enter a string value and convert the input into appropriate data type for use in the program.

4. Use the print() function to display text and values of variables.

5. Use comments and docstrings in a Python program.

6. Use decision structures (if-elif-else construct) to make decisions between actions.

7. Use assignment statement in a program.

8. Use variables in a program.

9. Perform operations on numeric types, including integer div and mod.

Sequence data types

1. Evaluate string expressions with concatenation (+), indexes and slices, use  len() function  - with strings and lists. Use the results of those operations in Python program.

2. Use the “in” operation for testing if an element is in a string or list or dictionary.

3. Write Python programs that read input from file and write output to file.

4. Identify scenarios when Python dictionary type should be used.

5. Write programs that use Python dictionaries.

Repetition structures

1. Discuss accumulation and use a variable as an accumulator variable in a Python program.

2. Explain the notion of sentinel value and use sentinel values in processing user input.

3. Write        Python         programs using for loops.

4. Write        Python programs using while loops.

5. Define and use definite and indefinite iteration. Identify scenarios in which definite iteration (for loop) and indefinite/conditional (while loop) iteration is preferred.

6. Write while True: loops and condition-based while loops, including loops for user input validation.

7. Use break statement in Python programs.

8. Write element-based        for loops and index-based for loops.

Functions and general programming skills

1. Write a Python function for a small problem.

2. Write a Python function that calls another Python function.

3. Specify function contract for a given function.

4. Manually trace the execution of a given Python program and illustrate the changes in values  of the variables, including the programs that contain loops and nested loops, function calls, file input and output.

Data representation

1. Explain the use of the ASCII Table for representing characters.

2. Write Python programs using the ord() and chr() functions.

3. Describe in your own words the representations of data for characters, positive integer numbers and images.

4. Convert base 10 numbers to base 2 numbers.  Convert base 2 numbers to base 10 numbers.

5. Write a  function to convert from base 10 to base 2.  And base 2 to base 10.

6. Perform binary addition, binary multiplication,  bit-wise AND, NOT, OR,   NOR, and bit-shift operations.

7. Explain the notion of a bit. (And demonstrate familiarity with concept of byte, Kbyte, Mbyte, Gbyte, Tbyte).

8. Apply the rule: n bits can represent 2n distinct values.

Digital logic

1. Construct a truth table for a Boolean function.

2. Perform the minterm expansion for the output of a truth table.

3. Design a circuit for a minterm expansion.

4. Explain how any computable function can be computed using AND, OR, NOT gates only.  

5. Evaluate the circuit consisting of a combination of AND, OR, NOT, NOR gates, given the input signals to the circuit.

6. Construct a 1-bit adder and explain its operation.  Explain how a circuit for adding numbers with several bits can be constructed.

7. Construct a SR latch (1-bit memory) from two NOR gates.

8. Analyze performance of SR-latch under different inputs.

9. Explain how to read to and write from 1-bit memory.

10. Explain how to add numbers that are longer than one bit.

11. Explain how to store numbers that are longer than 1 bit.

Computer organization

1. Describe the von Neumann Architecture and provide examples of devices that have  von Neumann Architecture.

2. Describe the von Neumann bottleneck.

3. Explain binary representation of executable commands.

4. Explain the notion of  “fetch and execute cycle.”

5. Explain the notion of abstraction and provide examples of abstraction in daily life and specifically in computing.          ·             

Sample problems

Please review the problems in our quizzes, labs and zybook. Many problems on the test will be very similar to the problems in the quizzes, labs, and zybook.

In addition, several sample problems are posted below. Some of them will definitely appear on the exam in un-modified or minimally modified form, hence, the solutions to the Sample Problems won’t be provided before the exam. Every time I shared this preparation guide with the students (including the preceding phrase that sample problems are provided, but solutions to them will not be provided),  I got several emails asking for solutions. So please excuse repetition, but  the solutions to the Sample Problems won’t be provided before the exam. Write and test your programs in IDLE and examine them in Pythontutor. You may find it helpful to work with a group of other people and question them on the material. If you have questions about program operation, bring them to class, TA or instructor office hours.

Introduction to programming (in Python)

Write a Python function fortyTwo() that returns 42. Write a second function main() that asks the user to input a positive integer n and uses a while construct to call the fortyTwo() function n times and print the result of calling fourtyTwo().

Write a Python function compute that has three input parameters: principal, rate, and

numYears that represents the principle of a bank account, the interest rate as a decimal, and the number of years the money is to be left in the bank. The function returns the computed principal after numYears years of compounded annual interest. After one year, the new principal is computed as

principal = principal * (1 + rate)

For example, compute(100, 0.04, 1) returns 104.0. Write a good docstring for the function.

Write Python function getInput that requests an integer input between 1 and 10 inclusive. Force the user to retype if the value is not in the range. Return a valid integer as the function value.

Write a Python function average() with a list of numbers as an input parameter that returns the average of the numbers. Use a for loop in your function to sum the numbers.

Write Python function find(s,ch) that returns the position of a target character in a string s. Return

-1 if not found. You may assume that target is a single character.

Write a Python function countVowels(s) that will count the number of vowels in a string. Your function should accept a string as input, and return the count as the output value. Use a for loop.

Write a Python function stars(n) with input parameter n, a positive integer, that prints n lines of stars with

1 star (asterisk) on first line, two stars on second line, and so forth. For example stars(4) prints

*

**

***

****

Solve this problem using two for-loops, with one loop being nested within the other one. Solve this problem using one for-loop and string multiplication.

What does this function print? Explain why.

def unknown ():

x = 'able '

while len(x) > 0:

print (x)

x = x [1:]

Write a Python function stringStats that prompts for a string. It will then print the number

of letters in the string, the number of vowels, and the percentage of vowels to letters. Here is a sample run.

>>> stringStats()

Enter a string: sequoia tree

Letters: 11

Vowels: 7

Percentage of vowels: 63.63636363

You may use your countVowels function from one of the above problems.

What is printed by the following working Python program? Explain your answer.

def mystery(x):

        print('x is', x)

        if x < 1:

          return 2

        else:

          p = 6 -(x//2 - 1)

       print('p is', p)

          return p

y = mystery(3)

print('y is', y)

What is printed by the following working Python program? Explain your answer.

def dog(x):

        print('in dog, x is',  x)

        y = cat(x-1) + cat(x+2)

        print('in dog, y is', y)

        return y

def cat(y):

        print('in cat, y is', y)

        x = rat(y*2)+3

        print('in cat, x is', x)

        return x

def rat(x):

        print('in rat, x is', x)

        return 2 * x

print('in main')

y = dog(3)

print('in main, y is', y)

The goal of this exercise is to trace how variables change during the execution of code. For each of the code fragments below do the following: Trace the code, and for each time #snapshot is encountered, draw a picture of the current variable values in memory. Remember that the #snapshot comment inside the loops will be encountered multiple times, so you will have to draw the current variable values in memory for each of those encounters.

x=0

i=0

while i<4:

#snapshot

x = x + i*i

i = i+1

print (x)

#snapshot

Another snapshot exercise (remember to illustrate all variables, in this example those are x and i)

        x=1

        lst = list(range(10))

for i in lst:

#snapshot

x = x*2

print (x)

#snapshot

Data representation

1. Convert 117 base 10 to binary, show your work.

2. What is the binary number 101110 in base 10? Show your work.

3. Given two binary numbers 1 1 0 1 and 1 0 1 1 1, perform binary addition, multiplication, bitwise AND, OR, NOR operations on them and write down the result of each operation.

4. If you know a number is stored using 16 bits, what can you say about maximum value of that number?  

Digital logic

1. Write the complete truth table for the Boolean function x~yz+ xy~z

2. Given the following truth table, perform the minterm expansion for the function. Don’t simplify!

1. Design the circuit for the two Boolean functions above.

2. Explain how S input of the memory circuit allows us to store a bit.

Final Exam

Final exam will be cumulative and  include all material covered during semester.  Exam is closed-books/closed-notes, closed-electronics,  one hand-written letter-size cheat sheet is allowed (you will be asked to submit the cheat sheet with your exam).

Exam topics include the material covered in midterm exam plus the following:

Python concepts

1. Perform a Big-Oh analysis on Python code containing assignment, math, selection (if, elif, else), repetition (for), functions

2. Use random numbers in a program and generate randomly chosen elements from a given list of elements.

3. Describe the differences between mutable and immutable data and correctly use mutable and immutable data in the program, including passing mutable and immutable types as function parameters.  

Recursive functions

1. Explain the purpose and general working of recursion (break down problem into smaller version of itself)

2. Identify base cases and recursive cases; identify type of recursion (linear/binary/multiple)

3. Read a recursive function and tell what prints when it runs

4. Write a recursive function for a given task

Object-oriented programming

1. Define the terms object, class, instance.

2. Describe the idea of object-oriented approach and its advantages.

3. Write the constructor ( __init__ method) for a class.

4. Write the __str__ method for a class.

5. Write methods that overload standard Python operations. For instance, write “equals” method for a class or use __eq__ to overload the == operator. Given a standard name for Python operator (__sub__, __gt__, etc) overload that method for the objects of given class. If this question appears, the list of overloadable operators will be provided.

1. Describe the purpose of attributes, i.e., instance variables, and methods in a class.

2. Explain the purpose of “self” in a class.

3. Use “self” inside a class for both calling methods and accessing attributes.

4. Given (full or partial) specifications of a class, write a short program that uses the class.

5. Write a Python class to model an everyday object or concept such as a digital clock, rational number.

Sorting and searching algorithms

1. Explain and illustrate how binary search and linear search work.

2. Write recursive code for performing binary search and iterative code for performing linear search

3. State the asymptotic running time of binary search and linear search. Explain the change in the running time as the size of input increases. For binary search, justify the running time.  

4. Explain and illustrate how selection sort and merge sort work, state their running times, discuss their relative performance. Write, use and analyze code for merge sort and selection sort.

Data structures - lists, trees, graphs

Linked list

1. Implement the a linked list using linked nodes (possibly using or not using head and tail nodes)

2. Draw memory pictures for the code which uses Python List and linked list (boxes with arrows connecting them or the contiguous boxes of an array)

3. Given a sample linked list or Python list, perform list operations  (find/insert/remove an element):  illustrate with drawings how the operations work,  write Python code for them and/or find Big-Oh run time.

4. Argue about strengths and weaknesses of linked list and Python list structures.  

BST

1. Explain the concept of binary search tree and how they work.

2. Explain basic properties of a binary tree such as parent, child,  root, leaf, and interior nodes, height of a tree, depth of a node.

3. Explain and perform on a given input tree common tree operations such as pre-, post-, and inorder traversals.

4. Build a binary search tree from a sequence of inputs (BST insertion) - provide illustration on paper and trace provided code.

5. Same for searching a  key in a BST, finding minimum and maximum in a BST.

6. Generate a sorted sequence from a given BST.

7. Provide big-Oh running-time for insertion, search and traversal of BST.

8. Provide a real-life example when data has to be stored in a tree structure. Provide example scenario when binary search tree needs to be used.

Graph

1. Explain the term graph, how graph is represented/stored conceptually, and what Python constructs we can use to represent it.  Use adjacency list representation of graphs in your code.

2. Compute how many edges can an undirected graph (with one edge per pair of vertices) can have; state the minimum  number of edges in a graph.

3. Explain what it means for a graph to be “connected”, and explain the term “connected component”.

4. Define a shortest path on graph.  

5. Explain how  breadth-first search works and illustrate BFS on an example graph.

6. How are the problems of network routing  solved using graphs? Provide other real-life scenarios where graphs can be used, and were the two graph problems that we studied - computing the number of connected components and computing the shortest path in graph can be used.

Boundaries of computation

1. Explain what it means for a problem to be solvable or not solvable in polynomial time, and what it means for a problem to be verifiable in polynomial time.

2. Discuss what P = NP? question means and why it is an important question for computer science.

3. Provide a formulation of a sample problem from class P and argue why it belongs to P.  

4. Provide a formulation of a sample problem from class NP and argue why it belongs to NP.  

5. Provide a well-defined computational task that is uncomputable.

6. State the halting problem and explain why it is impossible to write a program to solve it.

7. Given a finite state machine (FSM), describe what it does.

8. Design a finite state machine (FSM) for a simple problem.

9. Name several limitations of FSMs.

10. Describe the basic operations of a Turing Machine and describe the difference between Turing Machine and FSM.

Sample problems for Final

Please review the problems in our quizzes. Many problems on the test will be very similar to the problems in the quizzes.  In addition, several sample problems are posted below. Some of them will definitely appear on the exam in un-modified or minimally modified form, hence, the solutions to the Sample Problems won’t be provided before the exam. Write and test your programs in IDLE and examine them in Pythontutor. You may find it helpful to work with a group of other people and question them on the material

1. What does the following code print? Try to answer without executing the code, then check your understanding by running the code in Pythontutor.

a = [1, 2, 3, 4]

b = a

b[2] = 6

print(’a =’, a, ’b =’, b)

2. Using a diagram with boxes and arrows and a couple of sentences, explain the answer printed in problem number 1.

3. What is printed when you invoke prob3()?

 def eat(x):

         x[1] = 9

         x[3] = 11

 def prob3():

         food = [4, 5, 6, 7]

         eat(food)

         print(’food =’, food)

4.    Using a diagram with boxes and arrows and a couple of sentences, explain the answer printed in problem number 3.

5.   Write a function create2DArray with two inputs height and width that creates and returns a 2D array (i.e., a list of lists) with values that are the row number multiplied by the column number. For example,

>>> create2DArray(3, 5)

[[0, 0, 0, 0, 0], [0, 1, 2, 3, 4], [0, 2, 4, 6, 8]]

6.   Write a function addOne with one input anArray which is a 2D array (a list of lists). Your function will add 1 to each element of anArray. For example,  

>>> myArray = create2DArray(3, 5)

>>> addOne(myArray)

>>> print(myArray)

[[1, 1, 1, 1, 1], [1, 2, 3, 4, 5], [1, 3, 5, 7, 9]]

7. Write a Python function that simulates a roll of a pair of six-sided dice and returns a list with the two values.

8. Create a Python class named Phonebook. Add an __init__ method that creates an attribute called phonebook. Initialize phonebook to be a dictionary with the following names and phone numbers: Bob 72345, Sally 7100, John 79999. Make the name the key and the phone number the value. Make the phone number an int.

9. Add a method isNamePresent to your Phonebook class. It will have a name as a parameter. It will return True if the name is present in the phonebook, False otherwise. Here is an example that demonstrates how to use this method.

>>> book = Phonebook()

>>> book.isNamePresent(’Foo’)

False

>>> book.isNamePresent(’Bob’)

True

10.  Write another method for your PhoneBook class called numberFor. It returns the phone number for a name in your phonebook. It will return −1 if the name is not found. Here is an example.  

>>> book.numberFor(’Sally’)

71000

>>> book.numberFor(’foobar’)

-1

Hint: Consider using your isNamePresent method from problem 9.

11.  Create a Python class called Rectangle. The constructor for this class should take two numeric arguments, width and height. Add a method called area that computes and returns the area of the rectangle. Here is an example that shows how to use your class.

>>> myRect = Rectangle(3, 4)

>>> myRect.area()

12

12.  Add a method that will let you print a Rectangle object. For example, the following should work.  

>>> myRect = Rectangle(3, 4)

>>> print(myRect)

width: 3 height: 4

13.  Add a method to your Rectangle class that will allow you to test if two Rectangle objects are equal. Two rectangles are equal if they have the same height and width. For example,  

>>> myRect = Rectangle(3, 4)

>>> otherRect = Rectangle(3, 4)

>>> anotherRect = Rectangle(4, 3)

>>> myRect.equals(otherRect)

True

>>> myRect.equals(anotherRect)

False

14.  Add a method isSquare that determines if the rectangle is a square. For example,    

>>> myRect = Rectangle(3, 3)

>>> otherRect = Rectangle(3, 4)

>>> myRect.isSquare()

True

>>> otherRect.isSquare()

False

15.  Write a function called main that creates three rectangle objects rect1, rect2, and rect3. rect1 is 3 × 4, rect2 is 6 × 6, and rect3 is 3 × 4. It should then print the three objects and their area using the print function. Finally, main should report if rect1 and rect2 are equal and check if rect1 is square. Here is the output you should see when you run main.

>>> main()

rect1: width: 3 height: 4 area = 12

rect2: width: 6 height: 6 area = 36

rect3: width: 3 height: 4 area = 12

rect1 and rect2 are not equal

rect1 is not square

16. Write a function remove(x, s) using recursion that returns a string the same as s, but with no x

characters in it.  Example:

k= remove('t', 'wait a minute')

print(k)

would print 'wai a minue'

17. Write a function join(head1, head2) that takes as input the front nodes of two linked lists, and links those two linked lists together. The second list should be linked to the end of the first list. There should not be any new nodes created. The function should return the front node of the result list.

18. Given a graph stored as adjacency list in a Python dictionary G, write a function

isEdge(G,x,y) that tests whether edge connecting vertices x and y is present in G.

19. Draw a FSM that accepts all binary strings with three ones in a row. 

20. What kind of traversal do you get when you run BFS on the root of a tree?

21. Suppose you want to delete a binary search tree, node by node from the bottom up. What traversal order should you use?

22. Write a function that calculates the “range” of a binary search tree: the value of the largest node in the tree minus the value of the smallest node in the tree.

23. Write a function that prints out, one by one,  every edge in a graph

24. Write a recursive function that takes in a string and returns the same string in reverse order

25. Write a truth table for the NAND gate, or: not(x and y)

26. Name  operations that are faster on a linked list than an array

27. Name  operations that are faster on an array than a linked list

28. Suppose you are trying to create a data structure to represent train routes in the United States. What is wrong with using a tree for this task?

29. Name an algorithm with each of the following runtimes: O(1), O(log n), O(n), O(n2), O(n log n), O(2n)

30. Consider the following class to represent two-dimensional points in space with data consisting of two floats x,y and a method to multiply two points

Use mult to create a new method length() that returns the distance from a point to the origin (sqrt(x_1x_2 + y_1y_2)) E.g. I should be able to write:

p = Point(3,4)

print(p.length())

And have it say 5.0