Algorithmic Problem Solving

CSCI-UA.0480-004

Announcements

All announcements will be made over Piazza. If you do not have access, email the instructor.

Jump to lecture and assignments

Description

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.

Who should take this course

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.

Expectations

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.


Contact

Date, time, location

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

Recitation (Required)

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

Programming Team Mailing List

Sign up here.

Textbook

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

Office hours

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.

Grading

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

Syllabus

  1. Introduction
  2. Data Structures
  3. Problem Solving Paradigms
  4. Graph Algorithms
  5. Mathematical Problems
  6. String Processing Algorithms
  7. Computational Geometry
  8. Advanced Topics

Homework Policy

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.

Programming Homework Instructions

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).


Classes

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

  1. Lecture 1: Introduction, Logistics
  2. Lecture 2: Approaching Problems
  3. Lecture 3: Basic Data Structures, Union-Find
  4. Lecture 4: Bitmasks, Segment Trees
  5. Lecture 5: Fenwick Trees
  6. Lecture 6: Complete Search, Greedy Algorithms
  7. Lecture 7: Divide and Conquer
  8. Lecture 8: Dynamic Programming
  9. Lecture 9: More Dynamic Programming
  10. Lecture 10: Graph Traversal, Topological Sort
  11. Lecture 11: The Soul of Dynamic Programming
  12. Lecture 12: Bridges and Articulation Points, MST
  13. Lecture 13: The Art of Divide and Conquer
  14. Lecture 14: Single-Source Shortest Path and All-Pairs Shortest Path
  15. Lecture 15: Max Flow
  16. Lecture 16: Math in Programming Contests
  17. Lecture 17: Primes, Combinatorics
  18. Lecture 18: Probability
  19. Lecture 19: More Probability
  20. Lecture 20: Games
  21. Lecture 21: String Matching, DFAs, NFAs
  22. Lecture 22: Suffix Trees
    • Suffix tree implementations: Java, C++
  23. Lecture 23: Geometry
  24. Lecture 24: Sweep Line
  25. Lecture 25: Simplex Algorithm

Homeworks

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