mikeizbicki / cmc-csci046 Goto Github PK

I currently pass all tests in test_AVLTree.py, including the insert_list test, except for the test__AVLTree_insert FAILED and test__AVLTree_inorder_property FAILED which give the following error:

_____________________________ test__AVLTree_insert _____________________________
    @given(xs=ints)
>   def test__AVLTree_insert(xs):
tests/test_AVLTree.py:193: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
xs = [0, 1, 2]
    @given(xs=ints)
    def test__AVLTree_insert(xs):
        xs = list(set(xs))
        avl = AVLTree()
        for x in xs:
            avl.insert(x)
>           assert x in avl.to_list('inorder')
E           AssertionError: assert 2 in [0]
E            +  where [0] = <bound method BinaryTree.to_list of AVLTree([0])>('inorder')
E            +    where <bound method BinaryTree.to_list of AVLTree([0])> = AVLTree([0]).to_list
tests/test_AVLTree.py:198: AssertionError
---------------------------------- Hypothesis ----------------------------------
Falsifying example: test__AVLTree_insert(
    xs=[0, 1, 2],
)
________________________ test__AVLTree_inorder_property ________________________
    @given(xs=ints)
>   def test__AVLTree_inorder_property(xs):
        '''
        The order we insert objects into a AVLTree can affect the structure of the tree,
        but it should NOT affect the list we get out from an inorder traversal.
        (Recall that the inorder traversal of a AVLTree should always be a sorted list.)
        This test randomly shuffles the input list two different ways
        and checks that both shufflings give the same output list.
        This tests both the insertion functions and the traversal functions
        to ensure that there are no bad interactions between theses functions.
tests/test_AVLTree.py:279: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
xs = [0, 1, -1]
    @given(xs=ints)
    def test__AVLTree_inorder_property(xs):
        '''
        The order we insert objects into a AVLTree can affect the structure of the tree,
        but it should NOT affect the list we get out from an inorder traversal.
        (Recall that the inorder traversal of a AVLTree should always be a sorted list.)
        This test randomly shuffles the input list two different ways
        and checks that both shufflings give the same output list.
        This tests both the insertion functions and the traversal functions
        to ensure that there are no bad interactions between theses functions.
        '''
        xs = list(set(xs))
        random.seed(0)
    
        xs1 = copy.copy(xs)
        random.shuffle(xs1)
        bst1 = AVLTree(xs1)
    
        xs2 = copy.copy(xs)
        random.shuffle(xs2)
        bst2 = AVLTree(xs2)
    
>       assert bst1.to_list('inorder') == bst2.to_list('inorder')
E       assert [-1, 0, 1] == [-1]
E         Left contains 2 more items, first extra item: 0
E         Full diff:
E         - [-1, 0, 1]
E         + [-1]
tests/test_AVLTree.py:300: AssertionError
---------------------------------- Hypothesis ----------------------------------
Falsifying example: test__AVLTree_inorder_property(
    xs=[0, 1, -1],
)

It seems like my insert code must be wrong, but the insert_list function I have somehow works? Even though it uses the insert code.

Here are my insert functions:

def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            AVLTree._insert(value, self.root)

    @staticmethod
    def _insert(value,node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                AVLTree._insert(value, node.left)
        elif value > node.value:
            if node.right is None:
                node.right = Node(value)
            else:
                AVLTree._insert(value,node.right)
        if AVLTree._is_avl_satisfied(node)==False:
            return AVLTree.rebalance(node)

    def insert_list(self, xs):
        for item in xs:
            self.insert(item)

    @staticmethod
    def rebalance(node):
        while AVLTree._balance_factor(node)<-1 or AVLTree._balance_factor(node) > 1:
            if AVLTree._balance_factor(node)> 1:
                if AVLTree._balance_factor(node.left) < 0:
                    node.left = AVLTree._left_rotate(node.left)
                return AVLTree._right_rotate(node)
            elif AVLTree._balance_factor(node)<-1:
                if AVLTree._balance_factor(node.right)>0:
                    node.right = AVLTree._right_rotate(node.right)
                return AVLTree._left_rotate(node)
            else:
                return node

Any help would be greatly appreciated.

Hi, I'm a bit confused on how to submit homework 11. I pushed my code onto Github using $ git push origin avl and on my Github repo it asked me to compare and submit a pull request. I thought we weren't supposed to submit a pull request for this homework, so is there anything else I have to do? When I check my branches, the updated version of my AVLTree.py file doesn't show up.

Thanks!

Hi,
I'm getting the following error and I was wondering if someone could help me out (why is it saying bound method, not trying to print function or anything in the code):

assert False
        +  where False = <bound method AVLTree.is_avl_satisfied of AVLTree([-130, -52, -31])>()
        +    where <bound method AVLTree.is_avl_satisfied of AVLTree([-130, -52, -31])> = AVLTree([-130, -52, -31]).is_avl_satisfied

Thanks!

Hi Professor,

I have a quick question, what do you mean with "Implement this function by modifying the _print functions above." in the preorder , inorder, and postorder methods?

I would really appreciate it if you could explain a little bit more about what the purpose of such methods should be.

Thank you!

I have graded your hw7 and midterm assignments. There are several students who have extensions on these assignments, however, and so I will post solutions as soon as I've received everyone's submissions.

For the midterm, it's unfortunate that I can't give you all your written submissions with the feedback directly on the paper. I tried to give you feedback about the points missed in sakai's notes for the grade, and I'm happy to give you more detailed personal feedback over zoom.

Hi all,

I ran the map.py file on all the hashtags for a country basis and combined them into a reduced.country file. Now the next step is to create an output file for each hashtag using output redirection. Are we meant to do this for both the .lang files and the .country files, or just the .country files? Is this process as simple as manually re-entering the same command for each hashtag?

Thanks

Spring break is almost over, and I'm sure many of you are finding yourselves swamped with work that you've been (understandably) putting off. Therefore, I've decided to grant a 2 day extension on both the hw7 and midterm until Tuesday 31 Mar at midnight.

I created a test case to see how well the codes run. When I run

tree = AVLTree()
tree.root = Node(43)
tree.root.left = Node(18)
tree.root.left.right = Node(22)
print(tree.print_tree('inorder'))
print(tree.is_avl_satisfied())
tree.insert_list([9,21])
print(tree.print_tree('inorder'))

it gives the output correctly

18-22-43-
False
9-18-21-22-43-

However, when I use insert instead of insert_list

tree = AVLTree()
tree.root = Node(43)
tree.root.left = Node(18)
tree.root.left.right = Node(22)
print(tree.print_tree('inorder'))
print(tree.is_avl_satisfied())
tree.insert([9,21])
print(tree.print_tree('inorder'))

it gives an error saying

18-22-43-
False
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
~/Desktop/CS 46/AVLTree.py in <module>
    168 print(tree.print_tree('inorder'))
    169 print(tree.is_avl_satisfied())
--> 170 tree.insert([9,21])
    171 print(tree.print_tree('inorder'))

~/Desktop/CS 46/AVLTree.py in insert(self, value)
    114             self.root = Node(value)
    115         else:
--> 116             AVLTree._insert(value, self.root)
    117 
    118 

~/Desktop/CS 46/AVLTree.py in _insert(value, node)
    127     @staticmethod
    128     def _insert(value, node):
--> 129         if value < node.value:
    130             if node.left is None:
    131                 node.left = Node(value)

TypeError: '<' not supported between instances of 'list' and 'int'

Relevant codes are

class AVLTree(BST):
    def __init__(self, xs=None):
        super().__init__()
        self.root = None
        if xs:
            self.insert_list(xs)

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            AVLTree._insert(value, self.root)
    
    def insert_list(self, xs):
        for x in xs:
            self.insert(x)
            
    @staticmethod
    def _insert(value, node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                AVLTree._insert(value, node.left)
        elif value > node.value:
            if node.right is None:
                node.right = Node(value)
            else:
                AVLTree._insert(value, node.right)
        else:
            print("Value is already present in tree.")

        if AVLTree._is_avl_satisfied(node) == False:
            node.left = AVLTree.rebalance(node.left)
            node.right = AVLTree.rebalance(node.right)
            return AVLTree.rebalance(node)
        else:
            return node

When I run tests in travis, all tests pass except

tests/test_AVLTree.py::test__AVLTree_insert FAILED                       [ 85%]
tests/test_AVLTree.py::test__AVLTree_insert_list FAILED                  [ 90%]
tests/test_AVLTree.py::test__AVLTree___init__ FAILED   

I guess they are related to the same issue.
Any suggestions on how I might fix it? Thank you!

When trying to run the following shell command...

$ ./src/map.py --input_path=/data/tweets_corona/geoTwitter20-02-17.zip

It says permissions are denied for geoTwitter20-02-17.zip. I checked permissions for that file and I do not have execution permissions. I tried to change it using ch mod u+x geoTwitter20-02-17.zip but it won't work, it says "Operation not permitted".

Does anyone have any suggestions? Is changing the permissions of a zip file different from a normal file?

Thanks!

I edited and got the map.py function to run on the first day of the dataset but am unable to run it on the entire dataset.

yismaeel@lambda-server:~/hw09/twitter_coronavirus$ nohup scripts/run_map.sh
>>>nohup: ignoring input and appending output to 'nohup.out'
>>>nohup: failed to run command 'scripts/run_map.sh': No such file or directory 

Is there a different command I should be using to have it run on the entire dataset?

I ran the command

$ nohup ./scripts/run_map.sh

I got:

nohup: ignoring input and appending output to 'nohup.out'
nohup: failed to run command './scripts/run_map.sh': No such file or directory

I changed the path to tweets_corona and still got the error. Any suggestions?

1. My first question has to do with making BST a proper subclass of BinaryTree. When you say You should make the necessary changes in the class declaration line above and in the constructor below. Is this the appropriate response:

def __init__(self, root=None, xs=None):
        if root:
            self.root = Node(root)
        else:
            self.root = None

or do you want us to use super() like this:

def __init__(self, root=None, xs=None):
        super().__init__(root)

2. I followed the lecture's code when creating the find and _find functions, but when I try to find a number not in the BST, it returns None instead of False. I was wondering if this is going to be an issue later in the code? / Why is it not returning False?
   Function Code:

def find(self, value):
        if self.root:
            if BST._find(value, self.root):
                return True
        else:
            return False  


    @staticmethod
    def _find(value, node):
        if value > node.value and node.right:
            return BST._find(value,node.right)
        elif value < node.value and node.left:
            return BST._find(value,node.left)
        if value == node.value:
            return True

Input:

bst = BST()
bst.insert(4)
bst.insert(2)
bst.insert(8)
bst.insert(5)
bst.insert(10)
print(bst.find(11))

Output:

None

Hi everyone, there was a temporary error on the lambda-server that resulted in the hard drive being full, and so you couldn't create new files. If you were running your hw9 code at the time of this error, then your programs likely crashed (with an error message about the disk being full) and will have to be restarted.

Hi everyone,

I've put together another quick survey to get your feedback on how the online data structures course is going. Please take a minute to fill it out so that I can improve the course for the rest of the semester.

Survey link: https://docs.google.com/forms/d/1Ypnnm4Qz79w41cbsvB1vbZn3jylIMbo7_jT0iYLqfsI/

There's three announcements:

1. Good news everyone! I'm not assigning any new homework this week :)

   One of the common themes from the survey (#70) y'all filled out was that most of you have too much work to do, and so I want to give you a short break. This week you should focus on finishing up your AVL and Twitter assignments, and next week I will give you the assignment on the Heap data structure.

2. I will have a special office hours/live lecture dedicated to the Twitter data analysis homework on Tuesday during our normal lecture time (9:35-10:50). In this lecture, I will:

   1. review some of the terminal commands needed for the assignment
   2. cover some common pitfalls that I've seen students make, and how to avoid them
   3. answer any questions that you all have.

3. My Wednesday/Thursday office hours are cancelled this week. My wife has to go in for a followup surgery these days and so I won't be available. (I'm normally not available on Tuesdays because I have to watch my 2yo son then, but because I won't be available on Wednesday/Thursday, I've made special arrangements so that I can be available for you all on Tuesday this week.)

I am not sure why but when I try to save edits to my AVLTree.py file I get the error:

"AVLTree.py" E514: write error (file system full?)

None of my edits are being saved now, has anyone seen this error message before or know how to troubleshoot this?

Hi all,

I wrote my _is_heap_satisfied method and passed all but the 6th test. I wasn't sure why it was failing so I looked at the test itself and think there is an error.

def test__Heap_is_heap_satisified6():
    heap = Heap()
    heap.root = Node(0)
    heap.root.left = Node(2)
    heap.root.left.left = Node(3)
    heap.root.left.right = Node(5)
    heap.root.right = Node(1)
    heap.root.right.left = Node(4)
    heap.root.right.right = Node(-1)
    assert heap.is_heap_satisfied()

Since heap.root.right (the parent) is 1 and heap.root.right.right (the child) is -1, shouldn't this violate the minheap condition that each child must be greater than or equal to its parent?

Thank you

I had this issue resolved thanks to @mikeizbicki but I figured others might run into the same issue when trying to push their respective results for HW9 to Github and wanted to have that fix available for everyone.

Counting objects: 616, done.
Delta compression using up to 80 threads.
fatal: unable to create thread: Resource temporarily unavailable
fatal: The remote end hung up unexpectedly
fatal: The remote end hung up unexpectedly
fatal: The remote end hung up unexpectedly
error: failed to push some refs to 'https://github.com/yismaeel21/twitter_coronavirus.git'

This means that you are having issues with git and not with the lambda servers as your file sizes in the lambda server might be too big.
Type these commands in your terminal and try pushing again and it should work, it did for me.

git config --global pack.windowMemory "100m"
git config --global pack.packSizeLimit "100m"
git config --global pack.threads "1"

after I start running scripts/run_maps.sh

I got nohup: ignoring input and redirecting stderr to stdout
and this nohup: ignoring input and redirecting stderr to stdout keeps increasing.

Now it is like

zli@lambda-server:~/twitter_coronavirus$ scripts/run_maps.sh
nohup: ignoring input and redirecting stderr to stdout
nohup: ignoring input and redirecting stderr to stdout
nohup: ignoring input and redirecting stderr to stdout
nohup: ignoring input and redirecting stderr to stdout
nohup: ignoring input and redirecting stderr to stdout

what does this mean?

Then I checked my output folder, I do have

geoTwitter19-10-01.zip.lang     geoTwitter19-10-29.zip.lang
geoTwitter19-10-02.zip.country  geoTwitter20-02-16.zip.country
geoTwitter19-10-02.zip.lang     geoTwitter20-02-16.zip.lang

and these files are increasing as well

Hi Pythonistas!

As we transition our classroom online, we are going to be relying more heavily on github to coordinate classroom activities. In particular, we will be using github issues for all non-grade classroom communication [1]. I will post announcements, lecture videos, and zoom links here as issues (see #43 for an example), and if you have a question about a homework assignment you should create a new issue (see #44 for an example).

There are two things you need to know in order to use github issues effectively.

1. You must be "watching" this repo. This will ensure that whenever a new issue is posted, you will get an email.

2. Markdown is the language for formatting issues. (This is the same language used to format the README.md files.) The main thing you need to know about markdown is how to include code snippets. To include inline code, use the single backtick ` like this and to include a code block use triple backticks ```. To generate an output like:

   print('hello world')
   

   use the code

   ```

   print('hello world')

   ```

   Whenever you include code in an issue or a reply to an issue, you must use these formatting options or it won't display correctly and I won't be able to help you. Markdown has many other formatting options. You're not required to use any of these options, but if you're curious here's a tutorial: https://guides.github.com/features/mastering-markdown/

Please create a reply to this comment that includes a one line python code snippet just to demonstrate that you know how to use markdown. I've included an example below.

[1] Grades will continue to be posted on sakai. If you have a question about your grades, you should email me at [email protected] since this is private information.

Good morning Pythonistas! And welcome back from spring break :)

I've posted your first lecture on youtube at: https://youtu.be/psEBIb4iDKs

The lecture explains how the class will work going forward, and also your next homework assignment (hw10). The most important point is that we will not be having live class sessions over zoom, but will instead use prerecorded lecture videos.

I'll have zoom office hours today at 2PM Pacific. Feel free to ask questions about the lecture/hw7/midterm or just come by to chat. I'll announce additional office hours later in the week.

Here's my regularly scheduled zoom office hours for cs46. If you cannot make these times, feel free to send me an email to schedule a 1-1 zoom meeting.

We will use zoom url: https://cmc-its.zoom.us/j/644800111

I also have separate office hours for my deep learning class (see the schdeule). You are welcome to visit during those office hours as well, but I will prioritize deep learning students during those times.

[*] Unfortunately, I won't be available on Tuesdays during the normal class time because I have to watch my 2yo son then, and his daycare is closed. Also, the Tuesday 1-2pm timeslot is during his naptime, so this might change depending on his schedule.

I've posted your next lecture video on youtube at: https://www.youtube.com/watch?v=f6HPV45orD4

And your next homework assignment (due this Sunday unless there's a pull request) at: https://github.com/mikeizbicki/cmc-csci046/tree/master/hw11

I created a new branch called avl in my trees repo for hw10. Then I checked it out, and then I did

$ git branch -r

My output was:

  origin/HEAD -> origin/master
  origin/fix-trees
  origin/master
  upstream/master

So when I tried to do

$ git pull origin avl

it did not work. The error was:

fatal: Couldn't find remote ref avl

Sorry, I'm still having some issues with the Twitter coronavirus homework. I got it to work, but I entered the following commands and it stopped working:

$ ^Z
$ bg

I thought this would send it to the background and allow it to run in the background, like we did in the lab, but it seemed to interrupt the program and I can't seem to get it to resume. I tried killing the run_maps.sh processes and starting the process over, but even though I killed the processes, it doesn't seem to work.

This is what my nohup.out file says:

  File "src/map.py", line 53, in <module>
    for line in f:
  File "/usr/lib/python3.6/zipfile.py", line 831, in readline
    return io.BufferedIOBase.readline(self, limit)
  File "/usr/lib/python3.6/zipfile.py", line 836, in peek
    chunk = self.read(n)
  File "/usr/lib/python3.6/zipfile.py", line 872, in read
    data = self._read1(n)
  File "/usr/lib/python3.6/zipfile.py", line 948, in _read1
    data = self._decompressor.decompress(data, n)
KeyboardInterrupt

Is anyone else having trouble logging into Lambda Server right now? When I attempt to connect, I get the follow error:

ssh: connect to host 134.173.191.241 port 5055: Connection refused

Thank you!

I ran the command

nohup ./scripts/run_map.sh

and it gave me the following message:

nohup: ignoring input and appending output to 'nohup.out'

I checked the nohup.out file, which had the following error:

Traceback (most recent call last):
  File "src/map.py", line 43, in <module>
    with zipfile.ZipFile(args.input_path) as archive:
  File "/usr/lib/python3.6/zipfile.py", line 1113, in __init__
    self.fp = io.open(file, filemode)
FileNotFoundError: [Errno 2] No such file or directory: '/data/twitter_corona/*'

Should it be pointing to /data/'Twitter dataset'/* instead?

Hi, I have a question about Travis for the sorting homework. I did the extra credit and got the main and extra credit tests to pass on the lambda server, but on Travis it only shows that the six tests for the main py file passed without showing anything for the extra credit test cases. I know that our grade is the number of test cases that pass on Travis, so I was wondering if this is supposed to happen or if there is something I should do to get the extra credit cases to show up on Travis as well.

Thank you!

My left rotate function is:

@staticmethod
def _left_rotate(node):
        new_root = node.right
        node.right = new_root.left
        new_root.left = node
        node.height = BinaryTree._height(node)
        new_root.height = BinaryTree._height(new_root)
        return new_root

and when I run the test in pytest I get the error:

E       assert [1, 3, 5, 7] == [1, 3, 5]
E         Left contains one more item: 7
E         Use -v to get the full diff

with the rotated tree looking like:

(7 - (5 - (3 - (1 - - ) - ) - ) - )
(5 - (3 - (1 - - ) - ) - )
(3 - (1 - - ) - )
(1 - - )

So I think I am getting an extra left leaf node (?), but I am not sure why. Has anyone else run into this problem or have tips for troubleshooting?

Hi all,
I forked the CoronaVirus Repo and tried to clone it as usual, but am getting this error:

Any ideas how to fix this? Thank you

I've extended the deadline for hw11 to next week Tuesday (14 April) at midnight.

Hi pythonistas!

I've uploaded the next video to youtube: https://www.youtube.com/watch?v=6S3XyPAzWiU

and posted your next homework assignment: https://github.com/mikeizbicki/cmc-csci046/tree/master/hw12

Have a great week :)

1. I copied the code from the lecture for the _is_bst_satisfied() function, making changes so that it is a static function:

@staticmethod
    def _is_bst_satisfied(node, value):
        if node.left:
            if value > node.left.value:
                print('hello')
                return BST._is_bst_satisfied(node.left, node.left.value)
            else:
                return False
        if node.right:
            if value < node.right.value:
                print('hola')
                return BST._is_bst_satisfied(node.right, node.right.value)
            else:
                return False

and my is_bst_satisfied() class function looks like this:

def is_bst_satisfied(self):
        if self.root:
            print('hi')
            return BST._is_bst_satisfied(self.root, self.root.value)
        return True

The print statements are for me to try and figure out where the code is going wrong. When I prompt the functions with this input:

bst = BST()
bst.insert(4)
bst.insert(2)
bst.insert(8)
bst.insert(5)
bst.insert(10)
print(bst.is_bst_satisfied())

I get this output:

hi
hello
None

I was wondering where I went wrong? Does this have to do with your note "There is a major bug in the _is_bst_satisfied function. You will have to correct this bug in your implementation for the homework."

2. I assume the fact that the function returns None is why I'm failing test__BST_is_bst_satisified4 and test__BST_is_bst_satisified5 with the error code:

_________________________ test__BST_is_bst_satisified4 _________________________
    def test__BST_is_bst_satisified4():
        bst = BST()
        bst.root = Node(0)
        bst.root.left = Node(-1)
>       assert bst.is_bst_satisfied()
E       assert None
E        +  where None = <bound method BST.is_bst_satisfied of BST([-1, 0])>()
E        +    where <bound method BST.is_bst_satisfied of BST([-1, 0])> = BST([-1, 0]).is_bst_satisfied
tests/test_BST.py:47: AssertionError
_________________________ test__BST_is_bst_satisified5 _________________________
    def test__BST_is_bst_satisified5():
        bst = BST()
        bst.root = Node(0)
        bst.root.left = Node(-2)
        bst.root.left.left = Node(-3)
        bst.root.left.right = Node(-1)
        bst.root.right = Node(2)
        bst.root.right.left = Node(1)
        bst.root.right.right = Node(3)
>       assert bst.is_bst_satisfied()
E       assert None
E        +  where None = <bound method BST.is_bst_satisfied of BST([-3, -2, -1, 0, 1, 2, 3])>()
E        +    where <bound method BST.is_bst_satisfied of BST([-3, -2, -1, 0, 1, 2, 3])> = BST([-3, -2, -1, 0, 1, 2, 3]).is_bst_satisfied
tests/test_BST.py:58: AssertionError

3. I'm failing the test_BST.py function for find_smallest with a strange error that doesn't happen when I'm testing on my own. My code for these functions is:

def find_smallest(self):
        node = self.root
        return BST._find_smallest(node)
        
    
    @staticmethod
    def _find_smallest(node):
        if node.left:
            return BST._find_smallest(node.left)
        else:
            return node.value

My test input:

bst = BST()
bst.insert(4)
bst.insert(2)
bst.insert(8)
bst.insert(5)
bst.insert(10)
bst.find_smallest()

My test output:

2

Travis output:

___________________________ test__BST_find_smallest ____________________________
    @given(xs=ints)
>   def test__BST_find_smallest(xs):
tests/test_BST.py:124: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
xs = [0]
    @given(xs=ints)
    def test__BST_find_smallest(xs):
        xs = list(set(xs))
        if len(xs)>0:
            x = min(xs)
            bst = BST(xs)
>           assert x == bst.find_smallest()
E           assert 0 == [0]
E             -0
E             +[0]
tests/test_BST.py:129: AssertionError

Am I supposed to change the type of variable it is?

Any help would be appreciated.

Thanks, Ethan

I've had

nohup ./scripts/run_maps.sh

running all day in the background, but when I went back to check on it, I ran

cat nohup.out

and got the error:

Traceback (most recent call last):
  File "src/map.py", line 62, in <module>
    for hashtag in hashtags:
KeyboardInterrupt
Traceback (most recent call last):
  File "src/map.py", line 70, in <module>
    if hashtag in text:
KeyboardInterrupt

I'm not sure what this means, but my log has been updating. Have any of you received this message?

Hi everyone!

There's two upper division CS courses that CMC will be offering next semester that I want to make you aware of:

1. Graph algorithms (taught by prof Sarah Cannon, the other CS prof at CMC). This class will be more theory oriented than this data structures class, and would be a great course to take if you want to learn how to prove that code is correct/incorrect. We'll also be covering some simple graph algorithms in the last 2 weeks of the semester of this course. She has made a poster with more details: Graph Algorithms Poster.pdf

2. Data mining (taught by me!). If you liked the twitter analysis homework and want to learn how to do more advanced analyses, this would be the class to take. For more info, you can find last year's syllabus online at https://github.com/mikeizbicki/cmc-csci145-math166 .

In video "Binary Trees in Python: Introduction and Traversal Algorithms" when LucidProgramming was talking about postorder_print, he copied the code from inorder_print but forgot to change inorder to postorder. So instead of

    def postorder_print(self, start, traversal):
        """Left->Right->Root"""
        if start:
            traversal = self.postorder_print(start.left, traversal)
            traversal = self.postorder_print(start.right, traversal)
            traversal += (str(start.value) + "-")
        return traversal

his code in the video was

    def postorder_print(self, start, traversal):
        """Left->Right->Root"""
        if start:
            traversal = self.inorder_print(start.left, traversal)
            traversal = self.inorder_print(start.right, traversal)
            traversal += (str(start.value) + "-")
        return traversal

As a result, the example he used in the video for postorder was not right

# 4-2-5-6-3-7-1
#               1
#           /       \  
#          2          3  
#         /  \      /   \
#        4    5     6   7 

it should be 4-5-2-6-7-3-1.

He corrected it in the comment section but I did not look at the comment so it took me a while to figure it out LOL. Just want to share it here.

Hey Mike, I was wondering if you will continue to have office hours at the times listed on the syllabus or if you are switching to only having 1-on-1 appointments that are scheduled via email?

I have a quick question about my code for the static method for the height of the trees.
I quite don’t understand why my chunk of code won’t work.
The error I keep getting says: 

AttributeError: 'Node' object has no attribute ‘_height'

I attached a screenshot of my code for reference but I don’t fully understand the difference between the static and non-static method..

Hi All,
I was having an issue with my insert method and wasn't sure where it was failing so included a couple of print statements in this method (the rebalancing statement) as well as the test (printing the inorder traversal) I was failing so as to give me more info.

These print statements showed me that my "rebalancing..." print statement was called in cases when the tree only has two nodes (when it is in fact balanced), as such:

[17223]
[5127, 17223]
balance factor is 2
rebalancing...
[17223]



[17223]
[5127, 17223]
balance factor is 2
rebalancing...
[17223]



[-16416]
[-16416, 3457]
balance factor is -2
rebalancing...
[-16416]

For this reason I included a print statement in "is_avl_satisfied" that prints out the balance factor and sure enough for a tree with 2 nodes it is printing a balance of factor of 2 or -2. This doesn't make any sense, and I'm unsure where the error lies.

Here is my is_avl_satisfied method:

    def _is_avl_satisfied(node):
        '''
        FIXME:
        Implement this function.
        '''
        if AVLTree._balance_factor(node) not in [-1,0,1]:
            print('balance factor is', AVLTree._balance_factor(node))
            return False
        if node:
            if node.left and node.right:
                return AVLTree._is_avl_satisfied(node.left) and AVLTree._is_avl_satisfied(node.right)
            if node.left and node.right is None:
                return AVLTree._is_avl_satisfied(node.left)
            if node.right and node.left is None:
                return AVLTree._is_avl_satisfied(node.right)
        return True

Here is my insert method:

    def _insert(value,node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                AVLTree._insert(value, node.left)
        elif value > node.value:
            if node.right is None:
                node.right = Node(value)
            else:
                AVLTree._insert(value, node.right)
        if AVLTree._is_avl_satisfied(node) == False:
            print('rebalancing...')
            return AVLTree.rebalance(node, value)

And here is the test I am failing.

__________________________ test__AVLTree_insert ____________________________

    @given(xs=ints)
>   def test__AVLTree_insert(xs):

tests/test_AVLTree.py:193:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

xs = [0, 1, 2]

    @given(xs=ints)
    def test__AVLTree_insert(xs):
        print('\n\n')
        print('test we interested in:')
        xs = list(set(xs))
        avl = AVLTree()
        for x in xs:
            avl.insert(x)
            print(avl.to_list('inorder'))
>           assert x in avl.to_list('inorder')
E           AssertionError: assert 2 in [0]
E            +  where [0] = <bound method BinaryTree.to_list of AVLTree([0])>('inorder')
E            +    where <bound method BinaryTree.to_list of AVLTree([0])> = AVLTree([0]).to_list

tests/test_AVLTree.py:201: AssertionError

Please let me know if you have any suggestions for how to fix this issue. Thank you!

I copied the code exactly from the lectures for both the size and size_ functions and also put the Stack class in my code.

For some reason I am getting errors related to the node = stack.pop() line in the size function.

def size(self):
        if self.root is None:
            return 0
        
        stack = Stack()
        stack.push(self.root)
        size = 1
        while stack:
            node = stack.pop()
            if node.left:
                size +=1
                stack.push(node.left)
            if node.right:
                size +=1
                stack.push(node.right)
        return size

For some reason when I try using the print(tree.size_(tree.root) function, it returns None:

def size_(self, node):
        if node is None:
            return 0
        return 1+ self.size_(node.left) + self.size_(node.right)

Maybe I'm missing something really simple here and am just not seeing it.

Any help would be appreciated!

Thanks, Ethan

I'm trying to kill a process that's running in the background using the kill function. However when using the ps command, below is what I'm getting.

  PID TTY          TIME CMD
 8940 pts/2    00:00:00 bash
35030 pts/2    00:00:00 ps

I also tried using ps -aux | grep pgatabazi and I'm still not finding the PID value of the running process.

I've created a short survey to help me schedule our lectures and office hours for the rest of the semester. It should only take a minute to fill out, so please do so.

Here's the link: https://docs.google.com/forms/d/1TtywN5oX27C2Bcj5FANv1wtmdXobhW2HALgAvvi7pNg

I tried running this line of code for task 3

./src/visualize.py --input_path=/home/yismaeel/hw09/twitter_coronavirus/reduced.lang --key='#covid-2019' | head > viz/'#covid-2019'

But I kept on getting a traceback error and I dont quite understand what is causing this traceback error

>>>-bash: viz/#covid-2019: No such file or directory
>>>Traceback (most recent call last):
  File "./src/visualize.py", line 26, in <module>
    items = sorted(counts[args.key].items(), key=lambda item: (item[1],item[0]), reverse=True)

I know lots of you are overwhelmed with life and lots of classwork right now, so I'm granting a conditional extension on homework 10 until Friday at midnight. In order to get the extension, you just have to meet with me on zoom sometime before the assignment is due tomorrow. I'll be on during the normal office hours window from 1-2pm, but if you can't make the normal time than suggest another time below. I'm free 10-11:30, 12-2pm, and 3-5pm.

(If I've already granted you an extension, you don't need to meet with me on zoom again.)

To ease your transition into the online classroom, I have extended your homework 7 and take home midterm due dates until the end of spring break (Sunday, 29 March at midnight).

For homework 7, you will submit it just like your previous assignments by uploading a link to sakai.

For the midterm, you have two submission options: you may turn in a paper copy to me before leaving campus; or you may scan your midterm and email me the scans before the deadline.

Hi all,

I went to check on my nohup.out file and am seeing this error pop up pointing back to a print line I included for debugging purposes.

Any ideas how to fix this error?

I ran nohup./scripts/run_map.sh and this was the error I was getting.

gchoi@lambda-server:~/twitter_coronavirus$ nohup ./scripts/run_map.sh
nohup: ignoring input and appending output to 'nohup.out'
nohup: failed to run command './scripts/run_map.sh': No such file or directory

I think the error here has to do with not being in the correct file /data/tweets_corona/* but I am not sure how to fix this. When I do nohup ./scripts/run_map.sh > /data/tweets_corona/* this is what I get:
-bash: /data/tweets_corona/*: ambiguous redirect

If anyone can help I'd appreciate it!

Hi everyone!

When I run the command:

$ ./src/visualize.py --input_path=reduced.lang --key=#covid2019 | head > viz/#covid2019

I get the following error:

-bash: viz/#covid2019: No such file or directory
Exception ignored in: <_io.TextIOWrapper name='<stdout>' mode='w' encoding='UTF-8'>
BrokenPipeError: [Errno 32] Broken pipe

Any ideas what I am doing wrong? Thanks!

I have run my program for 10+ hours and I accidentally restarted my computer. When I log in again and check bg, it says

bg: current: no such job

Then I check outputs and log, the program seems to stop... How can I restart my program from where it left off? Thanks!

Fernanda and I had a few questions about the HW:

1. To clarify, the _merged function is simply adding the two lists, correct? Meaning we wouldn't have to use cmp_standard.
2. For the merged_sorted function, do we have to incorporate the previous functions?
3. For the merged_sorted function, can we use while loops or should we be using recursion?

Thank you :)