2012/2013, Semester 2

School of Computing (Computer Science)

Modular Credits: 4

It covers techniques for attacking and solving challenging* computational problems. Fundamental algorithmic solving techniques covered include complete search, divide/reduce/transform and conquer, greedy, dynamic programming, etc. Domain specific techniques like graph, mathematics-related, string processing, and computational geometry will also be covered. Some additional topics may be included depending on how the semester progresses. Programming language libraries that are commonly used in problem solving will also be taught.

*. We only study well-known/solved problems, not research problems.

Week | Contest | Lecture Topics | Self Reading (CP2.9) | Homework (due Wed, 11.59) |

1 16 Jan |
Mock 0 Ad Hoc |
Let's Talk CPIntroduction Course Admins Clicker System Some "Wow" MomentsMock/Preview Contest |
Preface to Chapter 1 (all pages) Plus Section 9.2, 9.17, 9.19, 9.21, and 9.22 |
Set up UVa account Solve one problem in UVa |

2 23 Jan |
Mini 1 Linear Algorithms |
Be A LibrarianMastery of Libraries (C++ STL & Java API) Mastery of Bit ManipulationBinary Indexed (Fenwick) TreeOptional class on Sat 26 Jan, 10am-12pm @ PL6 to discuss various Week01-02topics that are skipped in the first two Wednesday lectures of this semester. Students who are still deciding on continuing/dropping this module should attend! |
Chapter 2 Focus on Section 2.2 (Bitmask) and 2.4.4 (BIT) Read the rest of Chapter 2 by yourself |
uHunt series #1 due |

3 30 Jan |
Mini 2 Libraries |
Searching for AnswersIterative Techniques Recursive Backtracking State-Space Search (harder form of SSSP, Graph modeling + BFS/Dijkstra's) Meet in the Middle (Bidirectional Search) |
Chapter 3, 4, and 8 Focus on Section 3.1-2, 4.2.2, 4.4.2-3, and 8.1-8.2 Read Divide and Conquer (Section 3.3)and Greedy (Section 3.4) by yourself |
HW1 due Solve Mini 1, prob C uHunt series #2 due |

4 06 Feb |
Mini 3 Search |
Don't Forget to Take NoteDynamic Programming (round 1, easier) Review of CS2010/CS2020 Dynamic Programming Materials DP and DAG, more examples. |
Chapter 3 and 4 But focus on Section 3.5-3.7 and 4.7-4.7.1 |
HW2 due Solve Mini 2, prob C uHunt series #3 due |

5 13 Feb |
Mini 4 DP1 (easier) |
The Art of StenographyDynamic Programming (round 2, more challenging) Formulating non trivial DP states + transitionsDP on Math Problems, DP on String Problems, various DP tricks, DP speed up. (CNY holiday during Monday and Tuesday of Week05but try NOT to skip our Wednesday class this week). Optional review of CS2010/CS2020 graph materialon Sat 16 Feb, 12-2.30pm @ PL6. |
Focus on Section 5.4, 5.6, 6.5, and 8.3, Plus Section 9.1, 9.3, 9.11, 9.12, 9.13, and 9.23 Read "standard" graph topics by yourself(Section 4.1 to 4.5) or attend this optional review Note: All these have been covered in CS2010/20 |
HW3 due Solve Mini 3, prob C uHunt series #4 due |

6 20 Feb |
Mid-semester Team Contest Week01-05 stuffs 6-10pm (4 hours) |
No new lecture topic |
Wk1-5 reading materials and parts of Ch9 |
HW4 due Solve Mini 4, prob C uHunt series #5 due |

- | - | Recess week | - | uHunt series #6 due |

7 06 Mar |
Mini 5 DP2 (harder) |
How to (Theoretically) Prevent Flood?Graph (round 1): Network Flow and applicationsMax Flow: Ford Fulkerson's, Edmonds Karp's Applications: Bipartite Matching with Capacity, Min Cut, Multi Sources/Sinks, Vertex Capacities, Independent Paths, Edge-Disjoint Paths, Min Cost Max Flow Flow Graph Modeling skill NOI 2013: (Competition, 9 March 2013) |
Focus on Section 4.6 and parts of Ch9 |
HW5 (special) due uHunt series #7 due |

8 13 Mar |
Mini 6 Graph1 Network Flow |
Social Development NetworkGraph (round 2): Graph Matching and applicationsUnweighted MCBM: Max Flow, Augmenting Path, Hopcroft Karp's Unweighted MCM: Edmonds's Matching Algorithm Weighted MCBM: Min Cost Max Flow (overview only) Weighted MCM: DP with Bitmask (only for small graph) Applications: Matching with Capacity, Vertex Cover, Independent Set, Path Cover NOI 2013: (Prize Giving Ceremony, 16 March 2013) |
Focus on Section 4.7.4 and parts of Ch9 including the newly written sections in Ch9 |
HW6 due Solve Mini 5, prob C uHunt series #8 due |

9 20 Mar |
Mini 7 Graph2 Matching |
NUMB3RSMathematics, Overview Focus on Java BigInteger, Combinatorics, Number Theory, a bit of Cycle-Finding |
Chapter 5 Focus on Section 5.3-5.5 Read the rest of the chapter by yourself |
HW7 due Solve Mini 6, prob C uHunt series #9 due |

10 27 Mar |
Mini 8 Mathematics |
A Glance at BioinformaticsString Processing Focus on SuffixTrie, Suffix Tree, and Suffix Array(Good Friday and Easter Sunday this week) |
Chapter 6 But focus on Section 6.6 Read the rest of the chapter by yourself |
HW8 due Solve Mini 7, prob C uHunt series #10 due |

11 03 Apr |
Mini 9 String |
Inside Video Games(Computational) Geometry Focus on Algorithms Points, Lines, and Polygon |
Chapter 7 But focus on Section 7.3 Read the rest of the chapter by yourself |
HW9 due Solve Mini 8, prob C uHunt series #11 due |

12 10 Apr |
Mini 10 (Comp) Geometry |
The Last Lecture |
Something from Chapter 8 and something not found in the book at all |
HW10 due Solve Mini 9, prob C uHunt series #12 due |

13 17 Apr |
Final team contest Week01-12 stuffs 6-10pm (4 hours) |
No new lecture topic | The entire book |
HW11 due Solve Mini 10, prob C uHunt series #13 due |

- | No final exam | - | HW12 (special) due |

The programming languages used in this course are C/C++ (main) and Java (secondary). It is much better if you are a multi-lingual programmer.

The 2 hours lecture, 1 hour tutorial, and 0 hour lab are combined into 3 hours lecture + hands-on session

Each class usually starts with 75 minutes top-coder individual programming contest, followed by 15 minutes break / discussion of past contests.

Each contest contains: 1 (very?) easy + 1 easy-medium problems that have been taught in previous week(s) + 1 medium-hard problem that can also be from previous week(s) or just simply "out of topic", usually harder/more creative.

Then, the course material will be delivered via lectures.

On most weeks, classes will end by

For weekly homeworks (3+3 = 6 hours++), students are expected to read "Competitive Programming" textbook (2.9th edition) and attempt some written and programming exercises...

Students have to do

A.1. 10 Weekly Individual Contests (10 weeks x 3%/week = 30%, three problems in 75 minutes)

A-very easy/easy: 0.5%

B-easy/medium, 1.0%

C-medium/hard, 1.5%

Ocassionally, on some weeks, we may open problem D (or even E) which is the easier form of problem A/B/C, such problem will be given low marks.

A.2. 1 Mid-Semester

A.3. 1 Final

Bonus 0.5% for top 3 in each individual contest (or top 3 teams in mid and final contest)

Binary grading (Accepted or not Accepted: Wrong Answer, Time Limit, Memory Limit, Runtime Error, etc)

Team = team of three students.

B.1. 12 Weekly Homework (12 weeks * 1.5%/week = 18%)

CP2.9 book review + solve designated written exercises + weekly update with the lecturer (details after each lecture), 1.5%

Scoring scheme: 0% = no submission, 0.5% = poor submission, 1% = default score, 1.5% superb submission

B.2. Solve problem C of last week's mini contest at home,

Scoring scheme: 0% = not AC in the actual mini contest, not attempted after one more week, 0.3% = minimal attempt, very far from AC, 0.6% = not AC yet, but judged to be near AC, 1% = AC (either during the actual mini contest, or within one week after that)

B.3. Set of "Achievements" (24%++)

One star = 1%, three stars = 3 %

1*.**Let it begins:** Solve any 1st UVa problem by Thursday, 17 January 2013, 23:59 (one day after introduction lecture)

2*.**Quick starter: **Solve a total of **40** UVa problems (from any category) by the end of Week02

We will use the new http://uhunt.felix-halim.net/series for this semester.

Steven will select ten targetted UVa problems related to CS3233 topic of that week.

To get 1% achievement point, student has to solve three out of those ten problems within the stipulated deadline (Thursday of that week until Wednesday of the following week).

Out of this 10, Steven will highlight one (or two) that is (are) "highly recommended" to be tried at home, but you can generally solve any 3 out of 10.

3*. Week #1 (17-23 Jan), Ad Hoc

4*. Week #2 (24-30 Jan), Data Structures and Libraries

5*. Week #3 (31 Jan-06 Feb), Complete Search

6*. Week #4 (07-13 Feb), Dynamic Programming 1

7*. Week #5 (14-20 Feb), Dynamic Programming 2

8*. Week #6 (21-27 Feb), Graph 1 (Basics) -- intersect NUS recess week

9*. Week #7, Graph 2 (Shortest Paths) -- during NUS recess week

10*. Week #8, Graph 3 (Network Flow)

11*. Week #9, Graph 4 (Matching)

12*. Week #10, Mathematics

13*. Week #11, String Processing

14*. Week #12, Computational Geometry

15*. Week #13, Mix and Match

Total percentage so far: 15%

Awarded by TA: Huang Da

16*.**High determination**: Objective title for student who always diligently solve problem C (solve = eventually AC) of all 10 weekly contests, be it during contest time or as homework assignment

Total percentage so far: 16%

Awarded by Lecturer: Steven

17*.**Surprise us**: Managed to surprise the teaching staffs by giving a better/more elegant solution/pinpoint bug in lecture, etc anytime during the semester (max claim: 1 time/student)

18*.**Active in class**: Subjective title for student who participated well during **various class activities** (answering in-lecture questions, asking questions, consultations, active in uHunt series, etc), awarded by Steven

19***.**Bookworm**: *Subjective title* for student who diligently study and review CP2.9 book by the end of Week13, awarded by Steven

20***.**UVa apprentice**: 7 * X / 1670 * 3%, this is a comparison between what you manage to solve in UVa online judge (X) by the end of the semester (**Saturday, 11 May 2013**) compared to Steven's at the start of semester (1670 AC problems), multiplied by a scaling factor of 7 =)... or approximately 235 AC problems in one semester (it is possible for student to score > 3% in this component).

Total percentage so far: 24%

**No final exam, "no" Bell's curve, "easy to score", and a "very fun" course :)**

To get at least B+, student must score**at least 52 out of 100** from the assessment scheme shown above.

**Almost all** students in the past 4 years of CS3233 (2009, 2010, 2011, 2012) managed to achieve B+ or more.

One star = 1%, three stars = 3 %

1*.

2*.

We will use the new http://uhunt.felix-halim.net/series for this semester.

Steven will select ten targetted UVa problems related to CS3233 topic of that week.

To get 1% achievement point, student has to solve three out of those ten problems within the stipulated deadline (Thursday of that week until Wednesday of the following week).

Out of this 10, Steven will highlight one (or two) that is (are) "highly recommended" to be tried at home, but you can generally solve any 3 out of 10.

3*. Week #1 (17-23 Jan), Ad Hoc

4*. Week #2 (24-30 Jan), Data Structures and Libraries

5*. Week #3 (31 Jan-06 Feb), Complete Search

6*. Week #4 (07-13 Feb), Dynamic Programming 1

7*. Week #5 (14-20 Feb), Dynamic Programming 2

8*. Week #6 (21-27 Feb), Graph 1 (Basics) -- intersect NUS recess week

9*. Week #7, Graph 2 (Shortest Paths) -- during NUS recess week

10*. Week #8, Graph 3 (Network Flow)

11*. Week #9, Graph 4 (Matching)

12*. Week #10, Mathematics

13*. Week #11, String Processing

14*. Week #12, Computational Geometry

15*. Week #13, Mix and Match

Total percentage so far: 15%

Awarded by TA: Huang Da

16*.

Total percentage so far: 16%

Awarded by Lecturer: Steven

17*.

18*.

19***.

20***.

Total percentage so far: 24%

To get at least B+, student must score