Week 
Wed Lecture (2 hrs/wk) + SelfStudy/Review (3 hrs/wk) 
Tue/Wed Tutorial (1 hr/wk) 
Thu Demo Lab (1 hr/wk) 
Problem Set (3 hrs/wk) 
02/01/00 
For those who want to do head start in preparing CS2010 before it actually starts:
1. Revise your CS1020 & CS1231 (especially graphs, trees, proofs, see Workbin)
If you have not take CS1231 (which is not the compulsory prereq of this module),
it may be good to casually review some CS1231 material in Workbin
2. Solve the following problems (CS1020 level):
a. UVa 579 (Use this to revise your Java skill)
b. UVa 10855 (Use this to revise your knowledge about Array)
c. UVa 11988 (Use this to revise your knowledge about Linked List)
d. UVa 11111 (Use this to revise your knowledge about Stack)
e. UVa 10901 (Use this to revise your knowledge about Queue)
f. UVa 10258 (Use this to revise your knowledge about Sorting)
g. UVa 11340 (Use this to revise your knowledge about Hashing)

Legends:
RReview Questions
(for selfcheck only)
DDiscussion Questions
(will be discussed
during tutorial sessions)
AAdvanced Questions
(will not be discussed
during tutorial but eager
students are free to
cross check their answers
with TA/lecturers) 
 
 
01 
Wed, 14 Aug, L1: Introduction
a. Quick course admins
b. Distribution of Clickers :)
c. Overview of various technologies used in CS2010 class this semester.
d. CS1020 quick review with Clickers: OO, Big O notation, Linear DS, Hashing, etc
e. Overview of problem solving paradigms used in CS2010 
Not Started 
Not Started 
Not Started 
02 
Wed, 21 Aug, L2: Census Problem
a. ADT Table, comparison with CS1020 Linear DS
b. Revisit (or introduce) CS1231 material (tree)
c. The basic operations of Binary Search Tree (BST) > The first webbased lecture!!
d. Analysis of BST operations 
Not Started 
Not Started 
PS1: Baby Names v3
Released: Fri, 23 Aug, 0.00am
(for R students to decide if
they can handle CS2010R) 
03 
Wed, 28 Aug, L3: Keeping Everything in Balance
a. Quick revision of BST concepts
b. The importance of a balanced BST
c. Introducing AdelsonVelskii Landis (AVL) Tree
d. Overview implementation of AVL Tree, Java Inheritance (code not given due to PS1)

T01, Tue/Wed, 2728 Aug
DTA Introduction
RLinear DS Review
RBig O Review
DDiscussion of various
problem solving
techniques
AExpected O(n) Selection

L01, Thu, 29 Aug
DLab TA Intro & Expectations
DGame system/Coursemology
DOnline Judge/Mooshak
RPS1 overview
RReview of CS1020 material
DDiscussion of one solution
for Week00 UVa problems
(see above) 
No new PS

04 
Wed, 04 Sep, L4: Heaps of Fun
a. Priority Queue ADT
b. Binary Heap DS
c. Building heap from a set of numbers in O(n)
d. Inplace sorting: Heapsort

T02, Tue/Wed, 0304 Sep
RTree/BST DS
RBalanced BST
DbBST variants and
applications
DPS1 Subtask 1
AAVL Tree Deletion

L02, Thu, 05 Sep
DJava TreeMap/TreeSet Demo
(underlying DS: Balanced BST)
DDiscuss some features and
interesting usage :).
e.g. Indexing city names
DPS1 Subtask 2
RPS2 overview 
PS2: Scheduling Deliveries v3
Released: Sun, 01 Sep, 8pm
PS1 due: Sat, 07 Sep, 8am 
05
Elearning
week 
Wed, 11 Sep, L5: Laying the Foundations (electure)
a. Introduction of UnionFind Data Structure (useful for Kruskal's algorithm in Week07)
b. Introduction of Bitmask Data Structure (useful for TSP implementation in Week11)
c. Motivation for learning Graph (selfreading)
d. Revisit CS1231 graph material
i. Implementation of Graph DS: Adjacency Matrix and List (useful for Week 0613)
ii. Graph data structure applications: Enumerate neighbors, edge existence check
Sat, 14 Sep, Time: 10.00am12.00pm, Venue: Seminar Room @ LT19
Optional help session to prepare Quiz 1: Basics+BST+bBST+Heap
And also to review UFDS+Bitmask+Graph DS due to electure :O 
T03, Tue/Wed, 1011 Sep
(etutorial)
RHeap DS
DApplications
DPS2 Subtask 1

L03, Thu, 12 Sep (elab)
DPS1 debrief
DJava PriorityQueue Demo
(underlying DS: Heap)
DDiscuss some features
and interesting usage :)
e.g. Queueing "objects", ve
DPS2 Subtask 2
RPS3 overview

PS3: Hospital Tour v3
Released: Sun, 08 Sep, 8pm
PS2 due: Sat, 14 Sep, 8am 
06 
Wed, 18 Sep, L6: Maze Exploration
(we will use the first few minutes to revise eLecture 05 stuffs)
a. Revisit CS1231 graph material
ii. Implementation of Graph Traversal algorithms:
BreadthFirst Search (BFS), Depth First Search (DFS)
iii. Graph traversal applications:
reachability test, finding connected components, topological sorting
Sat, 21 Sep, 10.00am11.17am, Quiz 1Written (10%):
Venue: LT19 (for students with first name AL) + LT15 (for students with first name MZ)
up to Heap DS (Week04), open book, all essays, you can answer in pseudo code 
T04, Tue/Wed, 1718 Sep
RUFDS
RBitmask
RGraph DS
DPS3 Subtask 1
DDFS/BFS Traversal
(for PS3)

L04, Thu, 19 Sep
DPS2 quick debrief
DPS3 Subtask 23
(max 15 minutes)
Online Quiz 1 (bonus 2%)
about 10+ mins/session
max 2 attempts 
No new PS before Quiz 1
No PS deadline (Quiz 1)
PS bonus: Pancake Sorting
(very hard, not compulsory)
Released: Sat, 21 Sep after Quiz 1 
Recess 
No Lecture
(breathing space for CS2010 students to handle midterm tests
of your other modules if you choose to skip the optional PS bonus)

No session

No session

PS3 due: Mon, 23 Sep, 8am
(extension due to Quiz 1)
PS bonus due: Sat, 28 Sep, 8am 
07 
Wed, 02 Oct, Midsemester review (fifteen minutes)
L7: Connecting People (one+ hour)
a. Revisit CS1231 graphs (esp trees) matrial
b. One application of MST problem
c. Implementation of Minimum Spanning Tree (MST) algorithms
i. Implementation of Prim's with Priority Queue/Heap DS discussed in Lecture 020304
ii. Implementation of Kruskal's with Sorting + UnionFind DS discussed in eLecture 05

T05, Tue/Wed, 0102 Oct
RTopological Sort with DFS
DBipartite Check
DPS4 Subtask 1
ADiscussion of Quiz 1
solutions

L05, Thu, 03 Oct
DPS3 debrief
APS bonus discussion
DGraph DS manipulation
RPS4 overview
RPrimDemo/KruskalDemo

PS4: Out For a Walk v3
Released: Sun, 29 Sep, 8pm

08 
Wed, 09 Oct, L8: Finding Shortest Way from Here to There 1
a. SingleSource Shortest Paths (SSSP) introduction
b. BFS algorithm fails on general case of SSSP problem
b. Generic SSSP algorithm + "analysis"
c. BellmanFord's algorithm + analysis

T06, Tue/Wed, 0809 Oct
RMST, general ideas
DPrim's/Kruskal's
AMST applications
DPS5 Subtask 12

L06, Thu, 10 Oct
DPS4 Subtask 234 (or 56?)
AGraph modeling exercise:
Unlock the Lock and
Number Maze
RPS5 overview 
PS5: The Onset of Labor v3
Released: Sun, 06 Oct, 8pm
PS4 due: Sat, 12 Oct, 8am 
09 
Wed, 16 Oct, L9: Finding Shortest Way from Here to There 2
a. Special Case 1: SSSP on tree (quick review of DFS/BFS)
b. Special Case 2: SSSP on unweighted graph (quick review of BFS)
c. Special Case 3: SSSP on DAG (quick review of DFS/topological sort)
d. Special Case 4: SSSP on weighted graph without negativeweight/cycle (focus of today)
i. Dijkstra's algorithm, two versions
ii. Implementation of both Dijkstra's algorithm variants
iii. Analysis on the performance of both Dijkstra's algorithm variants
Note: Tue, 15 Oct, is Public Holiday (Hari Raya Haji)
Sat, 19 Oct, 10.00am12.00pm, Venue: Seminar Room @ LT19
Optional help session to prepare Quiz 2: Mostly on Week0509 material 
T07, Wed, 16 Oct only
Tue classes are
encouraged to attend
the Wed classes
RSSSP, general ideas
RBellman Ford's
AGraph Modeling exercise
using CS2010 past Quiz 2
problems

L07, Thu, 17 Oct
DPS4 debrief
RPS5 Subtask 1234 (or 5?)
ACool things about
SSSP algorithms
(from APIO2013, TASKSAUTHOR)
RPS6 overview

PS6: Emergency Caesarean v3
Released: Thu, 17 Oct, 9am
(timing adjusted)
PS5 due: Sat, 19 Oct, 8am 
10 
Wed, 23 Oct, L10: Algorithms on DAG
a. SSSP on DAG revisited
b. Longest Paths on DAG, link to Longest Increasing Subsequence (LIS)
c. Introduction to Dynamic Programming (DP)
d. Counting Paths in DAG
Steven will travel to Jakarta for ACM ICPC this week
and Dr Chong Ket Fah will deliver this lecture. 
T08, Tue/Wed, 2223 Oct
RDijkstra's
AGraph modeling, again
(very important skill)
DPS6 Subtask 1

L08, Thu, 24 Oct
DPS5 debrief
DPS6 Subtask 123 (or 4?)
ADemo on Solving UVa 926
(Walking Around Wisely)
which can be modeled as a DAG
RPS7 overview 
PS7: A Trip to Supermarket v3
Released: Thu, 24 Oct, 0.00am
(Happy 2nd birthday for Jane)
PS6 due: Sat, 26 Oct, 8am 
11 
Wed, 30 Oct, L11: Traveling Salesman
a. The Traveling Salesman Problem (TSP): two versions.
b. Conversion to DAG: the backtracking routine
c. Outline implementation using Bitmask (details in PS7)
d. Limitation of the Superpower (a bit of PS7 overview)
Sat, 02 Nov (instead of Sun, 03 Nov) is now a public holiday (Deepavali).
Quiz 2 has to be shifted backwards to our lecture 12 time. 
T09, Tue/Wed, 2930 Oct
RBasic DAG Properties
RBasic DP
DPS7 Subtask 12
AApplication

L09, Thu, 31 Oct
DShort PS6 debrief
ROnline Quiz 2 (10%)
But online quiz 1+quiz 2 scores
are capped to a max of 10%
one long 40 mins session, 1 attempt,
you can recheck your answers
as frequent as you want 
No new PS
No PS deadline (Quiz 2) 
12 
Wed, 06 Nov, 10.00am11.17am, Quiz 2Written (15%):
Venue: COM10206/Seminar Room 1 (big enough for all 166 students)
up to SSSP (Week09), open book, all essays, you can answer in pseudo code,
no more "basic questions".
L12: Four Lines Wonder (11.2011.40am)
a. Short Motivation of the AllPairs Shortest Paths Problem
b. The basic of Floyd Warshall's algorithm
(only the four lines implementation, derivation omitted and won't be asked in final exam)
c. Cool variants of Floyd Warhsall's 
T10, Tue/Wed, 0607 Nov
ALaser, Independent Set
RTSP
DPS7 discussion

L10, Thu, 08 Nov
DPS7 Subtask 2 implementation
DPS7 Subtask 34 (or 56?)
ANice problem solvable
with Floyd Warshall's
Degrees of Separation
RPS8 overview

PS8: The Toddler Years v1
Released: Wed, 06 Nov, 12pm
PS7 due: Sat, 09 Nov, 8am 
13 
Wed, 13 Nov, L13: Mystery Last Lecture (not examinable) + Summary
a. You will learn the details on the spot.
About a "cool" algorithm outside the syllabus
b. Summary and closing any loose ends...

T11, Tue/Wed, 1213 Nov
RFloyd Warshall's (APSP)
DDP vs Graph Problem?
DPS8 Subtask 12 (+3)
AkReliable Shortest Path
DSemester Review
(up to your Tutorial TA)
Take class photo! 
L11, Thu, 14 Nov
DPS7 debrief
DPS8 Subtask 12 (or 3?)
DSemester Review
(up to your Lab TA)
Take class photo!

No new PS
PS8 due: Sat, 16 Nov, 8am 
Study Week
and Exam 
Tue, 19 Nov, 10.00am12.00pm, Venue: COM1120/PL6
Optional help session to prepare Final Exam
Final Exam time/venue: Monday, 25 November 2013, Evening, Venue TBA
Everything, open book, all essays, you can answer in pseudo code 


