Overview

CSCI 3383 is the last part of a sequel (together with CSCI 2243 & CSCI 2244) that provides the mathematical background for upper-division courses in the theory field. Or as you wish, it helps to crack the code interview.
Concepts: asymptotic (“Big Oh”) notation, design and analysis of algorithms, algorithmic paradigms, basic data structures, randomized algorithms, graph algorithms, and limitations of the algorithmic techniques (NP-completeness).
Applications: communication networks, ensuring social distancing, primality testing, efficient look-up tables, operating systems, and other fields.

Schedule

Theme Date Topic Materials Assignments

Module I: Algorithm Analysis

Notation and Analysis
[Week 1-2]		 Tue, Aug. 29 Lec. 1: Introduction
What: design and analysis
How: syllabus, logistics
Thu, Aug. 31 Lec. 2: Basic Algorithm Analysis
Proof: Induction
Performance: Time complexity
Fri, Sep. 1 No Discussion
hw0 out
Tue, Sep. 5 Guest Lecture: How to Prepare for the Coding Interview
Guest: Fabio Costa (@Google)
Thu, Sep. 7 Lec. 3: Potential Method
  • [CLRS] Chap. 17.3, 31.2
Fri, Sep. 8 Reviews: Proofs, Asymptotic notation, Information
hw0 due
hw1 out

Module II: Algorithm Design

Design Paradigms
[Week 3-6] 		Tue, Sep. 12 Lec. 4: Greedy
What: linear chain
How: (by data structure) set, array, graph (MST)
Why: Matroid
Thu, Sep. 14 Guest Lecture: How to Do Well during the Coding Interview
Guest: Shang-En Huang (IOI 2007🥇)
Algorithmic Thinking
Fri, Sep. 15 Reviews: Greedy and Potential
hw1 due
hw2 out
Tue, Sep. 19 Lec. 5: Divide and Conquer I
Array: binary search, merge sort, Karasuba
Master theorem
Thu, Sep. 21 Lec. 6: Divide and Conquer II
Tree: balanced BST construction
Geometry: convex hull, closest pair of points
  • [CLRS] Chap. 33.4
Fri, Sep. 22 Reviews: Divide and Conquer
hw2 due
hw3 out
Tue, Sep. 26 Lec. 7: Dynamic Programming I
Array: coin changes, longest increasing subsequence, longest common subsequence
  • [CLRS] Chap. 15
  • [M] Chap. 8
  • [LC] 198, 5, 152
Thu, Sep. 28 Lec. 8: Dynamic Programming II
Matrix: pair of sequence, matrix, subset (sum, knapsack)
Fri, Sep. 29 Reviews: Dynamic Programming
hw3 due
hw4 out
Tue, Oct. 3 Lec. 9: Dynamic Programming III
Graph: shortest path for a single pair (Dijkstra's) and all pairs (Floyd–Warshall's)
  • [CLRS] Chap. 15, 25.2
  • [LC] 1049, 72, 62
Midterm
[Week 6-7]		 Thu, Oct. 5 Lec. 10: Midterm Review
hw4 due (Fri)
practice midterm out
No Class (Happy Fall Break)
Thu, Oct. 12 Midterm Exam (in class)
Fri, Oct. 13 Exam Walkthrough
Randomized Algorithms
[Week 8-10]		 Tue, Oct. 17 Lec. 11: Probability, Randomness in Computation
Types: Las Vegas and Monte Carlo
Maths review
  • [CLRS] Chap. 5, Appendix C
  • [M] Chap. 6
Thu, Oct. 19 Lec. 12: Primality Testing
  • [CLRS] Chap. 31.8
Fri, Oct. 20 Algorithms: 1-Sided Error Reduction
hw5 out
Tue, Oct. 24 Lec. 13: QuickSort, Verifying Polynomial Identities
  • [CLRS] Chap. 7, 30.1
  • [M] Chap. 10
Thu, Oct. 26 Lec. 14: Chernoff Bounds and Applications
Fri, Oct. 27 Quick Select
hw5 due
hw6 out
Tue, Oct. 30 Lec. 15: Hashing
Hash function, collision handling
  • [CLRS] Chap. 11
  • [M] XI (Hash Table)
  • [LC] 49, 347, 75
Thu, Nov. 1 Lec. 16: More on Sorting
Comparative: lower bound
Non-comparative: bucket sort and radix sort
  • [CLRS] Chap. 8
Fri, Nov. 3 Applications: Hashing and Sorting
hw6 due
hw7 out
Graph Algorithms
[Week 11-12] 		Tue, Nov. 7 Lec. 17: Graph Basics
Types: directed, weighted, connectivity pattern
Representation: adjacency matrix/list
Thu, Nov. 9 Lec. 18: Graph Traversal
Whatever-first-search: BFS and DFS
Connectivity problems
  • [CLRS] Chap. 22.2, 22.4
  • [M] XI (Topological Sort)
Fri, Nov. 10 Applications: BFS, DFS
hw7 due
hw8 out
Tue, Nov. 14 Lec. 19: Topological Sorting
DFS-post-order, Kahn's algorithm
Connectivity analysis
  • [CLRS] Chap. 24.3
Thu, Nov. 16 Lec. 20: Bipartite Graphs and Dijkstra's Algorithm
  • [CLRS] Chap. 24.3
  • [M] XI (Dijkstra)
  • [LC] 1631, 1584, 743
Fri, Nov. 17 Applications: Shortest Paths
NP-Completeness
[Week 13-15] 		Tue, Nov. 21 Lec. 21: Efficiently Verifiable Problems
P, NP (P-verifiable), AP, EXP
NP-completeness: SAT
  • [CLRS] Chap. 34
 hw8 due
hw9 out
No Class (Happy Thanksgiving)
Tue, Nov. 28 Lec. 22: Approximation Algorithms I
Minimum vertex covering: double cover
Maximum clique, maximum independent set
  • [CLRS] Chap. 35
Thu, Nov. 30 Lec. 23: Approximation Algorithms II
Maximum cut
3-coloring
  • [CLRS] Chap. 35
Fri, Dec. 1 Algorithms: More on Approximation
hw9 due
hw10 out
Tue, Dec. 5 Lec. 24: KNAPSACK and DP Review
Classic: fractional, 0/1
Extension: Bounded, unbounded
  • [CLRS] Chap. 34
Final
[Week 15-16]		 Thu, Dec. 7 Lec. 25: Material Review
hw10 due (Fri)
practice final out
Tue, Dec. 19 Final Exam (12:30pm)


Staff & Office Hours


Instructor
TA
TA
Name Discussion-based office hours
@245 Beacon Rm. 123
Peiyu Fri 12-12:50pm
Daniel Fri 1-1:50pm
Shameer Fri 2-2:50pm
Jo Fri 3-3:50pm
Name Office hours
Ilya Mon/Wed 4:15-5pm @ 245 Beacon Rm. 428F
Donglai Tue/Thu 4:15-5pm @ 245 Beacon Rm. 528F
Peiyu Mon 2-3pm @ 245 Beacon Rm. 122
Jo Tue 2-3pm @ 245 Beacon Rm. 122
Shameer Thu 11-12pm @ 245 Beacon Rm. 122
Daniel Thu 12-1pm @ 245 Beacon Rm. 122
  • Office hours are shared with prof. Volkovich's section 1.
  • Office hours will take place in person (or Zoom if needed).
  • Donglai will hold additional one-on-one AMA office hours Mon/Wed 4:15-5pm (15-min by appointment)


Course information

Please feel free to reach out if you need help in any form.

1. Course Format

  • Discussion-based OH: To better help you crack the coding interview, the discussion-based OHs are strongly encouraged!
  • Piazza: A Piazza page has been established to help with discussion outside of class. Any question that is not private and might be of interest to other students in the class should be posted to Piazza. Please note that the staff might ask you to post your questions on Piazza if we feel it will be beneficial to other students.

2. Grading: 10 homework (40%) + 1 midterm (25%) + 1 final exam (35%) + extra credit

  • Homework (40%)
    • There will be 10 weekly assignments HW1 - HW10, published in Canvas ("Files") every Friday and due at 10:00AM (accepted until 10:59 AM) the following Friday on Canvas ("Gradescope").
    • Late assignments will receive no credit. However, the lowest homework score will be dropped. Therefore, each homework assignment is worth 4% of your final grade. Unfortunately, exceptions can only be made for emergency situations (e.g. family or medical), and should be requested with as much notice as possible and/or be evidenced by documentation. Please plan accordingly and/or be ready to provide documentation of medical appointments, etc. Nonetheless, there will be a penalty for submissions that do not contain a reasonable attempt to solve all four questions. HW0 - is an optional assignment and worth 2%.
    • We encourage you to type the submitted assignments. In particular in LaTeX (see HW0), but not limited to. A typed assignment will receive 5 extra points (out of 100 for an assignment). Nonetheless, you can still get the full score by submitting a readable (scanned) handwritten solution. Your feedback is encouraged, 2 extra points will be awarded for each typographical error and 10 extra points for each mathematical error you call to attention. Only the first person to spot an error will receive the extra points.
  • Midterm (25%) and Final Exam (35%) One midterm and a cumulative final exam will be given. A large fraction of the questions on these exams will be similar to homework and class problems or very slight variations/extensions. Thus a good way to study is to make sure you know how to solve these problems.
  • Optional Extra Credit
    • Course Evaluation (1%) The course evaluations are important to us and will allow you to earn extra 1% to your final grade. Students will receive this point by submitting the final course evaluations and uploading the receipts from the course evaluations to Gradescope as a separate assignment.
    • Bonus Question on Homework Assignments: some homework assignments will have additional questions, allowing you to earn extra credit. This way your homework grade can exceed 100%!
  • Philosophy: In any humanities or social science class, you must write clearly and concisely to get your point across. It is not sufficient that a correct argument appears somewhere in your answer, if it is also accompanied by incorrect or faulty reasoning. The same applies for this course: your responses must be clear, concise, and correct to receive full credit.
  • Re-grading Policy:
    • If a student feels that credit has been inappropriately allocated, then they should ask for a regrade. The student should submit a request via Gradescope along with an explanation of what was incorrectly graded and why. Regrade requests must be made within one week of an assignment being graded.
    • No oral and/or e-mail regrade requests will be accepted
    • Students are cautioned that they have the possibility of both gaining and losing points (i.e., if the regrade determines that the answer was more incorrect than marked). Students are reminded that accuracy alone is not sufficient; the answer should also be clear and concise.
  • Chart: If your final raw score exceeds the threshold for grade X, your final letter grade will be X or better. The actual thresholds will be determined after the final exam, but will be no higher than what appears below. (E.g., a score of 87% or above is guaranteed to receive a B+ or better.) A failing grade on the final exam is grounds for failing the course.
    A A- B+ B B- C+ C C- D+ D D-
    ≥96 92 87 83 80 77 73 70 67 63 60

3. Academic Integrity

  • Unless otherwise specified in an assignment, all submitted work must be your own, original work. If you are referencing others' work, put it in quotes! If you are directly quoting, or building on others' writing, provide a citation.
  • Students are encouraged to collaborate (except when taking exams). Please use Piazza to this effect and also to find other students to work with on assignments, i.e., create study/homework groups. However, when turning in work that benefited from a collaboration, the student must state that clearly. Students must write their solutions on their own and may not look at any other student’s write-up.
  • Failure to comply with these guidelines will be considered a violation of the University policies on academic integrity. Please consult these policies.

4. Exam Conflicts
  • Everyone is expected to take all exams at the scheduled times. The times of the exams can be found on the course schedule. Alternate exams will be given only in very exceptional cases such as serious illness or a similarly serious family emergency.
  • In a case of a conflict due to a college sponsored event (such as participation in a sponsored sports event or a competition) a college official in charge of the event should contact the instructor at least three weeks in advance to determine how the missing grade will be made up.
  • We will post a form prior to each exam for notifying us of your conflicts. Make sure to fill out the form before the posted deadline.
  • Note that end-of-term transportation matters, such as the availability of inexpensive air tickets before the end of the term, are not acceptable reasons for an absence.

5. Wellness and Accommodations
  • Your health and well-being are important. Please be aware that the university provides a range of counseling and support services for students struggling with mental health issues.
  • If you have a disability, some aspects of this course, the assignments, the in-class activities, and the way we teach may be modified to facilitate your participation and progress. Please contact the Connors Family Learning Center or the Disability Services Office to request an accommodation.

© 2023 Boston College. Website based on a template from HTML5 Up and Andrew Owen's course at U. Michigan.