Tag Archives: graph-theory

Big-O Quiz: Graph Theory

I’ve been studying more graph theory recently. To take notes that I might remember, I added a Graphs quiz to my Big-O Quiz site. It covers the graph theory mentioned in The Algorithm Design Manual and in the Stanford/Coursera “Algorithms: Design and Analysis Parts 1 & 2”  courses by Tim Roughgarden. I’m adding to it as I work through Tim Roughgarden’s follow-up “Second course in Algorithms“.

It’s often a slightly silly quiz, offering you algorithm descriptions that make no sense for the question’s problem, along with the correct one, but the aim is to just to reinforce my memory by exercising my memory. So I’ve tried to use concise descriptions of problems and algorithms, without trying to be exhaustively correct.

Boost Graph Library and C++ >17

I’ve recently been looking at the Boost Graph Library (BGL), by reading through the excellent BGL book and playing with the BGL examples, which are mostly from the book.  Although it  was written 15 years ago, in 2001, it doesn’t feel dated because it uses techniques being actively discussed now for C++17 or later. And there’s a clear lineage from then to now.

For instance, I’ve been watching the charming Programming Conversations videos by Alexander Stepanov, who brought generic programming to C++ by designing the STL. At some early point in the videos, he mentioned the idea of concepts, which he expected to be in C++17, and showed how he mimicked the simpler concepts syntax (without the checking) with some #defines. Unfortunately, that proposal, by Andrew Sutton, has recently been rejected for C++17, though it seems likely to succeed after C++17. Andrew Sutton demonstrates the proposed syntax wonderfully in this C++Now 2015 Keynote video. He has implemented C++ concepts in gcc 6, and I’ve played with it very superficially for libsigc++.

I’ve written and maintained lots of C++ template code and I’ve never liked how each template makes only implicit requirements of its types. I would feel more comfortable if I could express those requirements in a concept and have the compiler tell me if my template’s types don’t “model” the concept. Eventually compiler errors will then mention problems at that higher level instead of spewing details about exactly how compilation failed. And eventually, C++ might allow checking of semantics as well as just syntax. I can even imagine tools that would analyze template code and suggest that it should require certain concepts for its types, a little like how the latest compilers can suggest that I use the override keyword on virtual method overloads. This means more checking at compile time, and that makes me happy. However, I understand why it would need multiple compilers to implement it before it would be accepted into C++17.

Anyway, I started reading that BGL book and immediately noticed the foreword by the same Alexandar Stepanov, which mentions generic programming ideas such as concepts. The BGL uses concepts, though with minimal checking, and the book uses these to show the structure of the API. Furthermore, as I tried to get some simple changes into the BGL, I noticed that the same Andrew Sutton had been a maintainer of the BGL.

I began playing with the BGL by converting its example code to modern C++, replacing as many of those verbose traits typedefs and awkward tie() calls, with the auto keyword and range-based for loops. The result looks far clearer to me, letting us see how the API could be improved further. For instance, the BGL’s use of generic free-standing functions can seem a little unconstrained to people used to knowing exactly what method they can call on what object, particularly as the BGL puts everything in the boost namespace instead of boost::graph). But Bjarne Stroustrup’s Unified Call proposal (apparently rejected for C++17 too) would improve that. For instance, num_vertices(graph), could be written as graph.num_vertices() and Concepts would let the compiler know if that should be allowed.

So, though the BGL source code seems to have had very little attention over the last 15 years, and now looks almost abandoned, it’s clearly been an inspiration for the most current trends in C++, such as Concepts and Unified Calling. All the work on C++11 and C++14 has drained the swamp so much that these old ideas are now more obviously necessary.

Coursera/Stanford course: Algorithms: Design and Analysis, Part 2

A few weeks ago I mentioned completing Part 1 of the online Coursera/Stanford “Algorithms: Design and Analysis” course. Part 2 of Algorithms: Design and Analysis isn’t due to start again until next year, but I didn’t want to wait, so I enrolled in the archived version of the course to watch the videos and do the assignments. I should be ready to just reuse my work when Part 2 starts again for real.

Part 2 was where things got really interesting. The assignments required implementing these algorithms, though the course covered others too:

  • A Greedy Algorithm for job scheduling.
  • Prim’s and Kruskal’s minimum spanning tree algorithms. (Both O(m log n) but Prims does better on dense graphs, with more edges.)
  • Modifying a minimum spanning tree to identify clusters.
  • The Knapsack problem (Dynamic Programming – both bottom-up and recursive).
  • Shortest Path with the Belmann-Ford SSSP (Single-Source Shortest Path) algorithm (O(mn) and works with negative paths, but fails with negative cycles) as an alternative to Dijkstra’s Shortest Path algorithm (O(m log n) and works only with positive paths).
  • All Pairs Shortest Path with the Floyd Warshall algorithm (dynamic programming) (O(n3) and works with negative paths, though it fails when it detects negative cycles). Best for dense graphs.
  • All Pairs Shortest path with Johnson’s algorithm, via one call to Belmann-Ford on a modified graph and repeated calls to Dijkstra on a reweighted graph. (O(mn log n) and works with negative paths, but fails with negative cycles.) Best for sparse graphs.
  • A dynamic programming algorithm for the Traveling Salesman Problem.
  • Local search with the 2Sat problem, using Papadimitriou’s Algorithm.

I particularly enjoyed exploring “dynamic programming”, which is really just avoiding unnecessary repeated work after you’ve identified the appropriate sub-problems. It’s identifying the sub problems that is really hard. I enjoyed playing with bottom-up dynamic programming (filling in an array as you go, often discarding the n-2th set of results as you go), and top-down dynamic programming, also known as memoization (usually recursing into sub problems and ideally not doing as many sub problems as you’d do working bottom up).

While implementing a dynamic programming solution for the Traveling Salesman Problem, I learned about Gosper’s Hack for iterating over subsets. It’s now a personal favorite in my toolbox.

As with part 1 of the course, I am not allowed to publish the code of my homework solutions. But I did create a public version of the knapsack problem for solving the Make Change problem without a canonical currency (not a real world set of coins), using dynamic programming, though you shouldn’t use that as a first way to understand the classic knapsack problem. I also implemented a simple greedy algorithm for the Make Change problem with a canonical currency (real world set of coins).

The Make Change problem was interesting because I’ve read that people can and should learn to recognize NP-Complete problems, such as the traveling salesman problem. However, it is not obvious which sets of coins would cause the Make Change problem to be solvable with a greedy algorithm and which would need dynamic programming, though it might at first seem like a minor detail. (I haven’t actually read that paper yet.)

I’ve also been reading through Steven Skiena’s The Algorithm Design Manual book, which I can highly recommend. It’s more practical and enjoyable than the classic Introduction to Algorithms book by Cormen et al.

Update: I did part 2 for real when it started again. Here is my certificate:

 

Coursera/Stanford course: Algorithms: Design and Analysis , Part 1

screenshot_github_algorithmsAlthough I’ve been developing software for years, I noticed recently that I lacked the basic computer science knowledge that other people got at university, though it’s never been an issue outside of job interviews. I knew the basics of Big-O notation and how to use data structures but couldn’t describe exactly how various sort algorithms worked or how to analyze an algorithm’s performance from pseudo-code.

But this is all standard stuff now, so filling in the gaps in my knowledge seemed like a solvable problem. Over the last few weeks, I’ve worked through Coursera’s “Algorithms: Design and Analsis, Part 1” online course, provided by Stanford University. I was surprised to find myself enjoying it. It’s nice to get some insight into commonly used algorithms and data structures, and I guess it does help to inform choices made at a higher level, even if that’s only occasionally useful.

Mostly I enjoyed the programming exercises, writing implementations of Mergesort, Quicksort, Karger’s Minimum Cut Algorithm, Strongly Connected Components, Dijkstra’s Shortest-Path Algorithm, a 2-Sum Algorithm, and a Median Maintenance algorithm. Likewise, each week had a theoretical test, checking knowledge of stuff such as the Master Method, sorting algorithms, graph algorithms, heaps, (balanced) binary trees, hash tables, and bloom filters.

Hopefully I’ll keep it in all my head from now on, but that is always easier when you’ve written actual code that you can look back at. I used C++, but you can use any programming language, and nobody checks your code. Of course, I’m not allowed to publish my homework solutions.

I had already been slowly reading through Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein, which is hard going. It also has exercises, but I was far more motivated to complete the Coursera exercises, whose aim was always to get the correct specific numerical answer, so you knew when you had the code working properly. After I finished the course, I found it easy to then read the relevant chapters, which offer much more in-depth analysis than the Coursera course.

Although the participants are all still waiting for their certificates (presumably some skeumorphic image file), I’m sure that I’ve passed with 80-something percent. I’d have done better but I started the course after some homework deadlines had already passed. The final test also showed that I need to be more familiar with logarithm equivalences and geometric progressions. I do have Maths and Further-Maths A-Levels, but it’s been a long time.

Unfortunately, part 2 isn’t due to start again until some time in 2016. But I think I can do the course in the meantime, just without earning an official score.

Update: Here is my certificate for part 1:

murrayc-2015-09-24_coursera_stanford_algorithms_part1

Update: I did part 2 too.