CSCI 3383, Fall 2021
Algorithms
Course Homepage and Syllabus
Prof. Alvarez

Welcome to the CSCI 3383 homepage for Fall 2021! You may use the menu options above to find your way around, if you'd rather not scroll.

---

Who, where, and when

• Instructor

  Prof. Sergio A. Alvarez
  alvarez@bc.edu
  St. Mary's (South), S255
  Office hours (on Zoom - see Canvas for times, link)

• Teaching Assistants (office hours in Fulton 160)

  • Anna Bolger: see Canvas for times

  • Abrar Jalal: see Canvas for times

• Lectures

  The class meets Tu Th at noon in Fulton 250

• Course web site

  The main course site for CSCI 3383 will be on Canvas, at bc.edu/lms. You should check the Canvas site regularly for updates, including supplementary materials and homework assignments. This web syllabus is at http://www.cs.bc.edu/~alvarez/Algorithms/.

  ---

  Textbook

  (available through the BC bookstore)

  S. Dasgupta, C. Papadimitriou, and U. Vazirani.
  Algorithms, McGraw-Hill, 2008
  ISBN-10: 0073523402
  ISBN-13: 978-0073523408

  Additional references

  I've requested that the following book be placed on reserve in O'Neill Library.
  • Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 3rd ed, MIT Press, 2009.

    Additional materials will be made available below on this page at http://www.cs.bc.edu/~alvarez/Algorithms/.

  ---

  What this course is about

  This course focuses on the time and memory requirements of the algorithms (procedures) that are embodied in computer programs. We will discuss both analysis of existing algorithms as well as design of new algorithms with a view toward achieving efficient computational procedures. Course topics include divide and conquer design, fundamental data structures, asymptotic notation, analysis of recurrence relations, greedy algorithms, search, and dynamic programming.

  • The catalog description is available in the Academics area of the CS department's web site.

  Prerequisites / Recommended background

  The prerequisites for CSCI 3383 are programming and data structures at the level of CSCI 1101 and CSCI 1102 (including a good grasp of recursion), and discrete mathematics at the level of CSCI 2243 Logic & Computation (including familiarity with basic proof techniques and mathematical induction). A post-calculus course in probability at the level of CSCI 2244 Randomness & Computation is a co-requisite. Additional background in mathematics and computer science would help but is not required. If you have any questions about prerequisites, please contact me.

  ---

  Grading

  The course grade will be based on homework and exams.

  • Homework (35%)

    Homework will be due on Canvas, in most weeks during the semester. Late homework submissions will receive no credit except in very unusual circumstances, at the discretion of the instructor. On the other hand, my "one free strike" policy will be in effect: each student's lowest homework grade will be dropped, no questions asked. This policy is intended to handle the inevitable unexpected circumstances that can occur occasionally, making it difficult to complete a particular assignment by the deadline. In order to be eligible to pass the course, you must complete and submit at least 2 out of every 3 homework assignments.

  • Midterm Exam and Quizzes (30%)

    One in-class midterm exam will be given. See the schedule below. No make-up exams will be given, so plan ahead. One or more quizzes may also be held, and would contribute to this part of your grade also.

  • Final Exam (35%)

    A cumulative final exam will be held according to the university's standard final exam schedule. Details appear in the Schedule section, below.

  Academic Honesty

  You must individually design and write your own solutions for all assignments. Furthermore, you should explicitly acknowledge any sources of ideas that are not your own; this includes other people, books, web pages, etc. Behavior that is not in the spirit of these guidelines is considered to be academically dishonest. Please also see the university's statement on academic integrity below. If you're unsure about what constitutes academic dishonesty in a particular situation, ask me before proceeding further.

  University statement on academic integrity

  Boston College values the academic integrity of its students and faculty. It is your responsibility to familiarize yourself with the university's policy on academic integrity: http://www.bc.edu/offices/stserv/academic/resources/policy/#integrity

  If you have any questions, always consult your professor. Violations of academic integrity will be reported to your class dean and judged by the academic integrity committee in your school. If you are found responsible for violating the policy, penalties may include a failing grade as well as possible probation, suspension, or expulsion, depending on the seriousness and circumstances of the violation.

  ---

  Assignments, Downloads, and Approximate Schedule of Topics

  (to be updated frequently during the semester)

  Notes:

  Large deviations from the rough schedule below may occur.
  See   http://cs.bc.edu/~alvarez/Algorithms/   for updates.

  Go to end

  Dates/Events	Reading/Homework	Sample Programs/Downloads	Topics
  Aug. 30 - Sept. 3	Read chapter 0 Read sections 1.1-1.2 HW1 due Sept. 9	Notes on induction Notes on asymptotic complexity	Introduction Algorithms Time efficiency Asymptotic notation
  Sept. 6-10 No noon classes on Thurs (university-wide)	1.3 HW2 due Sept. 16	Euclid's GCD algorithm timing program timing results	Modular arithmetic GCD: Euclid
  Sept. 13-17	1.4 HW3 due Sept. 23		Primality Cryptography: RSA
  Sept. 20-24	2.1-2.5 HW4 due Sept. 30	Notes on divide and conquer D & C multiplication: sample run Notes on divide and conquer recurrences	Divide and Conquer Recurrences Multiplication Medians Design examples
  Sept. 27 - Oct. 1	chapter 3 HW5 due Oct. 7	Notes on depth-first search	Graphs Search Backtracking DAGs
  Oct. 4-8	4.1-4.5	Notes on greedy algorithms Notes on disjoint sets and Kruskal MST Prim and Kruskal visualizations (David Galles)	Greedy algorithms Spanning trees (Prim, Kruskal)
  Oct. 11-15 No class on Tu (Mon schedule) Midterm exam Th Oct. 14
  Oct. 18-22	5.1-5.2 HW6 due Oct. 28	Dijkstra visualization (David Galles, U. of San Francisco) Notes on Huffman coding Notes on finite automata	Greedy algorithms Single source shortest paths Dijkstra Bellman-Ford
  Oct. 25-29	6.1-6.6 HW7 due Nov. 4	Combinatorial coefficients nchoosek.cxx Notes on dynamic programming	Dynamic programming Combinations Edit distance
  Nov. 1-5			Dynamic programming Knapsack Transitive closure (Warshall) Shortest paths (Floyd)
  Nov. 8-12	HW8 due Nov. 16	Notes on dynamic time warping	Dynamic programming Time warping
  Nov. 15-19	7.1, 7.2	Notes on linear programming Ford-Fulkerson visualization (Technical U. of Munich)	Linear programming Max flow: Ford-Fulkerson
  Nov. 22-26 Class meets Tuesday only Thanksgiving break Nov. 24-26	7.4-7.5		Linear programming Duality
  Nov. 29 - Dec. 3			Zero-sum games NP-hard problems
  Dec. 6-10 Last class meeting on Th, Dec 9 CSCI 3383 Final Exam: Thurs. Dec. 16 @ 12:30 PM (usual classroom)	chapter 8		Catch up / review