Jump to lecture and assignments

Algorithmic Problem Solving studies the implementation and application of algorithms to a variety of problems. Topics covered will include:

- code performance analysis,
- parsing and formatting text,
- mathematics,
- advanced data structures,
- graph algorithms,
- dynamic programming, and
- computational geometry.

Evaluation is based on participation in programming contests, quizzes, and exams.

Students who would like to develop their programming and algorithmic skills by having a new set of programming challenges presented to them in each class. Basic algorithms and comfort with Java or C++ is a prerequisite.

Students can expect to be challenged and practice understanding and implementing algorithmic ideas outside their skillset. Each class, a new set of problems will be presented to the students and they will be asked to solve the problems. The problems will then be discussed as a class, and each student is expected to contribute to the discussions.

**Instructor:**John R. Zhang**TA:**Bowen Yu

Tuesday and Thursday, 3:30PM-4:45PM, CIWW 101

Friday, 5:10PM-7:10PM, CIWW 101

Steven and Felix Halim's Competitive Programming (**Third Edition**) for $26.99. Also available as an eBook (PDF) for $19.99.

For John: Wednesdays from 9am to 10am **in WWH 328** and Mondays from 7:30pm to 8:30pm in the **13th floor lounge**. Please email me in advance just to give me a heads up.

- Homework: 50%
- Recitation contests: 15%
- Midterm: 15%
- Final Exam: 20%

- Introduction
- Data Structures
- Problem Solving Paradigms
- Graph Algorithms
- Mathematical Problems
- String Processing Algorithms
- Computational Geometry
- Advanced Topics

Codebooks are allowed for standard algorithms, but all of the submitted code must be your own. Collaboration is allowed on all assigments except the midterm and final, but each student must submit his/her own code. Programming assignments will be submitted through Virtual Judge. More information will be posted here for each assignment. If you are enrolled in the course, please register an account on Virtual Judge with username netid_CS480S16. If you are just following the course but are not enrolled, any username will do, but please do not suffix it with _CS480S16.

Each week there will be a programming homework hosted on the Virtual Judge, with links given below. As stated above, please register an account on Virtual Judge with username netid_CS480S16. Your grade will be based on the number of problems solved correctly.

All programs must take their input from standard input, and must write their output to standard output. Java programs must be contained in a public class entitled Main, and they must be in the default package. C++ programs must have a function main, and Java programs must have a method main. If you get Judging Error 1, it means the judging queue is backed up, and you can simply click refresh to be rejudged. If you get Judging Error 2, it means their are server-side communication errors, and your submission should be automatically rejudged when the communication problems are fixed. On Judging Error 2, if you see other people getting submissions through, you may want to resubmit. The student ranking (not used to determine your HW grade) is determined by how quickly you submit each problem (measured from the start of the competition), and how many incorrect submissions you have made (penalized 20 minutes for each incorrect submission).

*Lectures and assignments will be posted here. Based on material used with permission from Bowen Yu, Brett Bernstein and Sean McIntyre.*

- Lecture 1: Introduction, Logistics
- Lecture 2: Approaching Problems
- Lecture 3: Basic Data Structures, Union-Find
- Lecture 4: Bitmasks, Segment Trees
- Lecture 5: Fenwick Trees
- Lecture 6: Complete Search, Greedy Algorithms
- Lecture 7: Divide and Conquer
- Lecture 8: Dynamic Programming
- Lecture 9: More Dynamic Programming
- Lecture 10: Graph Traversal, Topological Sort
- Lecture 11: The Soul of Dynamic Programming
- Lecture 12: Bridges and Articulation Points, MST
- Prim's demo
- Sample code for finding articulation points and bridges (from Competitive Programming 3)

- Lecture 13: The Art of Divide and Conquer
- Lecture 14: Single-Source Shortest Path and All-Pairs Shortest Path
- Lecture 15: Max Flow
- Edmonds-Karp in C/C++ and Java
- Another example of Edmonds-Karp

- Lecture 16: Math in Programming Contests
- Lecture 17: Primes, Combinatorics
- Lecture 18: Probability
- Lecture 19: More Probability
- Lecture 20: Games
- Lecture 21: String Matching, DFAs, NFAs
- KMP (Java)
- More on automata and regular expressions
- Rob Pike's implementation of a mini regex parser from TPOP.
- Lecture 22: Suffix Trees
- Lecture 23: Geometry
- Lecture 24: Sweep Line
- Lecture 25: Simplex Algorithm

- Homework 1: Due 2PM Feb 12
- Homework 2: Due 2PM Feb 19
- Homework 3: Due 2PM Feb 26
- Homework 4: Due 2PM Mar 4
- Homework 5: Due 2PM Mar 11
- Homework 6: Due 2PM Mar 25
- Homework 7: Due 2PM Apr 1
- Homework 8: Due 2PM Apr 8
- Homework 9: Due 2PM Apr 15
- Homework 10: Due 2PM Apr 22
- Homework 11: Due 2PM Apr 29
- Homework 12: Due 2PM May 6