akueisara

Dijkstra's Algorithm

PQ ordering is based on: g(n): the distance (cost) from start vertex to vertex n.

A* algorithm

PQ ordering is based on: g(n): the distance (cost) from start vertex to vertex n AND h(n): the heuristic estimated cost from vertex n to goal vertex.
f(n) = g(n) + h(n)

akueisara

Most Direct Route

1. Most Direct Route

(1) Paths and lengths

Length of the path L(P) is the number of edges in the path.

(2) Distances

The distance between two vertices is the length of the shortest path between them.

2. Breadth-First Search

akueisara

BFS: Algorithm

BFS(S, G):
  Initialize: queue, visited HashSet and parent HashMap
  Enqueue S onto the queue and add to visited
  while stack is not empty:
    dequeue node curr from front of queue
    if curr == G return parent map
    for each of curr's neighbors, n, not in visited set:
      add n to visited set

akueisara

Directed Graphs

1. Directed Acyclic Graphs

(1) Directed Graphs

Definition

A directed graph is a graph where each edge has a start vertex and an end vertex.

(2) Directed DFS

• Only follow directed edges.
• explore(v) finds all vertices reachable from v.
• Can still compute pre- and post- orderings.

akueisara

Graph Basics

Examples

• Internet: Webpages connected by links.
• Maps: Intersections connected by roads.
• Social Networks: People connected by friendships.
• Configuration Spaces: Possible configurations connected by motions.

Definition

Graph

An (undirected) Graph is a collection V of vertices, and a collection E of edges each of which connects a pair of vertices.

akueisara

def isLeapYear(year):
    # From Wikipedia http://en.wikipedia.org/wiki/Leap_year
    """
    if (year is not exactly divisible by 4) then (it is a common year)
    else
    if (year is not exactly divisible by 100) then (it is a leap year)
    else
    if (year is not exactly divisible by 400) then (it is a common year)
    else (it is a leap year)    
    """

akueisara

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E extends Comparable<E>> {
  TreeNode<E> root;
  
  public BinaryTree() {
    root = null;
  }
 

akueisara

"""Count words."""

def count_words(s, n):
    """Return the n most frequently occuring words in s."""
    
    # TODO: Count the number of occurences of each word in s
    words = s.split()
    word_occurences = [words.count(i) for i in words]
    word_map = dict(zip(words, word_occurences))
    # TODO: Sort the occurences in descending order (alphabetically in case of ties)

akueisara

#Create a deck of cards

class Card(object):
    suits = ["spade", "heart", "club", "diamond"]
    ranks = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"]

    def _init_(self, suit, rank):
        self.suit = suit
        self.rank = rank