No description, website, or topics provided.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
week3/pset3
week4
week5
week6
README.md

README.md

cs215_Intro_to_Algorithms

Some Solutions to "Intro to Algorithms" problems.

Syllabus

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