CSCI 310 Advanced Algorithms (Fall 2023)

Contact Information

  • Instructor: Michael Levet (He/Him/His)
    • Contact: lastnamefirstinitial (at) cofc (dot) edu
    • Office: Harbor Walk East 312
    • Location:
      • HWEA 301: 9:55-11:10
      • HWEA 302: 11:20-12:35
      • Zoom- Remote Synchronous, for those who wish to participate remotely.
    • Office Hours (Tentative):
      • Monday/Wednesday: 9:45-10:45 AM (Zoom)
      • Tuesday/Thursday: If I am in my office, please feel free to knock.
      • By appointment
  • Syllabus
  • Official Course Textbook
  • Google Forms: (You must be signed in to your CofC account to access these forms.)

Announcements

  • 12/3: I am working to have everything graded no later than 12/6 at the end of the day. I will try to have things graded sooner, if at all possible.
  • 11/26:
    • I am moving my office hours tomorrow to 11/28 from 10:45-11:45 over Zoom.
    • Class on Tuesday and Thursday will be cancelled. Please use this time to work on the remaining assignments this semester.
    • If you have not already done so, please consider completing your Instructor Evaluations for this course. I appreciate constructive feedback and will use your comments to improve the course the next time I teach it.
  • 11/21:
    • RQ2 has been graded. Based on Standards 1-24 and the Engagement standard (which anyone who completed the Syllabus quiz will receive), here are some grade statistics:
      • Average: 20 standards at least once, and 14.57 standards twice
      • First Quartile Cutoff: 16 standards at least once, and 10 standards at twice.
      Generally, folks are doing well!
    • Progress reports are forthcoming.
    • The requisite grade to pass this course is a D- or better. The official cutoff on the syllabus is 18 standards. I will lower that to 15 standards. I recognize the impact of this course on your progress towards graduation, especially with it only being offered in the Fall.
    • If you are concerned about your grade, please make sure to take advantage of HW13, the retake tokens, Quizzes 19-20, and the final requizzing period.
  • 11/12:
    • Class is cancelled on 11/14. I will plan to be in my office from 10:45-11:45 for extra office hours.
    • Office hours will be cancelled on 11/20 due to RQ2.
  • 11/9:
    • Quizzes over Standards 21-23 have been posted. They are due on 11/15 at 8 PM. I will grade these ASAP, so you have feedback before RQ2 ends.
    • RQ2 will run 11/16-11/21, covering Standards 12-23. Class and office hours will be cancelled those days.
    • We will have quizzes on Standards 19-20 11/27 through 12/1 at 8 PM.
    • The Final Reuizzing Period will open on 12/6 and run through Monday 12/11 at 3 PM. Note that CofC has the 9:55 section's final exam time at 12/7 10:30-12:30, and the 11:20 section's final exam time on 12/11 from 1-3.
  • 11/5:
    • HW13 and HW14 have been posted. You will be able to work on HW13 Standards 25-27 now, and we will cover Hashing on Thursday. HW14 (Standard 28) is one of the more abstract and challenging standards in the class. You will learn a lot by attempting it. However, I would only recommend attempting it if you are otherwise in reasonably good shape in the class and want a challenge.
    • I have an old problem set on the Polynomial-Time Hierarchy. This generalizes NP in the direction of quantifiers. If you are interested in what is out there beyond P and NP, this should give you a taste. I'm happy to discuss this problem set, but it is not required and will not be graded. This is purely for enrichment.
  • 11/3: Quizzes over Standards 14-18 will run from November 4 through November 10 at 8 PM.
  • 11/2: PS12 over Divide and Conquer is now posted. I have pushed the due date to 11/14. As promised, it is intentionally short.
  • 10/30: The Quizzes for Standards 12-13 will run from November 1 through November 4 at 8 PM.
  • 10/26:
    • PS10 is now posted. Recall that it is due on 11/7 at 8 PM. I recommend prioritizing Standards 21 and 23. As we will need to have quizzes over PS10 before RQ2, do be aware that extension requests might mean that you could be taking the quizzes without feedback on the content beforehand. Please plan accordingly.
    • PS12 is now posted. Recall that it is due on 11/18 at 8 PM if you would like feedback. See the announcement on 10/8 for full details.
  • 10/22:
    • The retake token Google form is now open (see the link above). The form will close on Monday November 27 at 8 PM, so that I can process everything in a timely manner and so that you all will have time to take your quizzes. This is a firm deadline; there will be no extensions. You will have your RQ2 grades reasonably before then. If you submit corrections and reflections reasonably ahead of time, and they are not sufficient, I will let you know so that you have time to fix them and resubmit. Note that if you submit near the deadline, you may not have time to iterate on your corrections and reflections. Please plan accordingly.
    • Quiz 11 over Standard 11 will open on October 26, and it is due on October 28 at 8 PM.
  • 10/15: HW7 has been graded. The cutoff for Proficiency on Standard 11 was >= (Progress, Proficiency, Proficiency).
  • 10/12: In light of it being midterm week, I have extended HW7 to 10/14 at 8 PM. Please note that my availability to email tomorrow and Saturday may be limited. I hope this helps!
  • 10/8: Here is the tentative gameplan for HW for the rest of the semester. I will keep you posted if there are any changes (such changes would be in your favor).
    • HW9 over runtime analysis will be due on October 31 at 8 PM.
    • HW10 over dynamic programming will be due on November 7 at 8 PM.
    • Originally, I had intended Standard 24 on designing dynamic programming algorithms to have two attempts, both on HW. You would only need to demonstrate proficiency once for full credit. I propose the following modification. There will only be one HW (HW11), but you can revise it. The first attempt will be due on November 18. If you are happy with your grade, then there is nothing more to do. Otherwise, you can submit revisions for full credit by December 4 at 8 PM (the day before Reading Day). You may still submit HW11 on December 4, even if you do not submit it on November 18. However, you won't be able to further revise it if you go this route.
    • HW12 on divide and conquer will be due on November 13 at 8 PM. This will be short.
    • Requizzing Period 2 will run from November 16-21, tentatively covering Standards 12-23. Class will be cancelled those days.
    • HW13 on the basics of P vs. NP and hashing will be due on November 30 at 8 PM.
    • HW14 on Standard 28: Structure and Consequences of P vs. NP will be due on December 4 at 8 PM.
    • For standards 25-29 (P vs. NP and hashing), you will only need to demonstrate proficiency once. There will be two opportunities to do so: HW and the final requizzing period.
  • 10/6: HW8 is posted. It is due on 10/25 at 8 PM. I have left some comments and hints aimed at reducing/streamlining your workload for this assignment. Please do read over them and ask if something is not clear. I don't intend for this assignment to be overly painful, but it is possible to create more work for yourself than necessary. So please do read over the hints and suggestions.
  • 10/2:
    • Quiz 3 grades have been posted.
    • HW5 grades are posted. The cutoff for Proficiency on S4 required satisfying all of the following: (i) Demonstrated Progress or better on Problems 2-4, and (ii) Proficiency/Outstanding on at least two problems.
    • Midterm grades are due to the university soon (before Requizzing Period 1). I will submit midterm grades based on the snapshot today, for the number of standards on which folks have demonstrated proficiency at least once. In my experience, the first quartile cutoff is a clear threshold for progress to earn a C- or better. The first quartile cutoff today is proficiency on >= 4 standards at least once. Note that a D- or better will not prevent you from graduating on its own. Thus, I will submit midterm grades as follows.
      • A: 7 or 8 standards at least once.
      • B: 5 or 6 standards at least once.
      • C: 3 or 4 standards at least once.
      • D: 2 standards at least once.
      • F: Otherwise.
      If you are concerned about your grade, there is a lot of room to improve between now and the end of Requizzing Period 1. Your grade after Requizzing Period 1 will provide a much clearer indication of whether you are on track to pass. Please don't hesitate to reach out if you have any questions or concerns.
  • 10/2:
    • HW7 over Standard 11 has been posted and is due on 10/12 at 8 PM. You all have enough to start working on Problems 2 and 4. We will go through a reduction proof tomorrow in class, after which, you will be able to start on Problem 3.
    • Quizzes over Standards 4, 5, and 6 (HW4 and part of HW5) will run 10/5 through 10/8 at 8 PM. I will work to have at least Standard 6 on HW5 graded by Friday 10/6, if not earlier.
    • Quizzes over Standards 7, 8, 9, and 10 (HW5 and HW6) will run 10/11-10/15.
    • Requizzing Period 1 will run 10/18-10/21. It will cover Standards 1-11. Note that this will be your first timed assessment for Standard 11. There will be a second timed assessment (date TBA) after I get this first one graded.
    • Class will be cancelled on 10/19. I will be out of town 10/18-10/20 for a workshop on Broadening Participation in Computing, hosted by the Computing Research Association. This workshop will introduce evidence-based practices for broadening participation in computing, that I will be bringing back to share with the department. I will not be responsive to email during business hours, so that I can focus on the workshop. However, I will be checking email at night and will do my best to respond in a timely manner.
  • 9/21:
    • HW3 grades have been posted. The cutoff to earn a Demonstrated Proficiency or better on HW3 was earning on (Q2, Q3, Q4): >= (PR, PR, T) or >= (T, T, PR).
    • The Quiz over Standard 3 opens on 9/28 and closes on 9/30 at 8 PM.
    • HW6 opens on 9/22 and is due on 10/5 at 8 PM.
  • 9/10: Quiz 1 and HW2 grades have been posted. The cutoff to earn a Demonstrated Proficiency or better on HW2 was: (i) earning a Demonstrated Progress (PR) or better on all questions, and (ii) earning a Demonstrated Proficiency (P) or better on three of the four questions.
  • 9/8:
    • HW4 is now posted. It is due on 9/25 at 8 PM. Please note that this homework is not intended to take two weeks. As office hours will be cancelled the week of 9/18 (due to my being at a conference), I would like to make sure you all have time to ask me questions before turning in the HW. You have all the tools to start on HW4.
    • HW5 is scheduled to open on 9/12 at 1 PM. It is due on 9/29 at 8 PM. You will be able to start on this homework after class on Tuesday 9/12. Again, this should not take two weeks to do, but I want to make sure you have time to ask me questions.
    • Quiz 2 over BFS/DFS will open on 9/14 and close on 9/16 at 8 PM.
  • 9/6: HW1 grades have been released. The cutoff for Demonstrated Proficiency (Full Credit) on HW1 required getting (i) Demonstrated Progress or better on Problem 2, and (ii) Demonstrated Proficiency or better on both Problems 3 and 4. For HW1, you may revise Problems 3 and 4, and resubmit them to OAKS by 9/11 at 8 PM for full credit on those problems. For each i \in {3,4}, if it is to your benefit, I will replace your original score on Problem i with that of your revision. I will then update your HW1 grade accordingly. Note that you must have submitted HW1 to be eligible for this. Please also note that your revisions will likely not be graded quickly. I will get them graded before the first Requizzing Period, but I otherwise make no promises about when I will get to them. Additionally, please do not expect this for future assignments.
  • 9/4:
    • PS3 is now posted. It is due on 9/13 at 8 PM.
    • Quiz 1 over Standard 1- Induction, will open on 9/7 and close on 9/9 at 8 PM. You may take it in any 45 minute window (scaled for students with disability accommodations) as you wish. Note that if you start on 9/9 at 7:30 PM, OAKS may cut you off right at 8 PM. I will not accept the quiz via email in this case. Please plan accordingly.
    • There is a typo on HW2 (Problem 3 in Section 3.2). The question asks about DFS, but part (c) incorrectly references BFS. Instead, part (c) should reference DFS. I have uploaded a revised HW2 to OAKS, for clarity.
    • Recall that I will be out of town from 9/15-9/21. As a result, I will be recording lectures this weekend on 9/9 and 9/10 from 2:30-3:45 both days. I have reserved Harbor Walk West 217, in case folks want to attend in-person, and I'll also have Zoom open (use the usual Zoom room for class). If you would like to ask questions during the lectures, this is the opportunity. Nobody is obligated to attend on 9/9 or 9/10, but you are responsible for watching these lectures (either live or recorded). Note that Harbor Walk West is usually locked. You can either call the security office at 843.953.7390 or they can call Public Safety at 843.953.5609 to radio the guard.
  • 8/30: While I fully intend to hold office hours tomorrow, that is very dependent on whether I have electricity and internet tomorrow. If you log in to Zoom tomorrow, and I am not there at the usual time, please assume either my power or internet has gone out. If this happens, I'll communicate as soon as I'm able. On a similar note, please prioritize your own safety during this hurricane. Get to safety, and then ask for an extension if you need one. But please get to safety first.
  • 8/26: I will be out of town from 9/15-9/22 for a conference in Italy. While we will not be meeting those days, I will be recording lectures and posting them. You all are responsible for watching these lectures. With that said, I recognize the value in being able to ask questions in real-time. I will be recording these lectures over Zoom on Saturday 9/9 and Sunday 9/10, 2:30-3:45 both days. I have requested a classroom for those days, in case anyone wishes to attend in-person. Nobody is obligated to attend in-person (provided I can get a room) or via Zoom in real-time, but you are welcome to do so. I'll keep you all updated as I have more details. Also, office hours will be cancelled the week of 9/18. Please feel very welcome to email me, but please be aware that I may be slower to respond than normal.
  • 8/24: HW2 is now posted. It is due on 9/6 at 8 PM. We will finish covering the material for HW2, hopefully on Tuesday 8/29.
  • 8/23: There are many tools to compile LaTeX documents as PDFs. You will need to find one that works for you. I use MikTeX. Overleaf is another option. There are others-- I don't have particularly strong feelings; if another option works better for you, please feel free to use that!
  • 8/22:
  • 8/5:
    • The Syllabus Quiz will open on 8/21 at 12:01 AM and is due on 9/2 at 8 PM. One function this assignment serves is to provide a low-stakes way to get set up with LaTeX, as well as to ask questions about using LaTeX. Please note that during quizzes, you may wish to include images in the PDF. It is worth figuring out how to do this before you wish to do so in a timed environment.
    • HW1 will open on 8/22 at 12:45 PM. It is due on 9/2 at 8 PM. This assignment is intended to be doable in a week; the long deadline is intended to accommodate folks who add the class late.
  • 4/4: Website created.