1. API and elementary implementations

Collection: data struct for inserting and deleting items (ex. stack and queue).
Priority queue: a special kind of collection — remove largest/smallest element.

API:

public class Max<Kye implements Comparable<Key>>{   
    public MaxPQ();    
    public void insert(Key k);   
    public Key delMax();    
    public boolean isEmpty();     
    public …

(maybe best algorithm for sorting.)

1. Quicksort

Idea:

1. shuffle the array
2. Partition the array into two subarrays to left and right of pivot (*now pivot is *in its final position)

no larger entry to the left of pivot
no smaller entry to the right of pivot

1. sort each subarray recursively …

Two classical sorting algorithms: mergesort, quicksort.

1. Mergesort

Divide and conquer: top 10 algorithms of the 20th century, invented by von Neumann.

Idea:

• divide array into 2 halves
• recursively sort each half
• merge two sorted halves

Implementation

Merge:
Goal: a[lo] to a[mid] and a[mid+1] to a …

1. Introduction

rearanging array of size N into ascending order
test client code: Insertion.sort(a);

sort any datatype

callback

callback = reference to executable code
i.e. passing functions as argument to sort() method
sort() function calls object's compareTo() method

→ implement the Comparable interface:

    public class XX implements Comparable<XX …

fundamental data types: stacks and queues operations: insert, remove, test empy, iterate,...

module programming: seperate interface and implementation

1. Stacks

ex. a stack of strings

• API:

  public interface StackoOfStrings{ void push(String item); String pop(); boolean isEmpty(); //int size(); }

implementation 1: using a linkedlist

insert/remove from the top of …

model & problem

(原文描述太啰嗦了)
A system using an N-by-N grid of sites.
→ Each site is either open or blocked.
→ A full site is an open site that can be connected to an open site in the top row via a chain of neighboring open …

1. Introduction

2. Observations

ex. 3-SUM pb
given N distinct numbers, how many triples sum up to 0? (pb related to computatioal geogtry)

• brute force method:

for(int i=0;i<N;i++)
    for(int j=i+1;j<N;j++)
        for(int k=j+1;k<N;k++)
            {if …

Part 0: Preliminaries

Each line in the ratings dataset (ratings.dat.gz) is formatted as:
UserID::MovieID::Rating::Timestamp ⇒ tuples of (UserID, MovieID, Rating)in ratingsRDD
Each line in the movies (movies.dat) dataset is formatted as:
MovieID::Title::Genres ⇒ tuples of (MovieID, Title) in ratingsRDD

487650 ratings and 3883 …

1. Dynamic Connectivity pb

pb statement

a set of N obj, indexed by 0,1,...,N-1 ⇒ * UNION: connect objects void union(int p, int q) * FIND: is there a path connecting 2 obj? boolean connected(int p, int q)

ex:

connect components(联通分支): max set of obj …

STATISTICS, BUSINESS QUESTIONS, AND LEARNING TECHNIQUES

2 different kinds of statistics:

• descriptive statistics

ex. median — describes data, but cannot generalize beyong that

• inferential statistics

ex. t-testing — inferences beyond the data techniques leveraged for machine learning and prediction

supervised learning (clf, reg), unsupervised learning (clustering, dim-reduction) → UL often used in a …