CS 344: Design and Analysis of Computer Algorithms
Course Syllabus 1 Course Information
General information
Lectures: This is a fully asynchronous course and will be taught online.
Instructor: Sepehr Assadi – [email protected] – https://www.cs.rutgers.edu/~sa1497
Prerequisites: CS 112 Data Structures, CS 206 Introduction to Discrete Structures. We assume a knowledge of basic concepts of programming and data structures, e.g., lists, stacks, queues, trees, as well as basic mathematics, e.g., elementary calculus, proof by induction, linearity of expectation, permutations, logarithms, and asymptotic notation (i.e. “big-Oh”, “big-Omega”).
Textbook: Algorithms, by Erickson, c Copyright 2019 Jeff Erickson (the electronic version is freely available at: http://jeffe.cs.illinois.edu/teaching/algorithms).
Homeworks and exams will be solely based on the materials presented in the class – this includes the parts that may not necessarily be directly covered in the textbook.
Website: https://www.cs.rutgers.edu/~sa1497/courses/cs344-s21/ The webpage will contain updated syllabus information as the semester progresses and a calendar. There is a Canvas website for the course where you can find announcements and lecture notes, submit your homeworks, and check your grades. We will use Piazza for online discussions. Students with disabilities: The students with disabilities are encouraged to discuss with me any appropriate accommodations that we might make on their behalf following the guidelines of the Office of Disability Services1 .
Statement of inclusivity: I am committed to creating a learning environment in which all of my students feel safe and included, regardless of race, ethnicity, religion, gender or sexual orientation. Because we are individuals with varying needs, I rely on your feedback to achieve this goal. I invite you to let me know about what I can stop, start, or continue doing to make sure every one of my students feels valued and can engage actively in our learning community. Different timezones: As a standard, all the times for the office hours, deadlines, etc., will be posted in Eastern Time Zone (EST). If you are working in another timezone, pay attention when converting times from EST to your local timezone.
OAT program: This course has received an Open and Affordable Textbooks (OAT) Program award from the Rutgers University Libraries.The OAT Program supports textbook affordability at Rutgers by encouraging courses to adopt educational materials that are freely available, available at a low cost (compared to similar courses), or part of the Rutgers University Libraries’ electronic collections, and thereby free of charge to Rutgers University students. As a student in this course, you will be asked to provide feedback on this initiative at the end of the semester. https://ods.rutgers.edu 1 Asynchronous Remote Teaching Weekly Schedule: The class is taught on a week-by-week basis: on the Monday of each week, the video recordings and class notes for that week will be posted on Canvas. The students are expected to review these materials by Thursday. We will then have two interactive office hours on Thursday night and Friday morning for Q&A. Attendance in office hours is not mandatory but is strongly encouraged. The two office hours of each week cover the same topics and are intended to cover different time zones. Technology recommendation: You will need a laptop, desktop, cellphone, tablet, or other similar devices that can connect to the internet, play videos, and conduct video/audio communications2 . If you do not have the appropriate technology for financial reasons, please email Dean of Students at [email protected] for assistance. Recordings: The office hours may be recorded for students who are not able to attend. They will be posted only on Canvas. These recordings are solely for the students registered in the course and are not to be redistributed outside of this class.
Course Staff Instructor: Sepehr Assadi [email protected] TAs: Shuchang Liu [email protected] Vihan Shah [email protected] Janani Sundaresan [email protected] Weekly Schedule A typical workweek schedule during the course would look like this: (the schedule for some of the weeks may be entirely different, e.g., due to mid-term exams) Day Activities Assignments Monday video recordings and notes are released (weekly) quiz is released; (bi-weekly) homework is due Tuesday – (bi-weekly) homework is released Wednesday – – Thursday Instructor’s office hour: 8pm to 9pm – Friday Instructor’s office hour: 9am to 10am (weekly) quiz is due There will be additional office hours by the course staff scattered throughout the week. The schedule of these office hours will be posted soon on the course webpage.
Office Hours There are two Instructor’s office hours every week for going over the week’s lecture and/or homeworks, and Q&A with students. In general, the two office hours would cover the same topics and based on their timezones, students can choose one of the two office hours to attend. The office hours are held on Zoom and the links will be shared on Canvas. Attendance in office hours is not mandatory but is strongly encouraged. If you have something to discuss directly with the Instructor (e.g., a concern, a question, or a comment) outside regular office hours, send an email with the subject “[CS344S21] ?” (replace ? with what you like to discuss) to the Instructor and we will set up a time for a meeting. It may take up 24 hours (48 hours over the weekends) before you hear back on your email. Questions directly related about the materials of the course and clarifications about lectures should be posted on Piazza to allow for a more timely response by the entire course staff. 2See Rutger’s technology guide: https://it.rutgers.edu/technology-guide/students/ 2 Course Topics The main goal of this course is to help you further develop your algorithmic thinking skill: the art of getting to and rigorously analyzing a solution through clearly specified steps. We follow a certain set of standard topics that will help you on this front. But keep in mind that these topics are a means toward the main goal which is sharpening your algorithmic thinking skill. The following is a tentative list of the topics that we will cover in this course (not necessarily in order).
• Basics of Algorithm Design (review): algorithms, asymptotic analysis, proof of correctness
• Sorting and Searching: binary search, comparison sorting, counting sort, median selection • Hashing: hash tables, hash functions
• Algorithm Design Techniques: divide and conquer, dynamic programming, greedy algorithms
• Graph Algorithms: graph search, minimum spanning trees, shortest paths, network flows
• Advanced Topics: intro to NP-hardness, approximation algorithms, exponential-time algorithms 2 Assignments and Grading Grading
• 25% Quizzes (14 weekly quizzes for ∼ 2% each)
• 25% Homeworks (5 homeworks for 5% each + a “homework 0” with 2% bonus credit)
• 20% Mid-term exams (2 midterms for 10% each)
• 30% Final exam
• +10% Bonus credit (at the discretion of the Instructor/TAs) Quizzes There will be weekly quizzes accompanying the video lectures in the course. Each quiz will contain several multiple-choice (or similar types of) questions on the topics directly covered in the lectures. You should think of the quizzes as a reminder to follow the course lectures weekly; they are all the level that if you attended an in-class lecture instead, you could have easily answered them by the end of the class in less than 15 minutes. The quizzes are also a way for me to monitor the class progress and engagement as a whole. – Timing: Each quiz will be released at the same time as video lectures of the week on Monday and is due by 11:59 pm of Friday the same week. – Format: Quizzes are held on Canvas and their answers will be released after the deadline. – Quizzes should be done individually and you are not allowed to discuss these questions with other students in the class. – A missed/late quiz draws zero credit. Exceptions will be made only for exceptional circumstances and you will need to provide a university-issued written verification. However, we will be dropping the grade of your two lowest-graded quizzes. 3 Homeworks Homeworks are the main assignments in this course and will help you in developing and sharpening your algorithmic thinking skills. They will involve a small number of algorithmic questions for you to solve, as well as mathematical statements to prove. You should think of homeworks as the main way of exercising your skills in this course beyond what is directly taught in the lectures. – Timing: There will be five homeworks and a tentative schedule of release and due dates are available on the course calendar. Homeworks will typically be released on a Tuesday and are due two weeks later by 11:59 pm of Monday. Occasionally, a homework may be assigned/due on a different day so please follow the calendar. The solution to each homework will be released in the same week as the homework is due. – Format: Homeworks will be released on Canvas and should also be turned in on Canvas as a single pdf file containing the solutions in order. Moreover, homeworks must be typeset and handwritten homeworks will not be graded. The (strongly) preferred method for typesetting your homework is to use LaTeX. Simple instructions on using LaTeX are available on the course webpage and a template will be released with each homework. The course staff are also available to help you with any question you may have in using LaTeX. This policy has a twofold purpose: (i) For students: LaTeX (tremendously) helps you in writing clean and well-structured proofs (a clean proof is a necessity for a rigorous proof) as well as editing an already written proof further. Moreover, learning LaTeX is an important life-long skill that will come handy sooner or later. (ii) For course staff: Grading homeworks done in LaTeX is a considerably easier (and much more pleasant) task than handwritten homeworks. Students that turn in all their homeworks in LaTeX are given a +5% bonus credit at the end of the semester (note that this is equivalent of an entire homework grade).
– Regrading: You can make a regrade request for each of your homeworks within at most one week after you received your grades for that homework. To do so, send an email to the Instructor with the subject “[CS344S21] Regrade Request: Homework #?” (replace ? with the actual number). If you request a regrade for a particular question, all parts of that question will be regraded (possibly by a different course staff) and further points may potentially be deducted from your homework. – If you leave a question completely blank on a homework, you will receive 25% of the grade for that question. However, you may and will receive zero credit for a completely wrong answer. This policy is only in place to discourage writing a meaningless solution in hopes of receiving a few points. – You are allowed to discuss the homework problems with other students in the class. But you must write your solutions independently. You may also consult all the materials used in this course (notes, textbook, etc.) while writing your solution, but no other resources are allowed. – Late homeworks: You are allowed to submit two homeworks late, each up to two days (for instance, if the deadline is on Monday 11:59pm, you can submit the homework until Wednesday 11:59 pm). You do not need to ask for permission to use your extensions – simply write on the first page of your homework that you are using an extension. You will receive zero credit for any homework submitted after two days passed the deadline or after you have used both your extensions. Exceptions will be made only for exceptional circumstances and you will need to provide a university-issued written verification. Use your extensions wisely! It helps to save an extension for the end of the semester. Avoid taking an extension on the first homework.
– Extra Questions: Some of the homeworks may contain extra questions titled “Challenge yourself” or “Fun with algorithms”. These questions are for students who like to familiarize themselves with the topics taught in the course on a more advanced level and will be significantly more challenging 4 than typical questions or may be rather out of scope of the materials taught in this course. These questions will not be graded as part of your regular homework but rather will be considered toward your extra (up to) 10% bonus credit in this course. Mid-Term Exams There will be two take-home midterms in this course. You should think of these exams as a mix between quizzes and homeworks and a way of both testing your understanding of the course as well as further exercising your algorithmic thinking skill. – Mid-term exam 1 will tentatively be on Monday March 1st and mid-term exam 2 will be on Monday, April 12th. Both exams are take-home.
They will be released on Canvas at 9am EST and will be due exactly 24 hours later on Canvas. – Mid-term exam 1 will tentatively be from the materials in weeks 1 to 6 and mid-term exam 2 will tentatively be from the weeks 7 to 11. Any changes to this plan will be announced well in advance of the exam. – Exams should be done individually and you are not allowed to discuss these questions with anyone else. This includes asking any questions regarding the exam from other students or posting them on Piazza (any inquiry should be sent directly to the course staff).
You may however consult all the materials used in this course (notes, textbook, etc.) while writing your solution, but no other resources are allowed. – A missed exam draws zero credit. However, emergencies will be considered upon submitting a university-issued written verification to the Instructor. – Similar to the homeworks, leaving a question completely blank on an exam also will result in 25% of the grade for that question. – Unlike the homeworks, it is okay if you rather write down your solutions by hand due to the time constraints and then submit a scanned solution to Canvas.
Final Exam – The final exam will be held at the end of the semester according to the University schedule. – Further details on the timing and format of the final exam will be released soon.
3 Academic Integrity The students are expected to follow Rutgers and CS Department academic integrity policies3 for all their work in this course. Please familiarize yourself with these policies if you have not done so yet. In particular,
– The Rutgers honor pledge will be included on all (major) assessments for you to sign: On my honor, I have neither received nor given any unauthorized assistance on this examination (assignment).
– Use of external website resources such as Chegg.com or others to obtain solutions to homework assignments, quizzes, or exams is cheating and a violation of the University Academic Integrity policy. Cheating in the course may result in grade penalties, disciplinary sanctions or educational sanctions.
3Rutgers policy: http://academicintegrity.rutgers.edu/ CS department policy: https://www.cs.rutgers.edu/academics/undergraduate/academic-integrity-policy 5 Posting homework assignments, or exams, to external sites without the instructor’s permission may be a violation of copyright and may constitute the facilitation of dishonesty, which may result in the same penalties as plain cheating.
– You may not copy your homework solutions from any other student’s homework. Note that allowing someone else to copy your solution is just as serious of a violation as copying someone else’s solution.
– This policy will be strictly enforced and violations will be referred to the office of student conduct4 .
– There are no exceptions to this policy. If a homework problem is too hard, start earlier, come to the office hours, ask for help, or simply do not answer that question. Academic dishonesty is never the correct solution. If you are ever in doubt about what constitutes academic dishonesty, always ask the course staff or on Piazza.
Finally, all the materials released in this course are solely for the students registered in the course and are not to be redistributed outside of this class.