CSCI 3104 Algorithms (Summer 2021)

Contact Information

  • Instructor: Michael Levet (He/Him/His)
    • Contact: firstname (dot) lastname (at) colorado (dot) edu
    • Office Hours: (Zoom)
      • Tuesday 6/1 4:30-6:30 PM
      • Week of 6/7 onwards: Monday and Tuesday 3-4 PM, and By Appointment
      • 7/12: Cancelled.
  • Graduate Teaching Assistants:
    • Ethan Hobbs: Office Hours on Wednesdays, 2-4 PM (Zoom)
    • Vimal Kakarapathi: Office Hours on Tuesdays and Thursdays, 2:00-4:00 PM (Zoom)
    • Sagi Shaier: Office Hours Wednesdays and Fridays 8:00-9:00 AM (Zoom)
  • Undergraduate Course Assistants:
    • Helen Kim: Mondays 1-2 PM, Tuesdays 8-9 AM and 4-6 PM, Thursdays 3-5, and Fridays 4-5 PM (Zoom)
      • Office Hours Cancelled for Monday 6/14.
    • Seok Jun Song: Mondays 5-7 PM, Tuesdays 5-7 PM, and Saturdays 10 AM-1 PM (Zoom)
      • Seok's first day of office hours will be on Saturday 6/5.
      • Seok's office hours on Monday 6/14 will be cancelled. He will instead hold office hours on Wednesday 6/16 from 5-7 PM.
  • Syllabus
  • Lectures:
    • Section 400: MTW 9:25-10:45 (ECCS 1B28)
    • Section 401: MTW 9:25-10:45 (Zoom)
    • Section 410: MTW 11:20-12:40 (ECES 1B28)
    • Section 411: MTW 11:20-12:40 (Zoom)
  • Recitations:
    • Section 403 (Vimal): Thursday 9:25-10:45 (Zoom)
    • Section 405 (Vimal): Friday 9:25-10:45 (Zoom)
    • Section 413 (Sagi): Thursday 11:20-12:40 (Zoom)
    • Section 415 (Ethan): Friday 11:20-12:40 (Zoom)
  • Google Forms: (You must be signed in to your CU Boulder account to access these forms.)

Announcements

  • 8/4: PS14 grades are now posted. The cutoff for a S30 Overall Score >= 3 required getting at least a 2 on all problems, and at least a 3 on two or more of the problems.
  • 8/3:
    • PS13 grades are now posted to Gradescope. The cutoffs for a S31 Overall Score >= 3 required getting at least a 2 on each of Problems 5-7, as well as at least a 3 on at least two of Problems 5-7.
  • 8/2:
    • We are working to get everything graded as quickly as possible. Our goal is to have everything graded by Tuesday evening, but it may be Wednesday early afternoon until we finish all of our grading.
    • Progress reports will be posted once we have all of our grading done, to help you all gauge what you want/need to attempt on the final requizzing period.
    • Solutions for PS12, PS13, and PS14 will be up no later than tomorrow evening.
    • The logistics for the final requizzing period are the same as for RQ1 and RQ2. The Final Requizzing Period will be held from 8/4 at 8 AM through 8/6 at 2 PM.
    • After we grade the final requizzing period, we will release grades on Gradescope. You all will have roughly a day to check things over. I want to ensure that the grades I submit to the registrar are accurate. I will follow up with more on these logistics once grades are released.
    • The last day of office hours will be tomorrow 8/3.
    • If there is anything I can do to support you all between now and the end of the semester, please don't hesitate to reach out!
  • 7/29:
    • RQ2 grades have all been posted.
    • The retake token form will close on Saturday 7/31 at 4 PM.
    • PS14 has been extended to Monday 8/2 at 8 PM.
    • All retake token quizzes must be completed by then. You will hear back in time to take your retake token quiz before this deadline.
  • 7/27:
    • PS12 grades have been posted. Revisions for PS12 are due on 8/1 at 8 PM to the PS12 Revisions assignment on Canvas. Note that you must have made a good-faith effort at PS12 to be eligible for revisions.
    • We are working on grading RQ2 and will release grades as we have them. If you wish to use a retake token on Standards 1-13, I strongly encourage you to submit your corrections and reflections sooner than later. That way, if you need to revise your corrections and reflections, you will have time to resubmit them. Once the corrections and reflections Google form closes, new or revised corrections and reflections will not be accepted.
    • Solutions for RQ2- Standards 19-25 will be released tomorrow afternoon.
  • 7/24: PS11 grades have been posted.
    • The cutoffs for getting an S22 Overall Score >= 3 requried getting a 3 on both Problems 2 and 3, or getting a 4 on either Problem 2 or 3 and a 2 on the other. (So scores of (3, 3), (4, 2), or (2, 4)).
    • The cutoffs for getting an S23 Overall Score >= 3 requried getting a 3 on both Problems 4 and 5, or getting a 4 on either Problem 4 or 5 and a 2 on the other. (So scores of (3, 3), (4, 2), or (2, 4)).
  • 7/21:
    • Today was our last day of lecture. My intent is to return lecture time to you all, so that you all can work on problem sets, quizzes, retake tokens, etc.
    • This will be our last week for recitation.
    • PS10 solutions are posted to Canvas, and PS10 grades are posted to Gradescope. The cutoff for a S19 Overall Score >= 3 was a 3 on both Problems 2 and 3.
    • PS11 solutions will be up sometime Friday after 8 PM.
    • Solutions for Quizzes 14-18 will be up sometime Saturday evening.
    • We are intending to have PS11 and Quiz 14-18 grades posted no later than the end of the day on Sunday (and hopefully sooner).
  • 7/19: PS13 is now available and is due on 7/30 at 8 PM. PS14 is also available, and it is due on 8/1 at 8 PM.
  • 7/18: Grades for PS9, Quiz 12, and Quiz 13 have been released. The cutoff for a S16 Overall Score >= 3 on PS9 required a score of 3 on both Problems 4 and 5.
  • 7/16:
    • PS12, covering S26, is now posted. The due date is 7/24 at 8 PM. We will grade S26, and then there will be an opportunity to revise and resubmit the entirety of S26 after receiving initial feedback. You must make an initial and good-faith effort attempt in order to be eligible for revisions. Note that these revisions do not count towards your retake tokens.
    • Quizzes over S14-18 open on Monday and close Friday 7/23 at 8 PM. We will work to have grades back by Sunday 7/25 in the evening.
    • RQ2 will open on Sunday 7/25 at 10 AM and close on Tuesday 7/27 at 2 PM. The logistics are similar as RQ1.
      • RQ2 will cover S14-25.
      • As this will be the second attempt at S19-25, we will release solutions for these standards.
      • Class on 7/26 and 7/27 will be cancelled.
      • Office hours will be cancelled for the duration of RQ2. My office hours will also be cancelled on Tuesday afternoon, so that I can migrate the quizzes to Gradescope. The other TAs and CAs will have their scheduled office hours as usual, starting after 2 PM on Tuesday.
      • As a reminder, the quizzes are individual efforts. Collaboration on the quizzes is strictly prohibited.
    • There will be quizzes over S19-25 open from Wednesday 7/28-Sunday 8/1. We will work to have grades for these standards out from RQ2 ASAP.
    • For Standards 26-31, you will only need to demonstrate proficiency once in order for these standards to count towards your final grade. There will be two attempts: HW and the Final Requizzing Period.
    • PS13 covering Standards 26-29 (P vs. NP) and 31 (Hashing) will be released either on Monday or Tuesday 7/19-7/20. It will be due on Friday 7/30. I will keep this problem set intentionally short.
    • PS14 covering Standard 30 (Structure and Consequences of P vs. NP) will be released also likely be released on Monday or Tuesday 7/19-7/20. It will be due on Sunday 8/1. PS14 is designed to provide practice with reductions and the simulation technique.
    • The Final Requizzing Period will be held from 8/4 at 8 AM through 8/6 at 2 PM. The logistics will be identical to RQ1 and RQ2. The Final Requizzing Period will cover Standards 1-31.
  • 7/15:
    • PS11 is now posted. It is due on Wednesday 7/21 at 8 PM.
  • 7/13:
    • PS10 is now posted. It is due on Saturday 7/17 at 8 PM.
    • The Retake Token Form is now open. Please see under the Google Forms header. This form will close within 24 hours after grades for RQ2 are released or July 31 at 8 PM, whichever comes first.
  • 7/11:
    • Solutions for RQ1- S11, S12, and S13 have been posted to Canvas.
    • Grades for RQ1- S11 and S13 have been posted to Gradescope.
    • I will be cancelling my office hours on 7/12, so that I can work on finalizing grades for RQ1.
  • 7/9:
    • Quizzes for Standards 11, 12, and 13 open on 7/12. They close 7/16 at 8 PM.
    • Solutions for RQ1- S11-13 will be posted no later than Sunday evening. We are working to get these three requizzes graded ASAP.
    • PS10 will likely be posted Monday evening. It will be due on Saturday 7/17 at 8 PM.
  • 7/5:
    • Solutions for Quizzes 6-10 and PS8 are now on Canvas.
    • Grades for Quizzes 6, 8, and 9 were posted to Gradescope on 7/3.
    • Grades for PS7, PS8, Quiz 7, and Quiz 10 are posted to Gradescope as of today.
    • PS7: The cutoff for a Standard 11 Overall Score >= 3 involved: Problem 2 Score >= 2, Problem 3 Score >= 3, and Problem 4 Score >= 3.
    • PS8: The cutoff for a Standard 12 Overall Score >= 3 involved: Problem 2a Score >= 3, Problem 2b Score >= 2, Problem 2c Score >= 3.
    • PS8: The cutoff for a Standard 13 Overall Score >= 3 involved: Problem 3a Score >= 2, Problem 3b Score >= 3, Problem 3c Score >= 3.
    • I have posted progress reports to Gradescope. Next to each standard, there is a number 0, 1, or 2, indicating the number of assignments for which you have received a Standard Overall Score >= 3. You need to earn a Standard Overall Score >= 3 on two assignments in order for that standard to count towards your final grade. Therefore, you do not need to attempt again any standard where you have a 2 on the progress report. Please double check your progress report against your own records.
  • 7/2:
    • PS9 is now posted. It is due on 7/14.
    • Requizzing Period 2 (RQ2) will not be held on 7/22-7/23. The tentative dates will be 7/26-7/27. I reserve the right to push the dates back further. The precise standards covered on RQ2 is TBD. I will communicate more details as we get closer and they come into focus. For now, I didn't want you all to stress about RQ2.
  • 6/29:
    • Requizzing Period 1 will be next week. The logistics are below.
      • Requizzing Period 1 will cover Standards 1-13. There will be one quiz per standard.
      • The rules for our weekly quizzes apply for the requizzing period. These are open-book, open-note, and individual efforts. You may not discuss the quizzes with other people; however, you may email me (but not the TAs or CAs) for clarification (with the understanding that you may not get a response in time, and that emailing me counts against the time limit).
      • The quizzes will open on Wednesday July 7 at 4 PM. They window to take a requiz will close on Friday July 9 at 2 PM.
      • Solutions will be released for Standards 11-13, as this will be the second scheduled attempt at these standards. There will be a third scheduled attempt at these standards on a weekly quiz, which will be scheduled reasonably after you all receive graded feedback and solutions for these standards on the requizzing period.
      • As per the syllabus, solutions for Standards 1-10 will not be released.
      • All graded work (PS7, PS8, Quizzes 6-10) will be released no later than the end of the day on Wednesday July 8. We will make every effort to return grades as early as possible.
      • Class will be cancelled on July 6-7, so that you all can use this time to study. Recitation will be cancelled on July 8-9, so that you all can use this time for the requizzing period if you wish.
      • Office hours will be cancelled from Wednesday after 4 PM through Friday at 2 PM.
      • Once we return more grades (hopefully over the weekend or early next week), I will work on posting a progress report to Gradescope.
      • We will make every effort to have the Requizzing Period 1 quizzes graded by the end of the day on Wednesday, July 14 (and hopefully sooner). Note that the drop deadline is Thursday, July 15.
    • In light of the holiday weekend, office hours from July 3-5 will be cancelled.
  • 6/24:
    • PS5 grades have been posted. The cutoff for a Standard 6 Overall Score >= 3 required a score of 3 on Problems 2, 3, and 4.
    • We will have PS6 graded and released this weekend, along with PS6 solutions.
    • There will be quizzes over Standards 6-10 next week. Because there are 5 quizzes, we will open them on Monday 6/28, and they will close at 8 PM on Friday 7/2.
    • PS8 is now posted. It will be due on 7/2 at 8 PM.
    • Quiz 2 grades have been released, and the solutions are now on Canvas.
  • 6/22:
    • PS4 grades have been posted.
      • The cutoff for a Standard 4 Overall Score >= 3 was a majority of scores >= 3 and no scores < 2.
      • The cutoff for a Standard 5 Overall Score >= 3 was: score of >= 3 on both problems 5 and 6a, and a score >= 2 on problem 6b.
  • 6/21:
    • The Zoom recordings and handwritten notes from today have been posted to Canvas.
    • PS7 will become available tomorrow at 1 PM. It will be due on Tuesday 6/29 at 8 PM.
    • Several folks asked about opportunities to learn more about Ethics in Computing. Prof. Casey Fiesler's INFO 4601/5601 Ethical and Policy Dimensions of Information, Technology, and New Media is a very good (and also very popular) course to take!
    • Mechanism Design for Social Good (MD4SG) is another good resource for CS Ethics, though it is not affiliated with CU. Mechanism Design is closely associated with Game Theory. In Game Theory, the goal is to study how agents behave in competitive and cooperative situations. Mechanism Design focuses on how to design incentive structures to ellicit desired behavior or information from the agents. MD4SG applies Mechanism Design techniques with the goal of designing systems that support and catalyze social good.
    • The Algorithmic Justice League is an outstanding resource on AI Ethics.
  • 6/20: PS6 is now posted. It is due on Wednesday 6/23 at 8 PM.
  • 6/19:
    • PS3 Grades have been posted to Gradescope. The cutoff for a Standard 3 Overall Score of 3 was: (i) at least a 3 on problem 4(a)-(b), and (ii) a majority of 3's on problems 2, 3, and 4(c).
    • PS3 and PS4 solutions are on Canvas.
    • We will have quizzes over S3, S4, and S5 open Wednesday 6/23 and close Friday 6/25 at 8 PM.
  • 6/16:
    • The Zoom recordings and handwritten notes from today are on Canvas.
    • The recitation worksheet for this week is also on Canvas (Modules -> Week 3).
    • In case anyone was interested, here are links to the Fenner, Gurjar, and Thierauf paper on the parallel bipartite matching algorithm: the preprint and the subsequent journal version. The proofs in these two versions use different techniques. For reading through a paper, I recommend the following approach:
      • Read the Abstract and Introduction first to understand what the result is, why it is important, and a comparison to previous work.
      • Next, read the preliminaries to the point where you are comfortable with the key objects and terms. You will likely be referring back to the preliminaries frequently as you read the paper- this is completely normal (I do this all the time)!
      • For each subsequent section, read the section to understand what the main results in that section are. Try to understand the key ideas and approaches. Do not read the proofs, especially on a first pass!
      • If you are interested in the proofs and technical details after reading through the paper once, then go back through and read through the proofs.
      • Research papers take more time to go through than textbooks or lecture notes in classes you have taken.
      To be clear, there is no obligation to read through this paper, and you will not be assessed on it.
  • 6/15:
    • PS4 has been extended. The new due date is tomorrow 6/16 at 8 PM. Note that PS5 is still due on Friday 6/18 at 8 PM.
    • The Zoom recordings and handwritten notes from today have been posted.
    • The first Requizzing Period was tentatively slated for July 1-2 in the syllabus. In order to allow for more time for practice and feedback, the first Requizzing Period will be held on July 8-9.
  • 6/14:
    • PS2 grades have been posted. The cutoff for a Standard 2 Overall Score of 3 required meeting the following conditions:
      • Your Problem 2b score was >= 3.
      • You scored at least a 2 on all of Problems 2a, 3, 4, and 5.
      • On Problems 2a, 3, 4, and 5, you scored either: three 3's, or two 4's and two 2's.
    • The Zoom recordings and handwritten lecture notes from today are on Canvas. See Modules -> Week 3.
    • PS5 is now available. It is due on Friday 6/18 at 8 PM. For Problem 4, I highly recommend reading over the statements of Theorems 50 and 51 in Section 4.1 of the typed lecture notes. You should not need the proofs themselves, but the theorem statements may be useful.
  • 6/13:
    • Solutions for PS1 and PS2 are now available.
    • Quiz 1 over Standard 1 and Quiz 2 over Standard 2 will become available on Wednesday 6/16 at 8 AM. You will have 45 minutes per quiz, and you may take the quiz anytime before Friday 6/18 at 8 PM. I would advise starting before Friday 6/18 at 7:15 PM, as Canvas may lock you out at 8 PM sharp.
  • 6/9:
    • The Zoom recordings and handwritten notes from today are posted to Canvas (Modules -> Week 2).
    • PS4 is posted. It is due on Tuesday 6/15 at 8 PM.
    • The recitation worksheet for this week is also on Canvas (Modules -> Week 2). The goal of recitation is to gently introduce concepts related to trees; and in particular, minimum-weight spanning trees. We will build on these concepts more next week.
  • 6/8:
    • PS1 grades are released on Gradescope.
    • If you would like, you may revise and resubmit either Problem 3 or Problem 4 from PS1, subject to a few conditions.
      • You must have attempted the problem you are revising.
      • You must still sign the honor code.
      • If you submit revisions for both Problems 3 and 4, we will by default grade Problem 3 and ignore Problem 4.
      • Let x \in {3, 4}. If your revised score on Problem x is better than your initial attempt at Problem x, then we will update your original Problem x score with your revised Problem x score. In this case, the Standard 1 Overall score will be updated as necessary.
      • To clarify, you may redo the given problem. This is different than submitting a regrade request.
      • Revisions are due by Saturday 6/12 at 8 PM to Canvas. See the PS1 Revisions assignment on Canvas.
      • If it is helpful in deciding which problem to revise, the cutoff for a Standard 1 Overall Score of 3 was the following:
        • Problem 2: Score >= 2, and
        • Problem 3: Score >= 3, and
        • Problem 4: Score >= 3.
      • Regardless as to whether revising will change the outcome of your Standard 1 Overall Score, it is a good opportunity to get a second round of feedback, as well as to iron out any issues before the Standard 1 Quiz (which will likely be sometime next week depending on when the PS1 Revisions are graded).
    • The Zoom links and handwritten notes today are posted to Canvase (Modules -> Week 2).
    • We finished covering Section 3.1 Exchange Arguments, and we got up to Theorem 40 in Section 3.2 Interval Scheduling today. We will cover Theorem 40 and its proof tomorrow.
  • 6/7:
    • Problem Set 3 (Covering Dijkstra's Algorithm) is available starting at 1 PM. It is due on Friday 6/11 at 8:00 PM.
    • The handwritten notes and Zoom recordings are now posted to Canvas (Modules -> Week 2). OIT mentioned that they had issues with their technology freezing about 20 minutes into the 9:25 AM lecture. It may be possible that the videos from the Lecture Videos tab on Canvas may have issues today. So the Zoom links under modules may be better to view.
    • I have updated the Engagement Standard (Progress) assignment on Gradescope to only display the Recitation 1 grades. You should be hopefully able to see the feedback. Let me know if this is not the case.
  • 6/2:
    • We covered Chapters 2.1-2.3 (DFS, BFS, Shortest Paths on Unweighted Graphs) and started Chapter 2.4 (Dijkstra's Algorithm), covering through 2.4.1. We will cover a second example of Dijkstra's Algorithm (Section 2.4.2), the proof of correctness and complexity analysis (2.5) on Monday.
    • Problem Set 2 (covering BFS/DFS) is now available. It is due on Wednesday 6/9 at 8:00 PM.
    • The handwritten lecture notes and Zoom recordings from today have been posted to Canvas.
    • For recitation this week, there is a recitation worksheet on Canvas (Modules -> Week 1). Please work on this in groups. You are welcome and encouraged to have the typed lecture notes on Canvas open, while you are working the problems.
  • 6/1:
    • We covered Chapter 1 (Proof by Induction) through the proof of Proposition 5 in the lecture notes. We will begin with Definition 6 in the typed lecture notes tomorrow. Definition 6 through Proposition 8 on the typed lectures notes correspond to Problem 4 in HW1.
    • If you get a chance, please fill out this Day One Survey. This will help me plan for the class.
    • The handwritten lecture notes have been posted to Canvas. See Modules -> Week 1.
    • I have uploaded the Zoom recordings from today to Canvas (see Modules -> Week 1). Additionally, Classroom Capture should automatically post recordings to Canvas (see the Lecture Videos tabs). I have (hopefully) turned on transcripts for the Zoom recordings. I have no idea if one recording will be of higher quality than the other; both are there.
  • 5/30:
    • Problem Set 1 will become available on 6/1 at 1:00 PM. It is due on Friday 6/4 at 8:00 PM.
    • The Syllabus Quiz will become available on 6/1 at 1:00 PM. It is due on Wednesday 6/9 at 8:00 PM.
  • 4/19: CSCI 3104 will be taught with lectures in a hybrid format, where in-person and online sections meeting simultaneously. Recitations will be taught in a remote synchronous format, to facilitate working problems in groups.
    • Students enrolled for in-person lectures are welcome to participate virtually if they prefer.
    • Due to COVID restrictions, students enrolled for online lecture sections may not attend in person. Similarly, students enrolled for in-person lecture sections may only attend the sections in-person for which they registered (e.g., someone who registered for the 9:25 AM in-person lecture may not attend in-person lecture at 11:20 AM, but is welcome to attend the 11:20 lecture section online.)
    • While students are welcome to attend online lectures at the time of their choosing, they must attend recitations for which they are enrolled. Exceptions to this will be made on an individual basis, such as in cases of extenuating circumstances, and must be cleared with the instructor (and not the TAs).
    • All assignments and assessments will be done asynchronously and turned in online. Office hours will also be held virtually. Students may complete the entire course remotely.
    • Lectures will be recorded via Zoom and posted to Canvas. Handwritten lecture notes will also be posted to Canvas.