# CSCI3270 Advanced Programming Laboratory — Fall 2018

Siu On CHAN Office hours Tuesday 2:30-4:30pm SHB 911

Teaching assistant

- Pengguang CHEN pgchen@cse

## News

- Dec 8: Final Exam will be an open-notes exam: all hard-copy references allowed.
- Dec 8: Final Exam will be on Dec 19 (Wed) at SHB 924B at 6-10pm (please arrive 20 mins early)
- Dec 4: Homework 12 is now posted. Due Dec 12
- Dec 4: Week 12 lecture notes on FFT have been uploaded to Piazza
- Dec 1: Homework 11 is now posted
- Dec 1: Week 12 lecture notes on geometry have been uploaded to Piazza
- Nov 23: Homework 10 is now posted
- Nov 23: Week 11 lecture notes have been uploaded to Piazza
- Nov 3: Week 10 lecture notes on random walks have been uploaded to Piazza
- Nov 3: Homework 9 is now posted
- Nov 3: Week 9 lecture notes have been uploaded to Piazza
- Nov 3: Homework 8 is now posted
- Oct 26: Week 8 lecture notes have been uploaded to Piazza
- Oct 25: Homework 7 is now posted
- Oct 22: Week 7 lecture notes have been uploaded to Piazza
- Oct 19: Homework 6 is now posted
- Oct 12: Week 6 lecture notes have been uploaded to Piazza
- Oct 12: Homework 5 is now posted
- Oct 5: Week 5 lecture notes have been uploaded to Piazza
- Oct 5: Homework 4 is now posted
- Sep 27: Week 4 lecture notes have been uploaded to Piazza
- Sep 27: Homework 3 is now posted
- Sep 20: Homework 2 and Homework 1 replacement are now posted
- Sep 20: Week 3 lecture notes have been uploaded to Piazza
- Sep 19: POJ 1738 from Homework 1 turns out to be much more difficult than expected. I will assign a more appropriate replacement problem with a new deadline later
- Sep 14: Week 2 lecture notes have been uploaded to Piazza
- Sep 13: Homework 1 is now posted
- Sep 7: Starting from week 2 (Sep 13), our lecture is moved to Thu 2:30-4:15 at SHB 123
- Sep 6: Please email me your preferred presentation topic (suggestions are on Piazza) by the end of Sunday Sep 9. Not sending me an email is an indication that you will not take this course
- Sep 3: Please register on Codeforces before the first lecture
- Aug 31: Our first lecture on Sep 6 will take place at SHB 924
- Aug 29: During our first lecture on Sep 6, we will discuss whether to change our lecture time

## Information

## Topics

This course is seminar-based. Lectures consist of students’ 45-min presentations on the following topics that frequently appear in programming contests. Students’ grades are based in part on their presentations. Presenters are also expected to suggest 1-2 related problems on online judges that will serve as exercises or homework problems.

- Computational geometry
- Advanced data structures
- Number theory
- Dynamic programming
- Divide and conquer
- Network flows and linear programming
- Combinatorial game theory
- Miscellaneous

Grading rubrics for presentations (when normalized to 100%):

- Clarity 60%
- Suggested problems 20%
- Usefulness in contests 20%

## Lectures

Date | Topic | |
---|---|---|

1 | Sep 6 | Introduction & entrance exam (courtesy of Alex Tung) |

2 | Sep 13 | Pengguang Chen: Dynamic programming |

3 | Sep 20 | Ke Bi: Number theory |

4 | Sep 27 | Cyrus Yiu: Data structures I |

5 | Oct 4 | Percy Wong: Data structures II |

6 | Oct 11 | Jeremy Chow: String algorithms |

7 | Oct 18 | Ian Wong: Trees |

8 | Oct 25 | Charlie Li: Square-root decomposition |

9 | Nov 1 | Jason Yik: Fixed-parameter algorithms and searching |

10 | Nov 8 | Alex Tung: Random walks Anson Ho: Fast Fourier Transform (Part I) |

Nov 15 | Congregation for conferment of degrees | |

11 | Nov 22 | Janice Chen: Combinatorial game theory Zuoyang Wang: Numerical algorithms |

12 | Nov 29 | Qingyuan Liu: Computational geometry Anson Ho: Fast Fourier Transform (Part II) |

Dec 19 | Final exam (mini competition; 6pm-10pm, venue: 924B) |

## Homeworks

There will be 8-10 homeworks. Solve assigned problems at the online judges above and submit your programs (together with your ID/handle on the corresponding online judge) to the TA by the deadline. Homeworks are typically released on Thursday and will be due at 23:59 the next Wednesday.

- Homework 1:
~~POJ 1738 due Sep 19~~HDU 2829 due Sep 26 - Homework 2: UVa 11582 due Sep 26
- Homework 3: SPOJ ILKQUERY due Oct 3
- Homework 4: SPOJ DQUERY due Oct 10
- Homework 5: POJ 2774 due Oct 17
- Homework 6: POJ 1741 due Oct 24
- Homework 7: SPOJ COT2 due Oct 31
- Homework 8: UVa 7665 due Nov 7
- Homework 9: CF 26D due Nov 14
- Homework 10: CF Industrial Nim due Nov 28
- Homework 11: UVa 2512 due Dec 5
- Homework 12: A + B Problem due Dec 12