Udacity – CS101 & CS373 – Week Four

We’ve had three weeks, so far of CS101 and CS373. I am impressed with the improvements that have been made so far. Most of the little annoyances have already been fixed. The two most important ones are: the Course Content section remembers your current progress, and the homework problems now remember your previously saved values. There has been some definite progress. Functionally, the Udacity site isn’t any better than Coursera, and might be a little worse. However, polish-wise, it definitely is the champ, and as someone who has worked on many UIs, getting a nice polished design is a lot of work. I am continually impressed with the quality of this site, put together in such a short amount of time. Though, there are still a couple of improvements that I’d like to see, and some major bugs that have been affecting grading.

The improvements that I’d like to see are:

  • A better integration between Progress which shows which problems you got right, and Course Content which shows the question along with an explanation of the subject matter.
  • A resizeable coding window would be nice as well. I don’t always use the coding are they give, but when I do, I would love to be able to drag the bottom corner and increase my workspace area.
  • *** When there are carry over questions, I would like to be able to keep my code from the previous question. Currently, I can return to the previous question and then copy and paste, but that is less than ideal. This one I gave three gold stars for difficulty because, as a software engineer, I understand the effort involved in accomplishing this, not to mention that it would be prone to having many bugs.

The big grading bug affected three of my homework assignments. Apparently, there is a problem copy and pasting code into the code editor when there is not enough whitespace left at the end. At least that’s the impression I’ve gotten. Though it’s not something I am 100%. It seems like they team knows about the problem, and they will be regrading all of the assignment after upgrading to the latest version of python. I would like a better idea about a timeline of all of that so that I can verify that my solutions were indeed correct. However, I do understand the magnitude of the effort involved in completing this, so I am okay waiting for the grades to be fixed.

And, now on to the class specifics:

CS101 – BUILDING A SEARCH ENGINE

For anyone, learning how to program is difficult. It doesn’t matter how good your teacher is, there are a lot of new concepts that will take a while to sink in. As someone who has already gone through that, I cannot really understand what the introductory students are going through, just as I have no idea what my ten month old is going through with his first few steps. If you are taking this class, and have never programmed before, then I want to give you a real hand. Congratulations, it is difficult! You may feel that it is all over your head, but I promise you if you stick with it things will start to click in a month or two or more. Also, nothing else I say here applies to you.

The first two units were pretty introductory. There were a few tricky questions, but it was all just intro to programming material. However, now that he’s taught you programming, the difficult of the third unit jumped up a step. You are now required to apply all of your knowledge to start completing real programming assignments. Some of the problems are genuinely difficult and or tricky. I even got a tricky question wrong (HW3.2).

I didn’t even get a 100%, I got 3.2 wrong because it was actually a little tricky (I also got 3.3 wrong, but that was due to the whitespace bug as my code was exactly the same as the code Prof. David Evans showed in the explanation.) The only reason I signed up for it–as I mentioned previously–was for the competition at the end of the course. I didn’t expect to have any challenge for this course, so I am pleasantly surprised. Here are some of the more interesting problems.

CS101 – HW2.3 Median

I’m posting this one, not because it was a difficult problem, but because the solution is elegant. Though I must say, I solved it the brute force method. This solution I took from reddit

1
2
3
4
5
6
# Define a procedure, median, that takes three
# numbers as its inputs, and outputs the median
# of the three numbers.
 
def median(a, b, c):
    return sorted([a, b, c])[1]

CS101 – HW3.5 List Of Lists

This one is also a nicer solution than the brute force method. It uses something called a list comprehension. I have just started with python, so I am still learning all of their tricks myself. If you don’t know what they are, I suggest you look them up and practice making a few. They are one of the nicer features of python.

1
2
def total_enrollment(universities):
    return sum([u[1] for u in universities]), sum([u[1]*u[2] for u in universities])

CS101 – HW3.6 Max Pages

I like this one because the solution is so simple. It requires just one line of code to complete. My solution is slightly different than the one that Prof Evans showed in that it will stop looping immediately upon reaching the max pages. (Try running the two version of the function with a print statement at the beginning of the loop, and you will see sometimes Evans has a couple more loops where pages aren’t added to the crawled list.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#Modify the crawl_web procedure to take a second parameter,
#max_pages, that limits the number of pages to crawl.
#Your procedure should terminate the crawl after
#max_pages different pages have been crawled, or when
#there are no more pages to crawl.
 
def crawl_web(seed,max_pages):
    tocrawl = [seed]
    crawled = []
    while tocrawl:
        page = tocrawl.pop()
        if page not in crawled:
            union(tocrawl, get_all_links(get_page(page)))
            crawled.append(page)
 
        #Added lines here to break when crawled has reached max_pages.
        if len(crawled) >= max_pages:
            break
 
    return crawled

CS101 – HW3.7 Max Depth

I posting this solution because I solved it with a completely different method. Prof. Evans used a loop, I used recursion instead. In a real world situation of crawling the web, using recursion is probably a bad idea. The max_depth would likely be very large, and recursion could cause a stack overflow. In addition, recursion is much harder to parallelize than standard for loops, and web crawling is a demanding task that would need a parallelized solution. However, for a toy problem, recursion could create a nice, elegant solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#Modify the crawl_web procedure to take a second parameter,
#max_depth, that limits the minimum number of consecutive
#links that would need to be followed from the seed page to reach this
#page. For example, if max_depth is 0, the only page that should
#be crawled is the seed page. If max_depth is 1, the pages
#that should be crawled are the seed page and every page that links
#to it directly. If max_depth is 2, the crawl should also include all pages
#that are linked to by these pages.
 
def crawl_web(seed, max_depth, previous=[]):
    previous.append(seed)
 
    #base case of zero depth returns the previous array plus the seed.
    if max_depth == 0:
        return previous
 
    pages = get_all_links(get_page(seed))
 
    #create a new array of these pages, and all previously crawled pages
    crawled = []
    union(crawled, previous)
 
    for page in pages:
        if page not in previous:
            #this crawl_web should check against previously plus all other at this depth.
            union(crawled, crawl_web(page, max_depth-1, crawled))
 
    return crawled

CS101 – HW3.8 Sudoku

The sudoku problem was also an interesting one. I think this code is considerably simpler than the code Prof. Evans demonstrated in his explanation. However, even though I did get this question marked correct, now that I’m looking at this code I realized it has a bug. See if you can catch it. I’ll put the answer at then end of this post.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def check_sudoku(square):
    n = len(square)
 
    for i in range(n):
        row = []
        column = []
        if not len(square[i]) == n:
            return False
 
 
        for j in range(n):
            if square[i][j] in row:
                return False
            if square[j][i] in column:
                return False
 
            row.append(square[i][j])
            column.append(square[j][i])
 
    return True

CS373 – PROGRAMMING A ROBOTIC CAR

I’ve been surprised, the last two weeks of CS373 may actually be easier than CS101. This is not to say that the CS373 material isn’t difficult. However, the material has been organized in bite sized pieces with one lecture building off of the previous one perfectly. As a result there are no large leaps of understanding required. It’s difficult material. I am quite impressed with Thrun as a professor. As far as I understand, this is the first time he has taught this syllabus, usually it takes a couple years to refine material to this level. I imagine it will only get better, s future attendees of CS373 are in for real a treat.

CS373 – Unit 2 Kalman Filters

Unit 2 about Kalman filters was pretty easy as far as the work was concerned. The behind Kalman filters is pretty advanced, but we never needed to go into those details. As long as you followed along with the lectures, it was just a matter of directly applying the formulas that Thrun gave. The 2D Kalman Filter was tougher, but it was really just a matter of keeping track of dimensions. For anyone with a background in linear algebra/matrix multiplication it was rudimentary. For someone without that knowledge…probably significantly more difficult.

CS373 – Unit 3 Particle Filters

This has been my favorite unit so far. I particularly like particle filters. It is a very elegant solution to a tough problem. The animations showing them working are particularly interesting. I would like to redo the javascript localization demo I talked about previously with particle filters. Perhaps I’ll try it out later, when I have some more time.

The homework assignments were the right level of challenge for me. They required a little bit of thought, but weren’t so time consuming that I wasn’t able complete them. Unfortunately, I don’t have verification that I got them correct, because my solutions to HW3.4 and HW3.6 were marked wrong due to the whitespace bug that I previously mentioned.

CS373 – Unit 4 Planning and Search

The AI class that Thrun and Norvig taught in the spring also went over the search algorithms. However, I find that I am learning so much more in these lectures. I really give credit to the exercises adding a tremendous amount by engaging me and testing my understanding in a way that a multiple choice quiz cannot do. I still haven’t started on the homework, so I won’t discuss them here, but I thought I would present some of my solutions to the various in unit quizzes.

CS373 – Unit 4.8 First Search Program

This is the first programming question for unit. I’m posting my solution here because I think the code is cleaner than the example code. Here are a few differences from the solution that Thrun posted:

  • pop(0) instead of .reverse() since that will return the first value.
  • Multiple assignment is a nice python feature that helps with readability here. e.g. x, y = location
  • A single closed array, rather than checking against both the grid and a list of already visited items simplifies the logic. Here, I directly modified the grid, though in later exercises, I first copy it into a closed array.
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    
    # ----------
    # User Instructions:
    # 
    # Define a function, search() that takes no input
    # and returns a list
    # in the form of [optimal path length, x, y]. For
    # the grid shown below, your function should output
    # [11, 4, 5].
    #
    # If there is no valid path from the start point
    # to the goal, your function should return the string
    # 'fail'
    # ----------
     
    def search():
        # ----------------------------------------
        # insert code here and make sure it returns the appropriate result
        # ----------------------------------------
        m = len(grid)
        n = len(grid[0])
        nodes = [[0,init[0], init[1]]]
     
        x0, y0 = goal
     
        while len(nodes) > 0:
            nodes.sort()
            value, x, y = nodes.pop(0)
     
            # Check if we have reached the goal.
            if x == x0 and y == y0:
                return [value, x, y]
     
            value2 = value+1
            for d in delta:
                x2 = x+d[0]
                y2 = y+d[1]
     
                #Check if we are in bounds
                if x2 < 0 or y2 < 0 or x2 >= m or y2 >= n:
                    continue
     
                # This has a 1 for all barriers, and all visited cells.
                if grid[x2][y2] == 0:
                    grid[x2][y2] = 1
                    nodes.append([value2, x2, y2])
     
     
        return 'fail'

    CS373 Unit 4.9 Expansion Grid

    I won’t put the code here for the expansion grid, since the differences are in the same vein as those in Unit 4.8.

    CS373 Unit 4.9 Print Path

    I completed this one quite differently from Thrun. In addition to the improvements that I’ve already mentioned, I made another change that that I feel simplifies the code nicely. Thrun stores the action taken to get to a cell when it is visited. I store the entire path that was taken to get to a cell. Therefore at the end, populating the path is just a matter of looping through the path of the goal cell. At the end, there is no need to retrace my steps, because they are already stored.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    
    def search():
        x0, y0 = goal
        m = len(grid)
        n = len(grid[0])
     
        closed = [row[:] for row in grid]
        closed[init[0]][init[1]] = 1
     
        paths = [[[] for j in range(n)] for i in range(m)]
     
        nodes = [[0, init[0], init[1]]]
     
        while len(nodes) > 0:        
            nodes.sort()
            loc = nodes.pop(0)
     
            g, x, y = loc
            path = paths[x][y]
     
            # Check if the goal has been reached
            if x == x0 and y == y0:
                break
     
            g2 = g + 1
     
            for i in range(len(delta)):
                d = delta[i]
                d_name = delta_name[i]
     
                x2 = x + d[0]
                y2 = y + d[1]
     
                # Check if out of bounds
                if x2 < 0 or y2 < 0 or x2 >= m or y2 >= n:
                    continue
     
                if closed[x2][y2] == 0:
                    closed[x2][y2] = 1
                    nodes.append([g2, x2, y2])
     
                    # Create a new path, adding the last move
                    path2 = path[:]
                    path2.append([d_name, x, y])
                    paths[x2][y2] = path2                     
     
     
        # The final path is the path stored in the goal.
        final_path = paths[x0][y0]
     
        # Build the shortest_path array default
        shortest_path = [[' ' for j in range(n)] for i in range(m)]
        shortest_path[x0][y0] = '*'
     
        #populate with the final path.
        for move in final_path:
            shortest_path[move[1]][move[2]] = move[0]
     
        return shortest_path

    CS373 Unit 4.12 Implementing A*

    This required just changes to just a few lines from the expand function, so I won’t post the code.

    CS373 Unit 4.17 Value Program

    The code I used for this was considerably shorter than Thrun’s solution. I used a nice trick that enabled me to almost completely re-appropriate my code for the expansion grid unit. The only changes are:

    1. Initialize the values to 99 instead of -1
    2. Start the search from the goal cell
    3. Instead of finishing when we have reached a goal, we end only when there are no more nodes to expand.
      In other words, when there are no more cells that can be reached from the goal.

    I think you will agree, the resulting code is much easier to understand.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    
    # Create a function compute_value() which returns
    # a grid of values. Value is defined as the minimum
    # number of moves required to get from a cell to the
    # goal. 
    #
    # If it is impossible to reach the goal from a cell
    # you should assign that cell a value of 99.
     
    def compute_value():
        m = len(grid)
        n = len(grid[0])
     
        closed = [row[:] for row in grid]
        closed[goal[0]][goal[1]] = 1
     
        values = [[99 for i in range(n)] for j in range(m)]
     
        nodes = [[0, goal[0], goal[1]]]
     
        while len(nodes) > 0:
            nodes.sort()
            node = nodes.pop(0)
     
            value, x, y = node
            values[x][y] = value        
     
            value += 1
     
            for move in delta:
                x2 = x + move[0]
                y2 = y + move[1]
                if x2 < 0 or y2 < 0 or x2 >= m or y2 >= n:
                    continue
     
                if closed[x2][y2] == 0:
                    closed[x2][y2] = 1
                    nodes.append([value, x2, y2])
     
        return values

    CS373 Unit 4.18 Optimal Policy

    Again, I was able to reuse the search code from before. All I needed to do was populate a names array instead of a values array. Because all steps are of equal cost and I am opening cells in the order of lowest cost, the first time I reach a cell, it will be with an optimum move. Unfortunately, there was a problem with grading this assignment, so though I found an optimum path I was graded incorrectly on this problem because the grader found a different optimum path.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    
    def optimum_policy():
        m = len(grid)
        n = len(grid[0])
     
        closed = [row[:] for row in grid]
        values = [[99 for i in range(n)] for j in range(m)]
        names = [[' ' for i in range(n)] for j in range(m)]
     
        nodes = [[0, goal[0], goal[1]]]
        while len(nodes) > 0:
            nodes.sort()
            node = nodes.pop(0)
     
            value, x, y = node
            values[x][y] = value
            closed[x][y] = 1
     
            value += 1
     
            for i in range(len(delta)):
                move = delta[i]
                name = delta_name[i]
     
                # Subtract delta, because we are backtracking
                # and we want to match the delta_name
                x2 = x - move[0]
                y2 = y - move[1]
                if x2 < 0 or y2 < 0 or x2 >= m or y2 >= n:
                    continue
     
                if closed[x2][y2] == 0:
     
                    names[x2][y2] = name
                    closed[x2][y2] = 1
                    nodes.append([value, x2, y2])
     
        return names

    CS373 Unit 4.19 Left Turn Policy

    This question is considerably more work than any of the other problems, so much so that it deserves its own post. I will add another post on this at a later time.


    CS101 – 3.7 Bug

    The code doesn’t verify that the numbers are all in the proper range. e.g [[1,3][2,1]] would have been returned True.

This entry was posted in Online Learning and tagged , , , , , . Bookmark the permalink.

One comment on “Udacity – CS101 & CS373 – Week Four

  1. Pingback: Udacity – Unit 4.19 Left Turn Policy » Jacob Eggers

Leave a Reply

Your email address will not be published. Required fields are marked *

*

HTML tags are not allowed.