(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 …

DATA CLEANING

ex. deal with missing data, entity resolution, unit mismatch, ...

deal with non-ideal samples ⇒ tradeoff between simplicity and accuracy.

DATA QUALITY PROBLEMS

data quality problems:

• Conversions in complex pipelines can mess up data
• Combining multiple datasets can result in errrors
• Data degrades in accuracy or loses value over time …