Intro to Algorithms



Informazioni importanti

  • Corso
  • Online
  • Quando:

This class will give you an introduction to the design and analysis of algorithms, enabling you to analyze networks and discover how individuals are connected.

Informazioni importanti

Dove e quando

Inizio Luogo

Cosa impari in questo corso?

Magic Trick


Lesson 1: A Social Network Magic Trick

Objective: Become familiar with Algorithm Analysis.

  • Eulerian Path
  • Correctness of Naïve
  • Russian Peasants Algorithm
  • Measuring Time
  • Steps for Naive, Steps for Russian
  • Divide and Conquer
Lesson 2: Growth Rates in Social Networks

Objective: Use mathematical tools to analyze how things are connected.

  • Chain, Ring and Grid Networks
  • Big Theta
  • Planar Graphs
  • Nodes, Edges, Regions
  • Growth Rate of Edges in Planar Graph
  • Hypercube
  • Randomly Generated Graphs
  • N Squared
  • Tangled Hypercube
Lesson 3: Basic Graph Algorithms

Objective: Find the quickest route to Kevin Bacon.

  • Properties of Social Networks
  • Clustering Coefficient
  • Connected Components
  • Running Time of Connected Components
  • Checking Pairwise Connectivity
  • Pairwise Shortest Path
  • Depth vs. Breadth First Search
  • Recursion Replacement
  • Marvel “Social” Network
  • Finding Bridge Edges
Lesson 4: It’s Who You Know

Objective: Learn to keep track of your Best Friends using heaps.

  • Degree Centrality
  • Top K Via Partitioning
  • Three Partitioning Cases
  • Properties of a Heap
  • Patch Up a Heap
  • Down Heapify
  • Heap Sort
Lesson 5: Strong and Weak Bonds

Objective: Work with Social Networks that have edge weights.

  • Make a Tree
  • Strength of Connections
  • Weighted Social Networks
  • How to Find the Shortest Path
  • Dijkstra’s Shortest Path Algorithm
  • Floyd-Warshall Intro
  • Randomizing Clustering Coefficient
  • Bounds on the Estimate
Lesson 6: Hardness of Network Problems

Objective: Explore what it means for a Social Network problem to be "harder" than other.

  • Tetristan
  • Exponential Running Time
  • Degrees of Hardness
  • Reduction: Long and Simple Path
  • Polynomial Time Decidable Problems
  • Non-deterministic Polynomial Time Decidable Problem
  • Clique Problem in NP
  • Find the Strangers
  • Graph Coloring is NP-Complete
Lesson 7: Review and Application
  • Interview with Peter Winker (Professor, Dartmouth College) on Names and Boxes Problem && Puzzles and Algorithms

  • Interview with Tina Eliassi-Rad (Professor, Rutgers University) on Statistical Measures in Network && Social Networks in Security and Protests

  • Interview with Andrew Goldberg (Principal Researcher, Microsoft Research) on Practical Algorithms

  • Interview with Vukosi Marivate (Graduate Student, Rutgers University) on Social Algorithms

  • Interview with Duncan Watts (Principal Researcher, Microsoft) on Pathway That Can Use Two Nodes

  • Intro to Graph Search Animation