CS 3510 Fall 2020 Syllabus

Instructors: Jacob Abernethy (Coda S1221) and Gerandy Brito (Klaus 2111)
TAs: TBA
Textbook: Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.
- Note: The textbook Algorithm Design by J. Kleinberg and E. Tardos is optional but an excellent reference

Course Format

CS 3510 will be an almost entirely online course in Fall 2020. We are aiming to do a mix of synchronous and asynchronous instruction, using a “flipped classroom”-style format. Here’s how this will work:

For every class period, we will have a set of pre-recorded youtube videos for students to watch, covering the content for this class. Links to these videos can be found on the course page.
Having watched the videos, students will come and join our virtual classes (12:30-1:45pm on Tuesday/Thursday) via the Microsoft Teams Live Event link (see course schedule).
In the live class, we’ll have a quick quiz to check for compreshension of the lecture videos, but we’ll spend most of the time solving problems:
- Problems will be solved in small groups of about 8 students
- Once the problem is announced by the professor, students move into a breakout “room” with their group, and discuss the problem for 5-10 minutes.
- Students are then called back into the main room, and the solution is discussed with everyone, followed by a Q&A
Homework will be due every 1-2 weeks, submitted via gradescope
Each segment of the course (see below) will be concluded with an exam, testing the material for that segment of the course.

Topics to be covered

CS 3510 will have four segments, and each segment will take roughly 3-4 weeks.

Divide and conquer
Dynamic programming
Graph algorithms
Complexity Theory

We will typically discuss problems in class that are classical examples of the topic we are covering. Students are expected to do problems using similar strategies in homeworks and exams.

Grade breakdown

The evaluations will consist of 8 homeworks, 4 exams and one final exam. First, your grade will be weighted as follows:

30% Homeworks.
10% In-class quizzes
15% Each exam.

After all grades are in and all overall percentage scores for students have been computed using the weights described above, grades are assigned as follows:

A: 90-100%
B: 80-90%
C: 70-80%
D: 60-70%
F: 0-60%

After this computation you will have the opportunity to decide if you want to keep this grade or you want to do the final exam. In case you choose to do the final, your score in the final will substitute your lowest two exams, if higher (so you can only improve by taking the final).

Note: The cutoffs may be adjusted, but only in the downward direction to improve letter grades. In the event of a curve, only your final overall percentage grade for the course will be curved. Individual assignments will not be curved.

Homeworks

There will be eight homeworks. You will have roughly a week to complete each. Each homework will have several problems but only some problems will be graded. Homeworks will be the best source of practice for the exams. Homeworks must be submitted as a PDF document on Gradescope. The document must be typed (Word, LaTex, etc.) and handwritten solutions will not be accepted. There will be a grace period of one week to submit late homework. Late submissions will be penalized with a 20% deduction of your score. Once grades are released, you will have a week to ask for a regrade, if you reasonably consider that your homework was unfairly or incorrectly graded.

The homework instructions must be followed to receive full credit. A solution must adhere to any justification, time complexity analysis, correctness, and running time requirements. Unless otherwise stated, pseudocode is not an accepted format for an algorithm solution.

The CS 3510 homework collaboration policy is as follows:

Working together on homework is not only permitted but encouraged. You can discuss problems with fellow students, and try to develop answers together. But
- you must disclose your collaborators on the top of your homework submission, and
- your writeup must be your own work, and must not be significantly similar to other submissions.
The policy in 1b would be violated, for example, if you were copying a solution you found on the internet, copy/pasting text from another student’s notes or submission, copying from a shared collaboration space (collaborative whiteboard, google doc, etc.), or writing down another student’s verbal explanation of their solution.
- It is easy to not violate this policy: when working in a group, take your own notes, and when you sit down to expose your answers make sure you are in a separate location and you are not in direct communication (video chat) with other students;
- Please note that one of the most common violations of the homework policy is to use solutions found on the internet, which (coincidentally) happen to be the easiest to detect! We would strongly recommend against checking sites like Chegg, even if you’ve paid for a professional tutor, as this can often lead to policy violations
While not required, we would certainly encourage you to work with your assigned live session group for homeworks, exam studying, etc. You will work with this team throughout the semester anyway, so it shouldn’t be too hard to schedule additional meetings with them separately. You’re welcome to write “Questionable Quoll” (or whatever your group is named) on your homework if this was your collaboration group and we’ll accept this as the appropriate disclosure.

Quizzes

Each day, during the live session, there will be a quiz. The quizzes are meant to test three different things:

Did you at least watch the required lecture videos before the live session?
Did you understand the basic concepts discussed in these videos and reading?
Did you attend the live session?

We’ll test (1) by asking a trivial question about the lecture video; for example, sometimes I’ll mention an animal as “the word of the day”, or we’ll just ask something basic about the topics discussed. We’ll test (2) by asking a basic question on content. We’ll test (c) by giving out a 3-4 digit code, announced during each live session when I say “OK time for the quiz”.

You can find every quiz by going to GradeScope (linked via Canvas). Keep in mind that it’s timed! You only have 3 minutes to answer all three questions.

Students who are in distant time zones may want to take the quiz and not attend the live sessions. This is strongly discouraged but is partially acceptable. The quizzes will be made available several hours before the live sessions and you can take them early if you will not be awake for the live session. BUT you will almost certainly not be able to answer the question “What is the code given in lecture?” which will be 1 out of 3 points for the quiz. The quizzes make up 10% of the grade so this has a cost of 3.3% in total for the course.

We will drop the 4 lowest quiz scores. So you won’t be penalized if your internet goes down, or you have a doctor’s appointment, etc. You get four free passes.

Exams

Each exam will consist of 2-3 problems. Exams will be held during regular lecture time. The final exam will be cumulative and will be at the date, time and location indicated in the official GT calendar.

The final exam is optional in the following sense: we will compute your exam score by taking the average of your score on the four in-class exams. However, you can take the final exam which will substitute the score of your lowest two exams, but only if it improves your score. If you are happy with the score you already have across the first four exams, you can skip the final exam.

Students with Disabilities and/or in need of Special Accommodations

Georgia Tech complies with the regulations of the Americans with Disabilities Act of 1990 and offers accommodations to students with disabilities. If you are in need of classroom or testing accommodations, please make an appointment with the Office of Disability Services to discuss the appropriate procedures. More information is available on their website.