CS2010 Lab 01 – About Me – Attendance
CS2010 Lab 01
About Me
- Yao Yujian
- yyjhao@gmail.com
- Please indicate [CS2010] in the title of your email
Attendance
Coursemology
- http://coursemology.com/courses/20
- Download the PS1 Files
- Do not need to submit to Coursemology
-
Coursemology is for
- Downloading PS packages
- Viewing your scores and achievements
- Submit to Mooshak
Mooshak
- http://algorithmics.comp.nus.edu.sg/~mooshak
- Password has been sent to you by email
-
Automatic and instant grading!
- AC(cepted)
- Wrong Answer
- Time Limit Exceeded
- Run Time Error
- Compile Time Error
- Unless there are specific constraints (like PS1 Subtask 3/ Problem C), if you get your code AC, you will get that amount of marks as stated in the problem description
- However, post-deadline penalty (e.g. your code are found to be a very similar copy of someone else’s code) can still alter the score
The Problem Sets
- Subtask 1 is always the easiest, but low marks
- Subtask 2 (or also 3) is/are CS2010 standard, medium marks
- The last (or the R) Subtask is quite challenging, but low marks
Case study: Indexing City Names
- Given some cities
- Connect some of them
TreeMap<String, Integer> nameToNum = new TreeMap<String, Integer>();
if(!nameToNum.containsKey(name)){
nameToNum.put(name, nameToNum.size());
}
PS2
PriorityQueue
- There's a Java API for that
- http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html
- Here's also an example
// copy and paste this to your text editor for better reading experience
// credit: ch2_06_priority_queue.java from CP3 book
import java.util.*;
class pair < X, Y > { // utilizing Java "Generics"
X _first;
Y _second;
public pair(X f, Y s) { _first = f; _second = s; }
X first() { return _first; }
Y second() { return _second; }
void setFirst(X f) { _first = f; }
void setSecond(Y s) { _second = s; }
}
class ch2_06_priority_queue {
public static void main(String[] args) {
// introducing 'pair'
// take note of the use of comparator
PriorityQueue < pair < Integer, String > > pq = new PriorityQueue < pair < Integer, String > >(1,
new Comparator< pair < Integer, String > >() { // overriding the compare method
public int compare(pair < Integer, String > i, pair < Integer, String > j) {
return j.first() - i.first(); // currently max heap, reverse these two to try produce min-heap
}
}
);
// suppose we enter these 7 money-name pairs below
/*
100 john
10 billy
20 andy
100 steven
70 felix
2000 grace
70 martin
*/
pq.offer(new pair < Integer, String > (100, "john")); // inserting a pair in O(log n)
pq.offer(new pair < Integer, String > (10, "billy"));
pq.offer(new pair < Integer, String > (20, "andy"));
pq.offer(new pair < Integer, String > (100, "steven"));
pq.offer(new pair < Integer, String > (70, "felix"));
pq.offer(new pair < Integer, String > (2000, "grace"));
pq.offer(new pair < Integer, String > (70, "martin"));
// this is how we use Java PriorityQueue
// priority queue will arrange items in 'heap' based
// on the first key in pair, which is money (integer), largest first
// if first keys tied, use second key, which is name, largest first
// the internal content of pq heap MAY be something like this:
// re-read (max) heap concept if you do not understand this diagram
// the primary keys are money (integer), secondary keys are names (string)!
// (2000,grace)
// (100,steven) (70,martin)
// (100,john) (10,billy) (20,andy) (70,felix)
// let's print out the top 3 person with most money
pair<Integer, String> result = pq.poll(); // O(1) to access the top / max element + O(log n) removal of the top and repair the structure
System.out.println(result.second() + " has " + result.first() + " $");
result = pq.poll();
System.out.println(result.second() + " has " + result.first() + " $");
result = pq.poll();
System.out.println(result.second() + " has " + result.first() + " $");
}
}
The Online Quiz 1
- Your chance for 2% BONUS POINTS!!!
- URL:
- http://algorithmics.comp.nus.edu.sg /weneedaname/theexperiment.html
- This lab group 2-letter PWD prefix: wo
- UID is your matric number all in UPPERCASE
- Password is your Mooshak password with the prefix in front
Unlock the lock
- Given:
- L, current lock code, 4 digits integer 0000-9999
- U, unlock code, also 4 digits integer 0000-9999
-
R, number of buttons, R ≤ 10
- Followed by Ri numbers: the value of each button
- Each press of button i transform L to (L + Ri)
- Problem: Can U be reached from L?
- If yes, with how many button presses?
- If no, print “Permanently Locked”
Finding the implicit graph
- There are max 10000 vertices: 0000-9999!
Connect two vertices (L1 and L2) with an edge if L2 = (L1 + Ri) for some button i
- What is the graph problem?
- sssp from starting L, output dist[U]
if dist[u] is INF, print “Permanently Locked”
- What is the graph algorithm?
O(V+E) BFS, as the graph is unweighted
Number Maze
- Given:
-
- N*M grid of 1-digit integers [0..9] and 1 ≤ N, M ≤ 999
- Problem: What is the min cost value from TL to BR?
-
- TL = top-right corner, BL = bottom-right corner
0
3
1
2
9
7
3
4
9
9
1
7
5
5
3
2
3
4
2
5
implicit graph
- There are max 999 * 999 = 998001 1M vertices/cells
- Connect two vertices/cells (a and b) with an edge
- if they share a common border
- Give all weight to a vertex by the value of cell in maze
sssp from top-left cell to bottom-right cell + maze[0][0]
- O((V+E) * log V) Dijkstra’s for weighted graph
The O(VE) Bellman Ford’s is still too slow
0
3
1
2
9
7
3
4
9
9
1
7
5
5
3
2
3
4
2
5
class IntegerScanner { // only work for all integer input
BufferedInputStream bis;
IntegerScanner(InputStream is) {
bis = new BufferedInputStream(is, 1000000);
}
public int nextInt() {
int result = 0;
try {
int cur = bis.read(); // use read instead of readline
if (cur == -1)
return -1;
while (cur < 48 || cur > 57)
cur = bis.read();
while (cur >= 48 && cur <= 57) { // ASCII values of 0 to 9
result = result * 10 + (cur - 48);
cur = bis.read();
}
return result;
}
catch(IOException ioe) {
return -1;
} } }
Modified Bellman Ford's
counter = 0
for each query p(s,t);
dist[s] = 0; // s is the source vertex
loop V-1 times
change = false;
for each edge (u,v) in L
increase counter by 1;
if dist[u] + weight(u,v) < dist[v]
dist[v] = dist[u] + weight(u,v);
change = true;
if change is false // this is the ’optimized’ Bellman Ford
break from the outermost loop;
output dist[t];
How to make it run in O(VE)?
Modified Dijkstra’s
counter = 0;
for each query p(s,t)
dist[s] = 0; pq.push(pair(0, s)); // pq is a priority queue
while pq is not empty
increase counter by 1;
(d, u) = the top element of pq and then remove it from pq;
if (d == dist[u]) // that important check
for each edge (u,v) in L
if (dist[u] + weight(u,v)) < dist[v]
dist[v] = dist[u] + weight(u,v);
insert pair (dist[v], v) into the pq; // lazy
output dist[t];
How to make this run extremely slowly?
Image courtesy of Francisco Criado, one of Steven's CP book reader from Spain
What if
PriorityQueue<IntegerPair> pq = new PriorityQueue<IntegerPair>();
pq.offer(new IntegerPair(0, s));
while (!pq.isEmpty()) {
IntegerPair top = pq.poll();
int d = top.first(), u = top.second();
if (u == t) break; // to speed up a bit,
// what if 0 is very close to 1 but the graph is very gigantic?
if (d > dist.get(u)) continue; // some of you don’t do this
// what if there are so many inferior information in the PQ?
for (int j = 0; j < AdjList.get(u).size(); j++) {
IntegerPair p = AdjList.get(u).get(j);
int v = p.first(), weight_u_v = p.second();
if (dist.get(u) + weight_u_v < dist.get(v)) {
dist.set(v, dist.get(u) + weight_u_v);
pq.offer(new IntegerPair(dist.get(v), v));
} } }