Supplementary & Ancillary

Lecture topics

DSSL2

In addition to the parts of the documentation you will find particularly helpful, including

• Syntax
• Statements including class and struct
• Expressions
• Contracts

You should also consult the language implementation, which has available a whole collection of pre-implemented libraries whose source you could look at for interesting examples. Download it from Github and play with it yourself!

DSSL2 for Java Programmers

Please also find, in the course website repository, a kind of “Rosetta stone” for how to read and write DSSL2 code from the perspective of a Java programmer.

In order to run and test the Java code, assuming you have JDK1.8+ installed and on your path, execute the following:

javac Main.java; java Main

• How to Design Classes a draft text for designing programs w/classes.

Recursion

• Recursion refresher

Big O, Asymptotic analysis

• Big O Notation
• Calculating Asymptotic complexity for a piece of code
• Big O Cheat Sheet
• Alternative way to think about it, post

Dynamic Programming

• Dynamic programming

Graph Problems

• Breadth-first search
• Depth-first search
• Traveling salesman problem

Ancillary

• PageRank: A trillion dollar algorithm
• A* search algorithm, explained
• The sights and sounds of sorting
• Other traveling salesman solution
• A short history of computational complexity
• Python and Java sorting algorithms were broken!

Fun

• AlgoRhythmics dance troupe demonstrates sorting by European folk dances
• Sorting, searching, and balancing the IKEA way