Monthly Archives: May 2013

Review: CS107: C++ Programming — Saylor Foundation

Leave a reply

There are a few MOOCs I’m interested in taking that are taught using C++. I’m not overly familiar with this language, which was motivation enough for me to go through the third course in Saylor’s Computer Science curriculum, CS107: C++ Programming. That course promises a thorough introduction to C++ programming. It is not a course for beginners, though. You are expected to have a basic familiarity with programming, including object-orientation.

CS107 has been my third course on Saylor, and so far this is the course that best illustrates the viability of their approach to teaching. Yes, all the material they use is freely available elsewhere. However, by curating content and offering a syllabus, Saylor provides a helpful structure for self-learners. This makes it easy to follow along, and greatly increases the value of the original sources. For instance, Google’s C++ class is too dense and fast-paced for anyone who isn’t an experienced programmer already, and Keith Schwartz’s Stanford hand-outs might not be overly useful without the accompanying lectures, which are missing. An older version of Stanford’s CS106B is available online, though. Further, the tutorial on cplusplus.com provides very little hand-holding, with very few examples and no exercises at all. Saylor solves all those problems by combining those and other resources.

I would recommend that you get a book to complement the material. While I do think that CS107 is a perfectly adequate university-level course, it can be quite convenient to be able to quickly look-up topics in just one place, instead of having to go through various links and sites. There are a few free sources available. I’ve used Allen B. Downey’s How To Think Like a Computer Scientist: C++ Version. It has served me well as a concise reference, even though it won’t help you much in the second half of the course, which explores more advanced topics such as templates, preprocessor directives or manual memory management. Speaking of supplementary books, Eric Roberts offers a draft of Data Abstractions in C++ free of charge. It is quite verbose, but the book looked good to me. You might appreciate the many exercises it offers.

The final exam was quite satisfying, apart from some minor issues. The majority of questions were of a practical nature, which I find laudable. The most common question type was based on tracing the execution of a program and choosing the correct output from a number of alternatives. Other questions covered language details which, for the most part, were perfectly reasonable. I found just two of the 50 questions hard to justify. One asked to evaluate a statement of the form “x = (y = 10, y + 1)”. This is syntactically legal, and does evaluate to an integer, provided both x and y have previously been declared. However, I couldn’t think of a case where you would want to write code like that. Some other question presented you with a program that reads in a file consisting of a short sequence of characters as binary, and print the content character by character as hexadecimal values. I would have been fine with a short program or a question that tests whether you can manually convert from one number system to another, but seeing instructions that say, “(Hint: you should compile the code to figure it out.)” caught me off guard, and not just because I was doing this exam on a computer on which I didn’t have any software development tools installed.

What I disliked, though, was that all code fragments were presented as unformatted code. It is quite startling how difficult it can be to read code that wasn’t properly indented. Saylor should fix this issue, and it should be a relatively easy fix too. Despite the few minor flaws, though, I think that CS107 is a solid course. It won’t turn you into a master C++ programmer, but afterwards you should know enough C++ to go through more advanced CS courses that are taught in this language.

[EDIT: On 17 June I received an email from Tanner Huggins, Content Development Associate at Saylor Foundation. He let me know that they’ve fixed the formatting issues with the exam I had pointed out.]

Finding an Eulerian Path

1 Reply

In Udacity’s Introduction to Algorithms course, one of the challenge problems asks you to define a function that, given a graph that contains an Eulerian path, returns one such path. I’ve reproduced my solution below. The solutions posted on the Udacity forum where often in two camps: somewhat verbose imperative, and very concise functional ones that implemented Hierholzer’s algorithm for finding cycles in Eulerian paths. My solution is somewhat in the middle. It’s relatively concise, but it makes use of an additional data structure I found helpful as it allows to easily inspect the state during program execution: a list containing the number of unused edges per node. I think it’s quite easy to follow the flow of execution, but I’ll walk you through step by step afterwards.

Here is the program listing:

def find_eulerian_tour(graph):
            
    def freqencies():
        my_list = [x for (x, y) in graph]
        result = [0 for i in range(max(my_list) + 1)]
        for i in my_list:
            result[i] += 1
        return result
        
    def find_node(tour):
        for i in tour:
            if freq[i] != 0:
                return i
        return -1
    
    def helper(tour, next):
        find_path(tour, next)
        u = find_node(tour)
        while sum(freq) != 0:     
            sub = find_path([], u)
            tour = tour[:tour.index(u)] + sub + tour[tour.index(u) + 1:]  
            u = find_node(tour)
        return tour
                 
    def find_path(tour, next):
        for (x, y) in graph:
            if x == next:
                current = graph.pop(graph.index((x,y)))
                graph.pop(graph.index((current[1], current[0])))
                tour.append(current[0])
                freq[current[0]] -= 1
                freq[current[1]] -= 1
                return find_path(tour, current[1])
        tour.append(next)
        return tour             
             
    graph += [(y, x) for (x, y) in graph]
    freq = freqencies()   
    return helper([], graph[0][0])

The graph is given as a list of tuples. Tuple (x, y) indicates that node x has an (undirected) edge to node y. In line 37 the list with nodes is enlarged by adding tuples (y, x) to it, which reflects the fact that the edges are undirected.

In addition, a list of the number of edges per node (“freq”) is created and updated as the list with the eventual Eulerian tour is built. This means that whenever a node that is part of the Eulerian tour is found, the two affected nodes have their number of edges reduced by one.

If the graph has cycles, it is possible that the first pass of find_path() doesn’t process part of the graph. In this case, the program checks whether the sum of the list “freq” is equal to zero. If it is, then the Eulerian tour has been computed since there are no unused edges left. On the other hand, if “sum(freq)” is greater than zero, then unused edges are left, so the program proceeds finding a node with unused edges, finds another cycle, and inserts it into the resulting Eulerian tour. This step will be repeated for as long as there are unused edges in the graph.

Please note that any node can be used as a staring point. This follows from the existence of an Eulerian path, which uses all edges. Since it contains all edges, you can pick any node and from there pick any edge to start the Eulerian tour with.

On the Udacity forums I found a very helpful test case, which is a graph with three cycles. When working on the program, I used this and two derivative cases to test and guide development. Here they are:

graph1 = [(0, 1), (1, 2), (2, 0)]
# returns [0, 1, 2, 0]

graph2 = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)]
# returns [0, 1, 2, 3, 4, 2, 0]

graph3 = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2), (4, 5), (5, 6), (6, 4)]
# returns [0, 1, 2, 3, 4, 5, 6, 4, 2, 0]