Ludium
Sign In
Introduction to Computational Thinking and Data Science
Optimization
01Optimization Models and the Knapsack Problem02Brute-Force Knapsack and the Exponential Power Set03Greedy Algorithms: One Function, Any Definition of Best04Lambda Keys and Why Greedy Can Miss the OptimumProblem set0/10MIT problem set0/2
01The Knapsack Search Tree: Every Combination, 2ⁿ Nodes02Recursive maxVal: An Exhaustive Search That Beats Greedy03Memoization: Turning Slow Fibonacci into fastFib04Overlapping Subproblems and the Memoized KnapsackProblem set0/10MIT problem set0/2
Graph Models
01Graphs as Models: Nodes, Edges and Euler's Seven Bridges02Coding a Graph in Python: Node, Edge, Digraph and Graph03Depth-First Search for the Shortest Path in a Graph04Breadth-First Search: A Queue of Paths, Fewest Hops FirstProblem set0/10MIT problem set0/4

Coding challenges on graph-theoretic models

Problem 1Coding a Graph in Python: Node, Edge, Digraph and Graph

Store an Undirected Graph as a Dictionary

Write the function undirectedAdjacency(pairs) that turns a list of undirected edges into an adjacency dictionary. Assume pairs is a list of 2-tuples of node names (strings); each pair (a, b) is one undirected edge, so it lets you go from a to b and from b to a, the way the Graph subclass adds each edge's reverse. Return a dictionary mapping every node name that appears in pairs to the set of names it is joined to. A repeated pair adds nothing new.

print(undirectedAdjacency([('a', 'b')]))  # {'a': {'b'}, 'b': {'a'}}
print(undirectedAdjacency([]))  # {}
1
2
3
4
5
6
7
8
def undirectedAdjacency(pairs):
    """pairs: a list of (name, name) undirected edges. Return a dict mapping
    each name in pairs to the set of names it shares an edge with."""
    pass

Scratchpad— run any Python to test ideas
1
2
3
4
5
# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment
Python runtime ready in a moment
Visible tests · 2Examples — click to expand
?
one edge goes both ways
?
a small triangle plus a tail
Hidden tests · 3Bodies hidden — pass/fail only
?
Hidden test 1
?
Hidden test 2
?
Hidden test 3