Udacity – Unit 4.19 Left Turn Policy

This was a great assignment. By far the most challenging for far…in a good way.

My solution for this problem was very similar to the one for 4.17. In problem, I back propagated the path from the end state. Since we also needed to keep track of the final path taken, I also borrowed some techniques from Unit 4.9. There were a couple of complexities that required additional work.

One of the added difficulties was the addition of a variable step cost. That necessitated both keeping track of the additional dimension of orientation and restricting possible movements.

In addition, I needed an enhancement to building and looping through open nodes. Because the costs of actions varied, I was no longer able to just store the cost of the current node; I also needed to add information about the previous action. Therefore, for every location I need to add a new open node corresponding to each of the three actions. Then, when I pick items off of the open node list, I prioritize by minimizing (cost of node) + (cost of action) instead of just by cost of node. When the initial node is reached, we are assured of having the lowest possible cost because every other open node has a higher cost.

Here’s my commented code:

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
def optimum_policy2D():
    xN, yN = goal
    x0, y0, orient0 = init
    m = len(grid)
    n = len(grid[0])
 
    #Populate the closed with information from the grid.
    closed = [[[ cell for k in range(4)] for cell in row] for row in grid]
    paths = [[[ [] for k in range(4)] for j in range(n)] for i in range(m)]
 
    # Create the open list by building an array goal states,
    # plus valid actions to have gotten there.
    open = []    
    for i in range(len(action)):        
        for j in range(len(forward)):
            fx, fy = forward[j]            
            #verify that the cell is open
            if grid[xN-fx][yN-fy] == 0:
                closed[xN][yN][j] = 1
                open.append([cost[i], i, xN, yN, j])
 
    # While there are more cells to explore, we go backwards from 
    # the goal state.
    while len(open) > 0:
        #Take the cheapest point off of the list.
        open.sort()
        loc = open.pop(0)
 
        g, a_index, x, y, orient = loc
 
        #check if we have reached the goal
        if x == x0 and y == y0 and orient == orient0:
            break
 
        #Copy the path informtion for later use
        path = paths[x][y][orient]
        path = path[:]
 
        #grab the parameters for the specified action...
        fx, fy = forward[orient]
        a = action[a_index]
 
        # ... and take the action if it is in bounds
        x -= fx
        y -= fy    
 
        if x < 0 or y < 0 or x >= m or y >= n:
            continue
 
        orient -= a
        orient %= 4
 
        # Check if we had explored this cell before.
        if closed[x][y][orient] == 0:
 
            # Save the new path to this location and mark it as closed            
            path.append([action_name[a_index], x, y])
            paths[x][y][orient] = path            
            closed[x][y][orient] = 1
 
            # Add in all of the possible actions to the open array
            for i in range(len(action)):
                open.append([g + cost[i], i, x, y, orient])
 
 
    #the best path is the path to the finish
    best_path = paths[x0][y0][orient0]
 
    #fill in the policy with the data from the 
    policy2D = [[' ' for j in range(n)] for i in range(m)]
    policy2D[xN][yN] = '*'
    for step in best_path:
        name, x, y = step
        policy2D[x][y] = name
 
    return policy2D
Posted in Online Learning | Tagged , , , | Leave a comment

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.

Posted in Online Learning | Tagged , , , , , | 1 Comment

Coursera – SaaS – Week Two & Three

The Coursera Software as a Service class is one of several online courses that I’m currently looking at.

Week One Review

The first week of the SaaS class had been a boring 10,000 foot view of SaaS, Computer Architecture, agile methodologies, …etc. These lectures might have been useful to the Berkeley class full of students who had never had real world experience in software development. However, for a software engineer with industry experience, such as myself, it was more like reading the cliff notes of a favorite book. It overly simplistic and added no new insight.

Week Two

While the first week didn’t impress me, I opted to withhold final judgement for a few of weeks. I was looking forward to learning Ruby with actual programming assignments. I was not disappointed. I finished the first homework assignment last week and fully enjoyed it. The lectures on Ruby have been far more engaging than the first week. They have been helpful to develop an understanding of Ruby’s syntactic sugar and best practices. In addition, the assignments were well suited to showing off the unique features of Ruby, and were challenging enough to maintain my interest.

The first homework assignments were mostly introductory level problems to get a programmer familiar with Ruby syntax. Things such as list enumeration and accessor definitions. There was a fairly interesting use case of using class_eval to define a custom accessor type of attr_accessor_with_history. I would say overall, the difficulty level was moderate. Anyone with prior programming experience should be able to complete them without too much effort.

Week Three

The amount of work for week three has jumped a bit over week two. I had initially been running my code against ruby 1.8.6, while looking at the api for 1.9.4, and so came across some discrepancies. I had to replace a call to .reverse() because while Array does have that method, Enumerable doesn’t. However, I had to do some trial and error finding the right methods as there were a number of methods on Enumerable that were added in 1.9: ((1..9).count and .reverse_each .each_with_index, ….) Now that I’m up to date I shouldn’t have that problem again.

In addition, parts 3 – parts 5 required some more involved work. To start, the setup wasn’t completely straightforward. Error after error popped up while I installed rails, bundler, rvm, libksba, home brew, ruby 1.9.2, use ruby1.9.2, postgres. Then, I signed up for herokuapp, installed it, ran the migration ran it renamed site … before finally getting bundle install to work and load up the website. All of this just to start working on the assignment, far more time than I expected. However, it was a good learning experience. I can’t say that I’ll be any faster the next time I need to do this, but a few more attempts and the learning curve should start to level off.

Once the setup was finished, the actual programming assignments weren’t trivial either. They required either prior experience with rails, or some careful re-watching of the lectures to help find where the needed changes would go.

Again, for those interested in how the homeworks are scored, I’ve the point system for everyone’s reference:

Part1 = %"
Currency conversion
  correctly converts currency from rupees to dollars (singular) [2 points]
  correctly converts currency from yen to dollars (singular) [2 points]
  correctly converts currency from euro to dollars (singular) [2 points]
  correctly converts currency from rupees to dollars (plural) [3 points]
  correctly converts currency from yen to dollars (plural) [3 points]
  correctly converts currency from euro to dollars (plural) [3 points]
  correctly converts currency from rupees to yen, euros to rupees, yen to euros [15 points]
 
adapted palindrome?
  correctly identifies positive and negative palindromes [30 points]
 
enumerable palindrome?
  correctly identifies simple array positive palindromes [6 points]
  correctly identifies simple array non-palindromes [6 points]
  should not error on non-sensical cases of enumerables, like hashes [5 points]
  should still work for the case of non-array enumerables that do make sense, like iterators (valid palindrome) [15 points]
  should still work for non-array enumerables that do make sense (invalid palindromes) [8 points]"
 
Part2 = %"
CartesianProduct
  should work for the first example given in the homework [15 points]
  should work for the second example given in the homework [10 points]
  should return nothing for the case where both of them are empty [15 points]
  should work for other examples for 2x2 [20 points]
  should work for 3x3 and 4x4 [40 points]"
 
Part3 = %"
App
  should respond to simple request [0 points]
 
Table header
  should have link to sort by title [10 points]
  should have link to sort by release date [10 points]
 
Table
  should be sortable by title [20 points]
  should be sortable by release date [20 points]
  should highlight title header when sorted [20 points]
  should highlight release date header when sorted [20 points]"
 
Part4 = %"
GET /movies
  should be successful
  should have #ratings_submit button [10 points]
  should have checkboxes [10 points]
  when selecting a movie rating
    should only display movies of that rating [30 points]
    should automatically check the selected rating in the response [25 points]
  when selecting a sort column
    should preserve the ratings filter [25 points]"
 
Part5 = "
GET /movies
  basic tests
    should be successful
    should have #ratings_submit button
    should have checkboxes
    should have #movies
    should have #title_header
    should have #release_date_header
  when selecting a movie rating
    should remember the rating selected [20 points]
    should allow new ratings to be selected [15 points]
    should redirect to a RESTful route [15 points]
  when selecting a sort field
    should remember the sort order [20 points]
    should allow a new sort order to be selected [15 points]
    should redirect to a RESTful route [15 points]"

Wrap Up

I am so far quite satisfied with the class so far. The course is challenging enough that I am need to put some effort into the course. While I find that I generally don’t need to reference the lectures very frequently, when I do the material is quite accessible if a little haphazard. There’s certainly no handholding in this class, and that is not a bad thing. Professors Fox and Patterson expect the students to know a little something about programming, and figure it out for themselves when they don’t. However, that is not to say that everything about this class has been perfect.

The instructions on the homework have not been as clear as they could have been. The process of submitting hasn’t been explained on the pdf describing the assignment. Neither has the scoring system been detailed. It is only after making a submission that you see how points are awarded for the homeworks. I see no reason not to have made them available on the assignment. In fact, the whole pdf was pretty ugly, which made it made it more difficult to read and understand.

The submission process was also a little rocky. Due to server load issues, the first problem I submitted wasn’t graded for a number of hours. During this time, there was no clear message as to whether the assignment had been submitted successfully. Instead, one was left to speculate if a grade would come back before the due date at all. Other submissions were processed more quickly, but never without some delay. This lackluster performance doesn’t instil much confidence in ruby for production environments. These small issues that I found, led me to post my own more thorough instructions here.

Also, while the lectures are quite good, they are just recorded straight from the classroom and then chopped up into ~10min clips for the web. It seems to work better when, as has been done in the other courses, the lectures are specifically tailored and edited for the web. The quality of video tends to be better, and the lectures also have natural starts and finishes in ~5min bite sized pieces.

However, I think it is very important to emphasize that, while there were some minor issues, overall the class has been fantastic. Professors Armando Fox and David Patterson are doing us a great service in offering this class to the public at large for no cost. This type of class is a new concept and there are bound to be wrinkles, especially when compared next to Andrew Ng’s Machine Learning class, which was as close to perfect as a course can be. Ng is a a brilliant teacher, able to breakdown truly large, complex problems into digestible pieces. The homework assignments for that class were clearly outlined. All instructions and code templates were downloaded in a neat zip. The assignment description had step by step instructions with clear explanations of the grading system. Problems could be submitted quickly and easily, straight from the command line. In addition, the problems were scored without delay giving immediate and clear feedback on whether the solution was completed successfully. The machine learning class also had tests so that you could check your progress on the problem sets before submitting the assignments. I came out of that class having learned a huge amount about several important machine learning techniques, and with an excitement to start applying the knowledge.

Next to the machine learning class, the SaaS class is merely good. Standing alone, it is great. However, I expect it the quality of these courses to only improve as the professors learn what works, what doesn’t, and are able to finally solidify a syllabus that is specifically geared for the web environment. Even in the couple weeks that SaaS has been running, Tthere have already been a number of improvements made to both the course and the platform:

  • HTML5 Video has been buggy, so they added an option to revert to Flash Video. Note to all Flash haters HTML5 video and audio clearly aren’t ready for prime time yet
  • Instructions for assignments improved from HW1 to HW2 (Just to clarify, HW1 was week two and HW2 is week three) with clear links to pastebin templates to get you started on the assignments
  • The videos now remember what speed you were playing at (Though, annoyingly volume still resets to 100%.)
Posted in Online Learning | Tagged , , , | Leave a comment

Coursera – SaaS – How to Submit an Assignment

I’ve just started working on the assignment for the SAAS course, and I realized that people might have questions on how to submit a question since it’s not immediately obvious how to do so. Nor was it clear, how the question would be graded.

Step 1: Make one file for each part.

For my first submission, I didn’t realize that both Part 1: (a) & (b) should be in the same file. Here’s a template to get you started on Part 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def palindrome?(string)
  # your code here
end
 
def count_words(string)
  # your code here
end
 
puts palindrome?("A man, a plan, a canal -- Panama")  #=> true
print "  expect true\n"
puts palindrome?("Madam, I'm Adam!")  # => true
print "  expect true\n"
puts palindrome?("Abracadabra")  # => false (nil is also ok)
print "  expect false or nil\n"
puts count_words("A man, a plan, a canal -- Panama").inspect
# => {'a' => 3, 'man' => 1, 'canal' => 1, 'panama' => 1, 'plan' => 1}
print "  expect {'a' => 3, 'man' => 1, 'canal' => 1, 'panama' => 1, 'plan' => 1}\n"
puts count_words("Doo bee doo bee doo").inspect  # => {'doo' => 3, 'bee' => 2}
print "  expect {'doo' => 3, 'bee' => 2}\n"

Note: I’ve added the puts for help with debugging, you won’t need them in the file when you submit, though there is no harm in keeping them as they won’t affect the grading. Also, notice the .inspect, this will print a pretty format.

Step 2: Code the assignment

I generally work in vi, and just run ruby part1.rb from the command line to check that the program is running correctly. However, I have found codepad.org to be an invaluable tool. Codepad is an online compiler/interpreter. You can create your files in there, run the code to check that it works, and then just click the [raw code] link at the top when you’re done. This will download the code into a file which you can then use for submitting. Make sure you check the private box, otherwise your code will be visible to others in recent pastes.

Here are codepad.org links to get you started:

Step 3: Submit the assignment

Don’t be afraid to submit multiple times. Only the last submission will count towards your homework score.

  1. Follow the assignments link on the left nav.
  2. Click on the Submit button.
  3. Choose your completed file for Output Submission only!
  4. Wait. It can take a while for the homework to be processed, but when it’s done, the score will be available on the assignments page.
  5. Check on your score. If you didn’t get 100%, click on your score to see details.
  6. Repeat Steps 1-5 until you have 100% on all parts

Final Help

After you submit an assignment, you’ll see the grading criteria. However, since it’s not listed anywhere else, I’ve compiled all of them here:

Part1 = %"
#palindrome?
  recognizes palindromes correctly [25 points]
  recognizes non palindromes correctly [25 points]
 
#count_words
  counts the words properly [40 points]
  is not sensitive to case [10 points]
"
 
Part2 = %"
rps_game_winner
  should raise WrongNumberOfPlayersError if there are not exactly two players [1 point]
  should raise NoSuchStrategyError if there is some strategy that is not R, P, or S [4 points]
  should return the correct winner in a simple RPS game with a clear winner [15 points]
  should return the first player in the case of a tie [10 points]
 
rps_tournament_winner
  should still be able to handle the case where a tournament is just one game [10 points]
  should pass the example given in the homework of an 8-player tournament [5 points]
  should pass a basic test case of 8 players [15 points]
  should return the correct winner in the cases of 16 and 32-man tournaments [40 points]
"
 
Part3 = %"
anagrams
  should handle an empty array [2 points]
  should handle the most simple, single-character case with no repeats [2 points]
  should handle the most simple, single-character case with capital letters but no repeats [2 points]
  should handle a set with no repeated anagrams and words with distinct letters [10 points]
  should handle a set with no repeated anagrams, but words with similar letters [2 points]
  should handle non-anagrams that have all but one letters the same [2 points]
  should handle a complicated case of some repeated anagrams, but no duplicates [25 points]
  should handle a complicated case of some repeated anagrams, but no duplicates [25 points]
  should handle a simple case of some repeated single-character inputs [2 points]
  should handle a complicated case of some repeated anagrams, with duplicate inputs [7 points]
  should handle a complicated case of some repeated anagrams, with duplicate inputs [7 points]
  should treat single-character capital letters as equal [2 points]
  should handle repeated single-character inputs, and treat captial letters as anagrams, while preserving case in the output [2 points]
  should treat two identical words with different cases as the same, and preserve case in output [2 points]
  should treat many identical words with different cases as the same, and preserve case in output [8 points]
"
 
Part4 = %"
dessert
  should be able to set and get a dessert's name and calories [20 points]
  should return true if a dessert has fewer than 200 calories [10 points]
  should return true for any dessert [20 points]
 
jellybean
  should be a subclass of Dessert [10 points]
  should be able to set and get a jellybean's flavor [20 points]
  should return true unless the flavor is black licorice [20 points]
"
 
Part5 = %"
single attr_accessor_with_history
  should return nil as the first element [6 points]
  should record all past values of the variable, and be able to record for multiple instances [9 points]
  should record all past values of the variable, and be able to record for multiple variables [15 points]
 
multiple attr_accessor_with_history
  should return nil as the first element [14 points]
  should record all past values of the variable, and be able to record for multiple instances [21 points]
  should record all past values of the variable, and be able to record for multiple variables [35 points]
"
Posted in Online Learning | Tagged , , , | 1 Comment

Udacity CS373 – Unit 2 – The Monkey Coconut Problem

Thrun presented a bonus question at the beginning of Unit 2 about dividing piles of coconuts and uneven remainders. It goes like this:

Five men and a monkey were shipwrecked on a desert island, and they spent the first day day gathering coconuts for food. Piled them all up together and then went to sleep for the night.

But when they were all asleep one man woke up, and he thought there might be a row about dividing the coconuts in the morning, so he decided to take his share. So he divided the coconuts into five piles. He had one coconut left over, and gave it to the monkey, and he hid his pile and put the rest back together.

By and by, the next man woke up and did the same thing. And he had one left over and he gave it to the monkey. And all five of the men did the same thing, one after the other; each one taking the fifth of the coconuts in the pile when he woke up, and each one having one left over for the monkey. And in the morning they divided what coconuts were left. After dividing the coconuts into five equal shares, they again have one coconut left over, which they gave to the monkey. Of course each one must have known that there were coconuts missing; but each one was guilty as the others, so they didn’t say anything. How many coconuts there were in the beginning?

I sat down with my pen and solved this the long way by hand, like my old physics problems when I was in school. The answer I can up with was 56-4. This left me very unsatisfied, I know that I solved it, but I knew it was the long way, and that to me was the wrong way.

I had a professor in college for graduate level courses (e&m and mathematical physics). Every week, we would have a new proof to complete. He would remind throughout the course, that every one of his assignments could be solved the short way or the long way. You could solve it in several pages of messy algebra. Or, you could solve in half a page with an elegant proof. He would only give full credit for the half page elegant proof.

I only gave myself partial credit on this coconut problem.

Thrun’s explanation didn’t really satisfy me, but then I saw Mercher’s intuitive explanation on reddit. And it finally clicked. Here is my explanation of his intuitive solution:

As Thrun explained, -4 is a possible answer, but we need a positive solution, so let’s go about finding one.

  1. Start with N+4 coconuts.
  2. Split the coconuts into two piles: -4 & N
  3. Then, each step do the following:
    • From the pile of -4, do the process of take 1, multiply by 4/5. (You can do this forever.)
    • From the pile of N, just multiply by 4/5
  4. Repeat step 3 five times.
  5. You now have one pile of -4 coconuts, and one pile of N*46/56 coconuts. From this, it is clear that N must be a multiple of 56 . The smallest such number being…56.

=> The original pile of of N-4 coconuts == 56 - 4

Now that’s a half-page, full-credit solution.

Posted in Math, Online Learning | Tagged , , , | Leave a comment

Udacity CS101 & CS373 – HW1 Review

Week 1 is over, the results for the homework are available. I like the new progress section, it looks great. There are a couple of feature requests I would have would be:

  1. Result summary in the sidebar to let me see all my results at a glance
  2. Ability to see the question and explanations right from within the progress section so that I can more easily hop around between questions.

However, overall I am very impressed in the quality of the site. This site was put together in just a couple of months, and the user experience is fantastic. Meanwhile, I was just paying bills on the Bank of America site, and the experience was awful. I’m very disappointed in a site that has surely had several millions of dollars invested in it. Please, can every you just automatically fill in CA when I’ve typed in Santa Monica 90404?

Now, for a quick review of the questions:

UDACITY – CS101

I saw someone with this question on reddit, so just in case you didn’t know the Udacity questions all have explanation videos. From the question, just click the next button.

These questions are most pretty straight forward even for those who don’t have any programming experience. The quizes after the lectures were more tricky than the homework problems. However, I wouldn’t blame anyone getting a few questions wrong due. It could be tricky everyone has time to fully listen to all of the lectures, or verify their work. I will nevertheless address a few of the questions:

  • Q5. This is the question asking which expression involving s would have the same value of s. This was a little tricky since almost all of the expressions were the same as s, and the remaining was equal to s in all but the trivial case of s == ”, and then only because (”)[0] throws an error (or in python speak raises an error).
  • Q8. Print out the index of the second occurrence of the string ‘zip’. Most programmers’ first instinct was probably to use an if statement checking if the first find was successful. if firstIndex > -1: text.find(‘zip’,firstIndex + 1) else: return -1. However, this is CS101, and you haven’t learned the if statement yet. Oops. But, then you realize if text.find(‘zip’) returned -1, then so would text.find(‘zip’, 0), and so you found your solution: text.find(‘zip’, text.find(‘zip’) + 1)
  • Q9. This was rated two gold stars because of the difficulty, and it did take some thought. I had even written the solution using the if statement. But, then I remembered some post I had read on performance and how many of the as3 Math functions were slow. This person’s fast round solution was to add 0.5 and cast as int. So, there was my answer. I’m not sure if I would have thought of the answer if not for that distant memory.

UDACITY – CS373 – HW 1

First, I’d just like to say how happy I am that there is actual programming in this class. The programming assignments were the single greatest factor that made Ng’s machine learning class so much better than Norvig and Thrun’s Intro to AI class. Now, the playing field is evened.

  • Q1. Just very straight forward probability here. People might get sloppy or misread something and get part of this wrong, but I don’t see it as worthy of any additional explanation
  • Q2. How does memory scale in the number of variables? A. exponentially. I’m embarrassed to say that I got this one wrong. Not quite understanding what was being asked, I just sort of guessed that the memory would scale linearly. However, if I had actually listened to the question I would have heard Thrun say, “… memory scale… for our histogram based localization method” From that phrase, I could have worked out that in 1 variables you have n buckets. For 2 variables, you have m divisions for the first variable and m for the second variable, so m2 buckets. For 3 variables m divisions for each variable so m3 buckets… for n variables you need mn buckets. In other words, the number of buckets scales exponentially with the number of variables. Thrun gave a good explanation in response video. I recommend taking a look at it if you are unfamiliar with big O notation.
  • Q3. A Bayes rule question. This question was a matter of applying the formula and plugging in the values. It sound easier than it is. It’s easy to miss a step or plug in the wrong value. For those that got this question wrong, my recommendation is to redo all of the quiz questions on Bayes and listen to Thrun’s explanations. It should be just a matter of straight forward algebra once you understand how to find the correct values.
  • Q4. My favorite question by far. It really allowed me to practice my python and achieve some comfort in the standard language constructs. (I’m using far fewer semi-colons.) I did get this marked correct, but I like Thrun’s solution more. It is far more elegant and pythony. I’ll need to gain more familiarity with the syntactic sugar of python, for example aux = [[0 for row in p[0]] for col in p].
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
def sense(p, Z):
    q = []
    for i in range(m):
        q.append([])
        for j in range(n):
            factor = sensor_right
 
            if colors[i][j] != Z:
                factor = 1. - sensor_right
 
            q[i].append(p[i][j]*factor)
 
    q_sum = 0.
    for row in q:
        q_sum += sum(row)
 
    #normalize
    for i in range(m):
        for j in range(n):
            q[i][j] = q[i][j]/q_sum
 
    return q    
 
 
def move(p, motion):
    q = []
    for i in range(m):
        q.append([])
        for j in range(n):
            failed_to_move = p[i][j] * (1. - p_move)
            moved = p[(i - motion[0]) % m][(j - motion[1]) % n] * p_move
 
            q[i].append(failed_to_move + moved)
 
    return q
 
p = []
 
m = len(colors)
n = len(colors[0])
 
uniform_p = 1./float(m*n)
 
for row in colors:
    p_row = []
    p.append(p_row)
    for cell in row:
        p_row.append(uniform_p)
 
for i in range(len(motions)):
    p = move(p, motions[i])
    p = sense(p, measurements[i])

Conclusion

Awesome, great job. I would say I’m looking forward to Unit 2, but I’ve already completed the lectures. So, here’s to Unit 3!

Note: There was also one new strange thing that happened. The time scrubber on the videos stopped showing where I was in the video. I’m not sure if this is an Udacity bug, or a youtube bug, or something with the browser, but it is very strange.

Posted in Machine Learning, Online Learning | Tagged , , , , , | Leave a comment

Udacity CS373 – Homework 1.4: Part I

I have just been playing with this localization demo that pomber made in javascript here. It’s a little snowman that you move around with the arrow keys.

I was watching the probabilities move around; sometimes the snowman would be highly localized, but an incorrect reading or a missed move would delocalize the snowman again. And, then there were situations like the one below–where the only move to improve localization is a move to the right.

In fact, the situation could be even worse. From the above position, move right, then you will have no available moves to improve your localization. Move up or down, and you are guaranteed to see a dark color. Try to move left, and again you will definitely see a dark color. Every cell in that column is equally likely, with some additional chance that the move failed. Try to move right, and you will see a light color, again every cell in the column being equally likely. Any failure to move only worsens the situation adding more uncertainty to the localization.

Making a Game

All of this playing around got me to thinking, why not turn it into a game? Instead of showing where the snowman is, we can hide it. The object of the game could then be to move around until you know where you are and then make a guess.

Step 1: Remove the Snowman

The author of the demo, pomber, was kind enough to provide the source code so the first part was easy enough. On line 85, the robot char was set “☃”, so we just change that to “”:

85
var robotSymbol = "☃";

->

85
var robotSymbol = "";

Step 2: Guess the Cell

For the next step, we’ll want to add some handlers so that we can guess which cell we are actually on. Again, this is pretty easy because pomber has done a nice job creating clean, readable code. The boards are both labelled with a class of “board”, so I can easily add a listener to the click event of the enclosed td tags.

158
159
160
161
162
163
164
165
166
$(".board td").click(function (e) {
 
    var position = e.target.id.substr(2).split('-');
 
    var row = position[0];
    var col = position[1];
 
    guess(row, col);
});

My guess function will just contain some simple code alerting if the clicked cell matches the currentRow and currentCol.

202
203
204
205
206
207
208
function guess(row, col) {
    if (row == currentRow && col == currentCol) {
        alert('Correct');
    } else {
        alert('Incorrect');
    }
}

That’s mostly it. Some very simple changes, and we’ve made a simple game. However, I’m not done there. I’d like to add some additional features such as scoring, a leaderboard, and a way to make new games.

Step 3: Scoring

Any real game has high scores. A simple way to get points can be to track of the number of steps, how much time, and how many guesses were needed to find the robot. Let’s put all of that together.

First let’s add all of the necessary variables and util/helper functions. We need the movesLeft, livesLeft, and startTime vars.

3
4
5
6
7
8
var movesLeft = null;
var livesLeft = null;
var startTime = null;
 
var allowedMoves = 3;
var allowedLives = 3;

Set all of the defaults in the initializeWorld() function.

156
157
158
159
function initializeWorld() {
    livesLeft = allowedLives;
    movesLeft = allowedMoves;
    startTime = null;

Some util functions to help with calculating scores:

230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
function getLifeBonus() {
    return livesLeft * 100;
}
 
function getTimeBonus() {
    return Math.round(
        Math.max(
            0,
            300 - ((new Date()).getTime() - startTime) / 50
        )
    );
}
 
function getMoveBonus() {
    return Math.max(0, movesLeft * 25);
}

Add a place to show the current score:

15
16
<div id="result">
</div>

Update the movesLeft and livesLeft vars in the move and guess functions. Then, when the robot has been found, total up the scores, display them in the result div.

191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
function move(rowDelta, colDelta) {
    if (startTime == null) {
        startTime = (new Date()).getTime();
    }
    movesLeft--;
 
    moveRobot(rowDelta, colDelta);
    drawRobot();
    moveBelief(rowDelta, colDelta);
    drawBelief();
 
    if (autoSense) {
        sense();
    }
}
 
function guess(row, col) {
    if (row == currentRow && col == currentCol) {
        var timeBonus = getTimeBonus();
        var moveBonus = getMoveBonus();
        var lifeBonus = getLifeBonus();
        var totalScore = 100 + timeBonus + moveBonus + lifeBonus;
 
        $("#result").append(
            '<b>You got it!</b>' + 
            '<br/>Completion: 100 pts' + 
            '<br/>Time Bonus: ' + timeBonus + ' pts' +
            '<br/>Move Bonus: ' + moveBonus + ' pts' + 
            '<br/>Life Bonus: ' + lifeBonus + ' pts' +
            '<br/><b>Total: ' + totalScore + ' pts</b>'
        );
 
 
    } else {
        livesLeft--;
 
        if (livesLeft == 0) {
            $("#result").append(
                '<b>Game Over!</b>' + 
                '<br/>Try Again\n'
            );
 
        } else {
            alert(
                'Incorrect!\n' + 
                'Try Again\n' + 
                livesLeft + ' Lives Left'
            );
        }
    }
}

For some better formatting of the results, we’ll use a monospace font:

1
2
3
* {
  font-family: monospace;
}

Step 4: Replaying

The next enhancment will be a New Game button so we can play again without having to reload the page. First add in the button and a listener for it that will reinitialize the boards.

1
<button id="newgame">New Game</button>
191
192
193
$("#newgame").click(function(e) {
    initializeWorld();
});

However, that’s not enough because the initializeWorld function doesn’t clear the existing board before adding a new one:

We need a clearBoard function to start new games and a

91
92
93
function clearBoards() {
    $(".board").empty();
}
160
161
162
163
function initializeWorld() {    
    clearBoards();
    ...
}

Almost done, but the listeners on the $(“.board td”).click were disappearing on clearBoards()., I moved the handlers inside of initializeWorld() and everything worked like a charm.

Step 5: The Leaderboard

Add the leaderboard list and submit to leaderboard form. The form starts out as hidden and is only shown when a game is won.

25
26
27
28
29
30
31
32
33
34
35
<div id="leaderboard">
    <b>Leaderboard</b>
    <ul>
    </ul>
</div>
 
<form id="frmLeaderboard" style="display:none;">
    <label for="name" id="name_label">Name</label>  
    <input type="text" name="name" id="name" size="25" value="" class="text-input" />
    <button id="btnLeaderboard">Submit to Leaderboard</button>
</form>

First some cleanup on the guess function, moving the win/lose handling into their own functions. Then, showing the leader board form when winning a game.

95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
function guess(row, col) {
    if (row == currentRow && col == currentCol) {
        won();
    } else {
        livesLeft--;
 
        if (livesLeft == 0) {
            lost();
        } else {
            alert(
                'Incorrect!\n' + 
                'Try Again\n' + 
                livesLeft + ' Lives Left'
            );
        }
    }
}
 
function won() {
    var timeBonus = getTimeBonus();
    var moveBonus = getMoveBonus();
    var lifeBonus = getLifeBonus();
    totalScore = 100 + timeBonus + moveBonus + lifeBonus;
 
    $("#result").empty();
    $("#result").append(
        '<b>You got it!</b>' + 
        '<br/>Completion: 100 pts' + 
        '<br/>Time Bonus: ' + timeBonus + ' pts' +
        '<br/>Move Bonus: ' + moveBonus + ' pts' + 
        '<br/>Life Bonus: ' + lifeBonus + ' pts' +
        '<br/><b>Total: ' + totalScore + ' pts</b>'
    );
 
    //Show leadderboard form
    $("#frmLeaderboard").show();
 
}
 
function lost() {
    $("#result").empty();
    $("#result").append(
        '<b>Game Over!</b>' + 
        '<br/>Try Again\n'
    );
}

Add the click function to the submit button which adds the score to the leader board, clears the current, and rehides the form.

95
96
97
98
99
100
101
102
103
104
105
106
107
108
$("#btnLeaderboard").click(function(e) {
 
    var liNode = $("<li>");
 
    liNode.append(
        '<b>' + totalScore + 
        ' ' + $("#name").val() + '</b>'
    );
 
    $('#leaderboard ul').append(liNode);
    $("#frmLeaderboard").hide();
    $("#result").empty();
    return false;
});

Step 6: Finishing Touches

I also thought it would be nice to show the robot when finishing a game, successfully or unsuccessully. This was easily done by making a showRobot() and calling it in won() and lost() functions.

95
96
97
98
99
function showRobot() {
    robotSymbol = "☃";
    drawRobot();
    robotSymbol = "";    
}

Final Product

link: http://jsfiddle.net/u9xj6/embedded/result/

There are some pretty obvious bugs. Some ui/design work could certainly benefit the leaderboard/result section. The code could also use some clean up. Plus, some additional enhancements would also be easy, such as a larger board, adjustable parameters, or a third cell color. There would definitely be some interesting result from that, I have already tested out the board with higher sensor fail and movement stall rates and it became much more difficult to locate the robot. Another big win would be recalculating the probabilities on a miss, since we know that the guessed location definitely does not have the would also be a big win. However overall, I am quite happy with the results. We have a nice little localization game. It’s been a good test for me as well since I’ve never worked with jQuery before and rarely work with javascript anymore either. If anyone takes this project further, I’d like to hear about it, so let me know in the comments.

Part II

You may have noticed that this post is labelled Part I, meaning there is a part II. For part II, I’ll be moving back toward the focus of the class, machine learning. For part II, we will be looking at building an algorithm that will choose the best movements so that the machine will be able to localize itself in as few steps as possible. I’m most of the way through the first half of the algorithm. Now comes the difficult part.

Until next time.

Posted in Data Analysis, Data Visualization, Machine Learning, Online Learning | Tagged , , , , | 1 Comment

Udacity and Coursera – Week 1

I’ve just started taking four of the new batch of online classes being offered. Udacity’s CS101 and CS373 as well as Coursera’s Model Thinking and Software Engineering for Software as a Service which have also just gotten started as well. In my previous post, I compared the Coursera and Udacity platforms. In this post, I’ll address the classes themselves.

UDACITY – CS101: BUILDING A SEARCH ENGINE

CS101 is an intro level computer science course taught by David Evans, a Professor of Computer Science at the University of Virginia. The material requires no programming experience at all. I am clearly not the audience for the course. Despite that, I have decided to take the course, though solely for the contest at the class’s end. Because most of the material is so elementary, I’m skipping through most the lectures and just completing the quiz and homework questions. It’s good practice to get my Python syntax more comfortable. Some of the questions even a little challenging requiring some genuine thought and understanding. For example, recognizing that (”)[0] will cause a run-time error in python.

As of now there isn’t much more to say, but I’ll update with more information as the level goes up in future weeks.

UDACITY – CS373: PROGRAMMING A ROBOTIC CAR

Sebastian Thrun is teaching this course on how to program a robotic car. This is clearly a topic that excites Thrun, and not just because of his involvement with projects such as Stanford Racing Team’s car, Stanley and Google’s self driving car. Thrun’s excitement for this topic comes across clearly in his lectures and makes the whole process interesting for the student as well.

This first unit was titled the Basics of probability: Car localization with particle filters, so as you can imagine the material covered was almost identical to material covered in Thrun and Peter Norvig‘s Introduction to Artificial Intelligence except for one notable exception: the addition of actual programming exercises. And this made all of the difference. I felt like I had a pretty good understanding of particle filters and Bayesian probabilities after taking ai-class and ml-class in the fall. However, applying my knowledge in a programming exercise pushed my understanding further. I’m also happy that the exercises are using Python as I’ve been interested in learning it for quite a while. It’s good practice getting comfortable with the syntax, though I keep pumping out code that looks like this:

15
16
for (row in p)
    q.append(row);

Notice the missing : and added ;

I’m looking forward to the rest of this course. Sebastian Thrun, Thank you for leaving Stanford and starting Udacity.

COURSERA – MODEL THINKING

Scott E Page is teaching this class. He’s also a professor at University of Michigan. So far, his explanations are clear and illuminating. It’s still early in the class, and there haven’t been any assignments, but already you can tell that he really cares about this subject and has put a strong effort building a well organized course with a clear plan and direction. The videos are 8-15min each, and they are each well organized around a single topic. There is also additional reading material given in the syllabus that I have yet to look at. I’ll review that later. The course seems to be directed at humanities. Page must be in high demand at Michigan.

So far there have been four units. In the introductory unit he presented some interesting evidence in favor of using models to help make decisions. For those not following along with the course. It boiled down to: people who use models make better decisions than people who don’t, people who use many models do better than people who use only one model, formal models do better than people, and using lots of formal models does better than a single formal model. Page then gave a bunch of example of models used in the real world. My favorites were determining the authorship of the Federalist Papers and the much cited Monty Hall Problem.

The second unit discussed Segregation and Peer Effects. Again Page presents a number of simple examples highlighting surprising results that result from simple models. The one example that stood out was a very simple model, Schelling’s segregation model, which showed how a city could become highly segregated with only a small preference for similar neighbors. While listening to this lecture, I thought of the possible way that the simplifications of model could be distorting the results and of some ways we could expand the model to investigate alternate scenarios. I guess you could say I was Model Thinking.

The third unit is called Aggregation. The two standout example from this? Conway’s Game of Life and Stephen Wolfram’s A New Kind of Science. Both are worth a look or review if you’re already familiar with them. The main theme of this section was how complex behavior can come out of an initial set of simple rules.

Unit 4 on Decision Models covered ground that anyone familiar with Machine Learning would have already learned more in depth. Though it can always be helpful to hear a topic again from a different perspective. For example, here is a poignant quote that came out of this section, ”We don’t want the models to tell us what to do. We want the models to help us make better choices.”

Scott E Page, so far so good. Though, one thing that I noticed, your talking speed fluctuates. It is only an issue at 1.5X when some of your speech becomes too fast to understand.

COURSERA – SOFTWARE ENGINEERING FOR SOFTWARE AS A SERVICE

The Coursera Saas course is being co-taught by UC Berkeley Professors Armando Fox and David Patterson. The first two sections have been mostly a 10,000 foot view of the very basics of software engineering processes (waterfall, agile, …) and SaaS. There was plenty of talk about tcp/ip, dns, 127.0.0.1. A lot of web 2.0 buzz words. 76 PowerPoint slides. For someone who has worked in a number of companies included strict SRUM Agile, Waterfall, and agile with a lowercase “a”, this has been pretty basic and dry material.

However, I am really looking forward to the assignments in this course, perhaps more so than any of the other courses. The excitement mostly comes from this sentence in the Overview, “Those [sic] submit homework 1 and receive a passing grade will receive a coupon good for 100 hours of small instances of EC2 for use on the remaining homework assignments plus a coupon to upgrade their free GitHub accounts to a Micro account (both good through the end of course).” Ruby on Rails, GitHub, Amazon Web Services EC2 and S3, … I’ve always wanted to be a hipsterhacker.

Seriously though, this class has some potential to be very interesting, for now I’m withholding judgment.

CONCLUSION

That concludes Week 1 in my online learning review. I plan on posting regular updates on the courses and my engagement with them. This whole online learning phenomenon has really taken off in ways that we only dreamed of a few years ago. In closing I just want to thank Khan Academy. They were the first online learning site to really take off. Salman Khan, the founder, finally found the winning recipe, and he deserves much of the credit for kick starting this phenomenon. Before Khan Academy, the state of the art in online learning was MIT’s Open Courseware.

Thank you Salman Khan.

Posted in Data Analysis, Machine Learning, Online Learning | Tagged , , , , , , , , , , , | Leave a comment

Udacity vs Coursera

I’ve seen another live blog on for the Udacity courses on Journal of a Quant by Ilya.

Later this week I’ll be talking about Udacity’s CS101 and CS 373 as well as Coursera’s Model Thinking and Software Engineering for Software as a Servic which have also just gotten started as well. However for this post, I’ve decided to just focus on the course platforms themselves, Coursera and Udacity.

COURSERA

Coursera got it’s start in the fall with ml-class and db-class as Stanford’s Online Learning Initiative. Then, in January it got rebranded as Daphne Koller and Andrew Ng are launching it as its own company. It’s unclear what if any affiliation coursera will maintain with Stanford.

The coursera platform was already pretty solid in the Fall. I never experienced any of the network issues with ml-class that ai-class had every week. Coursera also has some very nice features. I particularly like the ability to play the videos at 1.2X or 1.5X normal speed. The quizzes embeded in the video are very helpful. I’m pretty familiar with most of the material that is being covered, so I will often listen to the lectures in background at 1.2X or 1.5X while completing some other task–such as writing this blog post. When the lecture is stopped with a quiz, I am able to gauge my understanding. If one of the questions takes me by surprise, I know to re-watch the last few minutes. I assume that the Coursera professors are also looking at the quiz/speed/re-watching data to better understand how the students are understanding and digesting the material.

Since the fall classes, coursera has definitely improved. The interface is a bit slicker. The design is a little more professional. There is now an indicator next to the lecture if you have attempted the in lecture quiz. There is also a little hint “Press ? for keyboard shortcuts”. Doing so gives you a list convenient, if largely unecessary shortcuts:

Keyboard Controls
  • ?: Show / hide shortcuts
  • P: Play/Pause
  • Up: Increase volume
  • Down: Decrease volume
  • Left: Rewind
  • Right: Fast forward
  • F: Toggle fullscreen
  • C: Toggle captions
  • Esc: Close video

I don’t think that captions had been available in the previous version of Coursera. Howerver, they don’t seem to work that well from my limited look at them. Though that doesn’t bother me as I don’t use captions anyway.

However, the most appreciable improvement? After answering a question you are given a option to see an explanation. I think that is pretty valuable. If I really understand a topic, maybe I don’t want to see an explanation. However even if I got a question correct, I might want to see an explanation on why that answer was correct.

Coursera has definitely improved. My complaints with the new system? There are three small complaints which I think are actually regressions since the first version.

  1. The lengths of the video are posted next to the name in the list. I distinctly remember ml-class having all of the video lengths posted. I also remember them being mostly ~5min. The new courses have runtimes mostly >10min. I preferred the 5min videos.
  2. Settings aren’t remembered from one video to another. I start watching a video. I adjust my volume down to ~25% and set my speed to 1.5X. When I finish that video and click Next, I expect that the next video will keep those settings. However, every time the speed resets to 1X , and more annoyingly, the volume jumps back up to 100%. I am split on whether the settings should be kept from one session to another. However, I definitely feel that if I have just adjusted my volume down, the system should definitely remember that for the next video.
  3. Progress isn’t tracked properly. The original Coursera showed a green checkmark next to any lecture I had already watched. There were some other features around course progress which look to have all disappeared. I think that this is a relatively recent feature loss because I thought that the preview videos for Model Thinking actually had the progress checkmarks. Correction: I refreshed the page and the checkmarks appeared next to the videos that I had seen. The bug isn’t that progress isn’t tracked, it’s that progress isn’t updated until you refresh the page. Not a very big problem at all. However, now that I’ve seen how the progress system works there are some enhancements that I would love.
I expect that both of these issues will be fixed pretty soon. So when you log in and have settings and progress remembered, don’t blame me.
The enhancements to the progress tracking that I’d love to see:
  1. A way to mark videos as watched without actually opening it up to watch. There are other ways to watch the video than through the Coursera player, but only watching through the player will update the progress.
  2. A way to unmark a video as watched. There were times that I wanted to re-watch a video from ml-class to review the information or because I hadn’t been paying 100% attention the first time. A way to remove progress would have been great.
  3. Remember where in the video I stopped watching. Currently the system marks a video as watched after only watching a portion of it. Now the videos are generally short, so I should be able to watch them in a single sitting. However, there are definitely times that I have started a video and closed the browser, then reopened, forgetting that I hadn’t actually finished the video. To be fair, this is pretty nitpicky. The only site I have ever seen implement a feature like this with any sort of consistency has been Netflix.

UDACITY

Udacity is a good improvement over Know Labs’ freshman effort with Artificial Intelligence. The design has also been spruced up to my liking. The best part was the addition of actual programming exercises. Here come my list of things that I would love to see improved:

  1. The only way to get to the forum is first by clicking the Announcements and then clicking on the forum link. I’m looking forward to the day that the Discussion link is activated.
  2. My Udacity login doesn’t work in the forum. I would have hoped they would have had an integrated login.
  3. The first video starts playing every time you enter Course Content. It was nice the first time, but now it’s just getting in the way.
  4. Homework answers aren’t saved properly. My programming answers for the homework are saved nicely, however when I go back to review my answers to the other questions, I find the text inputs are empty.
  5. The questions don’t automatically come up when the video ends. It wasn’t wholly intuitive that I should click the NEXT button to get to the question. This is actually a regression, as it worked for ai-class.

The list of improvements above are really just nitpicks. Also, I am sure many improvements are coming soon. They have already fixed some issues such as an indication of which video is currently in progress which Ilya from Journal of a Quant also mentioned.

 

Posted in Data Analysis, Machine Learning, Online Learning | Tagged , , , , , , , , | Leave a comment

Next Steps After ai-class & ml-class

Early last fall, I read about a course on artificial intelligence that Sebastian Thrun and Peter Norvig were teaching online (from nytimes.com), ai-class. Thrun and Norvig are two of the top names in AI today. If you haven’t heard of them, Thrun is behind Google’s driverless car, and I’d first heard of Norvig from reading his very excellent post How to Write a Spelling Corrector. Norvig is also one of the early Google employees who helped with their translation and search optimization.

I have been interested in big data and statistics for a while, and just last spring and summer I had just been doing some side work developing a prototype system for optimizing websites. The long run goal is to use AI to determine which variations will most improve the site. I had been doing research on various techniques that would be most useful. The methods that I had been researching were random forests, decision trees, and artificial neural networks. As I was learning more about these techniques, a huge field of potential applications opened up before me. That’s right when I saw the announcement for Norvig and Thrun’s Introduction to Artificial Intelligence. So, I put the optimization project and my self learning on hold and signed up for their course. Then, I also heard of two other courses also being taught by Stanford professors. One was db-class and the other was ml-class taught by Andrew Ng. (You may have seen videos of the autonomous helicopters for which Ng is known.) There were some potential applications for topics in the machine learning class, so I signed up for that one as well. The intention was to start with the two courses, but then just stick with the more interesting one, dropping to the basic track for the other just to follow the lectures. However, both Thrun and Norvig’s ai-class and Ng’s ml-class were so engaging, that I kept up with both in the advanced track. Below are my brief impressions of the class after some reflection.

AI-CLASS

Introduction to Artificial Intelligence offered a nice introduction to the field of artificial intelligence. The topics were pretty elementary and didn’t require any previous knowledge. Some units were better than others. I generally enjoyed Thrun’s lectures more than Norvig’s. I found his lectures more clear and his lecturing style more filled with energy and excitement which helped to transmit the same feeling to me. Overall, I give the class a solid B as a result of some of the problems:

  • The site went down almost every week when the homeworks were being submitted/grades being checked
  • The site forums never went live, instead we used reddit/r/aiclass and aiqus.com, which became the official forum
  • Some questions each week were vague (Though the complaints on the forums make them sound worse than they actually were)
  • Not as challenging as I would have liked

ML-CLASS

I can’t say enough about how great this class was. Ng is an excellent lecturer with a fantastic ability at explaining difficult concepts. Having actual programming assignments really helped to solidify my understand of the new concepts. The level of this class was difficult enough to be challenging, but light enough that I was able to complete all of the exercises without impacting my family and work life too much. Though, as a warning to others, I have had previous experience with MatLab, both in University and last summer I was porting some MatLab code to ActionScript. Without that experience, I may not have had time to keep up with this course. However, that being said MatLab/Octave is a great language for this topic as it simplifies much of the code needed to complete the assignments.

In summary, ml-class had none of the technical issues of ai-class, and some additional added benefits:

  • You could watch the more elementary material at 1.25X or 1.5X
  • There were actual coding exercises
  • The material was the right level of challenge for me.
  • Ng was such a good lecturer who made difficult material easy to understand

Ng’s ml-class is being offered again this semester. He made me want to go back to school, but only at Stanford and only if I could get Ng as an adviser. Therefore, I highly recommend it for anyone interested in the subject. I also found a great video of a presentation he gave about Machine Learning to the Bay Area Vision Meeting. Machine learning is an exciting field right now. My only wish would have been to also be assigned a final project: See the CS229 Final Project Page.

NEXT STEPS

I wasn’t the only one who took these classes. Tens of thousands of students worldwide started, and finished, each course. After this immense success, Coursera, the the platform for ml-class, listed a dozen more classes that would be offered in the Spring. Most of their classes have been delayed due to legal issues. I think that Stanford is having second thoughts now that their economic model is being threatened. It also inspired two other new platforms for offering free, online university level classes:

  1. MITx from open courseware pioneer MIT is offering one class: Circuits and Electronics 6.002x
  2. Udacity from ai-class’s Thrun is offering two courses CS101 and CS373

In December, I signed up for a few of the Coursera classes, and in January I signed up for CS373 from Udacity. I was going to stop there, but then I saw this video about CS101. They’re having a contest at the end of the class, and even though I may not be the target audience, I couldn’t resist. Plus, it shouldn’t take much time as I’m already a proficient programmer familiar with python.

This time, I have decided to post weekly updates on the classes as they progress. I hope that you enjoy.

Posted in Data Analysis, Machine Learning, Online Learning | Tagged , , , , , , , , | Leave a comment