[Algorithms I] Week 2-1 Stacks and Queues

Thu, 09 Jul 2015 Category notes algorithm Series Part 4 of «Algorithms Princeton MOOC I»

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 ...

[Algorithms I] Week1-Lab: Percolation

Tue, 07 Jul 2015 Category notes algorithm Series Part 3 of «Algorithms Princeton MOOC I»

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 sites. (这个full的定义有玄机而且导致后面写程序时有个问题, 看论坛想了半天才想出来, 见后文.)
→ We say ...

[Algorithms I] Week 1-2 Analysis of Algorithms

Thu, 02 Jul 2015 Category notes algorithm Series Part 2 of «Algorithms Princeton MOOC I»

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 ...

[Algorithms I] Week 1-1 Union-Find

Sat, 27 Jun 2015 Category notes algorithm Series Part 1 of «Algorithms Princeton MOOC I»

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: