biancadanforth

/* eslint-env node */

/**
* -------------------------- Part 1 -----------------------------
*/

/**
* In this programming problem and the next you'll code up the greedy algorithms
* from lecture for minimizing the weighted sum of completion times.
*

biancadanforth

/* eslint-env node */

/**
* The goal of this problem is to implement a variant of the 2-SUM algorithm
* covered in this week's lectures.
*
* The file contains 1 million integers, both positive and negative (there
* might be some repetitions!).This is your array of integers, with the ith
* row of the file specifying the ith entry of the array.
*

biancadanforth

/* eslint-env node */

/**
* The goal of this problem is to implement the "Median Maintenance" algorithm
* (covered in the Week 3 lecture on heap applications). The text file contains
* a list of the integers from 1 to 10000 in unsorted order; you should treat
* this as a stream of numbers, arriving one by one. Letting x_i denote the ith
* number of the file, the kth median m_k is defined as the median of the
* numbers x_1, ...,x_k (So, if k is odd, then m_k is ((k+1)/2)th smallest number
*  among x_1, ... ,x_k; if k is even, then m_k is the (k/2)th smallest number

biancadanforth

/* eslint-env node */

/**
* The file contains an adjacency list representation of an undirected weighted
* graph with 200 vertices labeled 1 to 200. Each row consists of the node
* tuples that are adjacent to that particular vertex along with the length of
* that edge. For example, the 6th row has 6 as the first entry indicating that
* this row corresponds to the vertex labeled 6. The next entry of this row
* "141,8200" indicates that there is an edge between vertex 6 and vertex 141
* that has length 8200. The rest of the pairs of this row indicate the other

biancadanforth

/* eslint-env node */
/**
* The file contains the edges of a directed graph. Vertices are labeled
* as positive integers from 1 to 875714. Every row indicates an edge,
* the vertex label in first column is the tail and the vertex label in
* second column is the head (recall the graph is directed, and the edges
* are directed from the first column vertex to the second column vertex).
* So for example, the 11th row looks like: "2 47646". This just means
* that the vertex with label 2 has an outgoing edge to the vertex with
* label 47646

biancadanforth

/* eslint-env node */
/**
* The file contains the adjacency list representation of a simple
* undirected graph. There are 200 vertices labeled 1 to 200. The
* first column in the file represents the vertex label, and the
* particular row (other entries except the first column) tells all
* the vertices that the vertex is adjacent to. So for example, the
* 6th row looks like : "6 155 56 52 120 ...". This just means that
* the vertex with label 6 is adjacent to (i.e., shares an edge with)
* the vertices with labels 155,56,52,120, etc.

biancadanforth

// Course: https://www.coursera.org/learn/algorithms-divide-conquer/home/welcome
// Assignment: https://www.coursera.org/learn/algorithms-divide-conquer/exam/YLbzP/programming-assignment-3
/* eslint-env node */
/**
* Download the following text file: QuickSort.txt
* The file contains all of the integers between 1 and 10,000
* (inclusive, with no repeats) in unsorted order. The integer
* in the ith row of the file gives you the ith entry of an
* input array.
*

biancadanforth

// Course: https://www.coursera.org/learn/algorithms-divide-conquer/home/welcome
// Assignment: https://www.coursera.org/learn/algorithms-divide-conquer/exam/YLbzP/programming-assignment-2

/**
 * Maximum number of inversions: "n choose 2", where n = 100000; i.e. if array of numbers were
 * sorted in descending order (worst case scenario), rather than ascending (best case scenario,
 * 0 inversions).
 * "n choose 2" = [n * (n - 1)]/2
 */

biancadanforth

// From https://www.coursera.org/learn/algorithms-divide-conquer/home/welcome
// Assignment: https://www.coursera.org/learn/algorithms-divide-conquer/exam/srsxO/programming-assignment-1

/**
 * Assignment: Implement a recursive integer multiplication and/or Karatsuba's
 * algorithm to compute the product of the following two 64-digit numbers:
 *  - 3141592653589793238462643383279502884197169399375105820974944592
 *  - 2718281828459045235360287471352662497757247093699959574966967627
 * Constraints:
 *  - Multiply only pairs of single digit numbers

biancadanforth

Patch review

Bug review

• Supporting