CS 4102: Algorithms Spring 2019\ M/W 3:30-4:45pm, Rice 130

Instructor: Robbie Hott\ Email: jrhott\@virginia.edu\ Office: Rice Hall 210\ Office Hours: tbd\ 0.3in

Teaching Assistants: See Collab

# Overview {#overview .unnumbered}

Course Description: Introduces the analysis of algorithms and the effects of data structures on them. Algorithms selected from areas such as sorting, searching, shortest paths, greedy algorithms, backtracking, divide-and-conquer, and dynamic programming. Data structures include heaps and search, splay, and spanning trees. Analysis techniques include asymptotic worst-case, expected time, amortized analysis, and reductions between problems

Availability: It is important to me to be available to our students, and to address their concerns. If you cannot meet with me during our office hours, e-mail me and we will find the time to meet. That being said, like everybody else I am quite busy, so it may take a day or more to find a time to meet. And if you have any comments on the course—what is working, what is not working, what can be done better, etc.—I am very interested in hearing about them. There is an anonymous feedback tool through Collab, or you can send me or one of the TAs an e-mail. We tend to get bogged down by e-mail as the semester progresses, so seeing us in person (right after lecture, during office hours, etc.) is often a good way to get a more immediate response.

Prerequisites: CS 2102 and 2150 with grades of C- or higher, and APMA 1090 or MATH 1210 or MATH 1310.

Course Objectives: Students who complete the course will:

• Comprehend fundamental ideas in algorithm analysis, including: time and space complexity; identifying and counting basic operations; order classes and asymptotic growth; lower bounds; optimal algorithms.

• Apply these fundamental ideas to analyze and evaluate important problems and algorithms in computing, including search, sorting, graph problems, and optimization problems.

• Apply appropriate mathematical techniques in evaluation and analysis, including limits, logarithms, exponents, summations, recurrence relations, lower-bounds proofs and other proofs.

• Comprehend, apply and evaluate the use of algorithm design techniques such as divide and conquer, the greedy approach, dynamic programming, and exhaustive or brute-force solutions.

• Comprehend the fundamental ideas related to the problem classes NP and NP-complete, including their definitions, their theoretical implications, Cook’s theorem, etc. Be exposed to the design of polynomial reductions used to prove membership in NP-complete.

Textbooks:

• Required: NONE

• Highly Recommended: Introduction to Algorithms, Third Edition by Cormen, et. al. (ISBN 0262033844).

• $60\%$ Assignments

• $20\%$ Midterm

• $20\%$ Final Exam

• $10\%$ Extra Credit

I recognize that I cannot expect to produce assignments which are perfect evaluations of your fluency in course material. As such, grade breakdowns will be determined after all assignments are graded. This adjustment will occur prior to assessing extra credit.

Extra credit will be awarded for any action which displays extraordinary engagement with the course. Actions deserving of extra credit include, but are not limited to, insightful questions/comments in lecture, completing given extra credit assignments, submitting responses to current events which are relevant to algorithms, attending special seminars/colloquia, slide corrections, compelling office-hours conversation. Actions that require more effort to complete will be given a higher weight than those that require little effort. As a general rule, if you have done something that you feel might be deserving of extra credit, just ask for it! Submit extra credit via email to extracredit.cs4102\@gmail.com.

\newpage Exams: There will be one midterm exam, as well as a final. The (tentative) exam dates are as follows:

• Midterm: tbd

• Final: See Registrar’s Calendar

Assignments: This course will have a heavy emphasis on programming the algorithmic techniques taught. The homeworks will thus be about 1/3 programming and 2/3 traditional pen-and-paper problems. Expect about 10 homework assignments throughout the semester.

Programming assignments may be completed in either Python or Java.

The pen-and-paper (a.k.a. “written”) assignments are not really pen-and-paper: they must be typeset with LaTeX, a professional formatting system. Tutorials on how to use LaTeXwill be made available when the first written problem set is released. LaTeXis easily installable on many computers:

• Cygwin (which you all saw in CS 216/2150) has LaTeXpackages that can be installed

• MiKTeX provides a stand-alone installer for Windows and Mac, miktex.org

• Ubuntu and CentOS provide TeXLive packages in their repos

I recommend using Overleaf, http://overleaf.com. It is an in-browser LaTeXeditor which behaves much like Google Docs. We generally will not accept LaTeXdocuments with images of text or formulas; you must typeset the formulas in LaTeX, not in another program and have them exported as images.

Submission System: All homeworks will be submitted via Collab. For written assignments, you will submit both your .tex mark-up file as well as a PDF of your write up as two separate attachments. For programming assignments, you will submit a zip file containing all of your code, including a ReadMe text file containing any instructions for us regarding how to execute your program correctly. Submit extra credit via email to extracredit.cs4102\@gmail.com.

Late Policy: $grade = grade_{earned} e^{-\frac{1}{\varphi} days}$.

Your grade for each assignment is given by the above formula (this is an exponential decay formula). To calculate your grade, let $grade_{earned}$ be your earned grade (the remaining grade after scoring), let $days$ be the (fractional) number of days late, let $\varphi = \frac{1+\sqrt{5}}{2}$ be the golden ratio, and $e$ be Euler’s constant. To give you an idea of the result of this scheme, submitting an assignment $4$ hours late ($days = 1/6$) will result in a grade penalty of $10\%$, submitting 1 day late will result in an $\approx 45\%$ penalty, and submitting 2 days late will result in an $\approx 70\%$ penalty.

Regrades: All regrades are conducted in person Prof. Hott. Regrade office hours are listed at the top of this syllabus, please attend these office hours to discuss your assignments. If you are unable to make this time, then please schedule an appointment.

Note: I reserve the right to modify the weighting (changing the curve, adding pop quizzes, etc.), especially if attendance drops off significantly. If this happens, it will be clearly announced in lecture. However, attendance in this class is not mandatory. You can still receive an A if you are not present in lecture, although you will obviously have to find other ways to participate in the course. If you do attend class, then you must agree to limit computer usage to things directly helping you understand the lectures, such as following the slides online, etc. I reserve the right to forbid using laptops/phones in class.

# Collaboration {#collaboration .unnumbered}

Collaboration Policy: You are encouraged to collaborate with up to 4 other students in the course on each homework, but all work submitted must be your own independently written solution. Any solutions that share similar text/code will be considered in breach of this policy. You must list the names of all of your collaborators.

Do not seek published solutions for any assignments. Any submission which is discovered to be similar to a published solution will be considered in breach of this policy. If you use any published resources when completing your assignments, be sure to cite them.

Exams are always individual assignments; collaboration with others is not allowed for the midterm and final.

Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to a member of the course staff, and we reserve the right to spot-check for this requirement.

Assignments or exams where violations of this policy occur will receive a zero grade for that entire assignment or exam, as well as a full letter-grade penalty on the course grade. Such infractions will also be submitted to the Honor Committee if deemed appropriate.

Special Circumstances: The University of Virginia strives to provide accessibility to all students. If you require an accommodation to fully access this course, please contact the Student Disability Access Center (SDAC) at (434) 243-5180 or sdac\@virginia.edu. If you are unsure if you require an accommodation, or to learn more about their services, you may contact the SDAC at the number above or by visiting their website http://studenthealth.virginia.edu/sdac.

For this course, I ask that students with special circumstances let me know as soon as possible, preferrably during the first week of class.

Religious Accommodations: It is the University’s long-standing policy and practice to reasonably accommodate students so that they do not experience an adverse academic consequence when sincerely held religious beliefs or observances conflict with academic requirements. Students who wish to request academic accommodation for a religious observance should submit their request in writing to me as far in advance as possible. If you have questions or concerns about academic accommodations for religious observance or religious beliefs, visit

https://eocr.virginia.edu/accommodations-religious-observance

or contact the University’s Office for Equal Opportunity and Civil Rights (EOCR) at UVAEOCR\@virginia.edu or 434-924-3200. Accommodations do not relieve you of the responsibility for completion of any part of the coursework missed as the result of a religious observance.

Safe Environment: The University of Virginia is dedicated to providing a safe and equitable learning environment for all students. To that end, it is vital that you know two values that the University and I hold as critically important:

1. Power-based personal violence will not be tolerated.

2. Everyone has a responsibility to do their part to maintain a safe community on Grounds.

If you or someone you know has been affected by power-based personal violence, more information can be found on the UVA Sexual Violence website that describes reporting options and resources available – www.virginia.edu/sexualviolence.

As your professor and as a person, know that I care about you and your well-being and stand ready to provide support and resources as I can. As a faculty member, I am a responsible employee, which means that I am required by University policy and federal law to report what you tell me to the University’s Title IX Coordinator. The Title IX Coordinator’s job is to ensure that the reporting student receives the resources and support that they need, while also reviewing the information presented to determine whether further action is necessary to ensure survivor safety and the safety of the University community. If you would rather keep this information confidential, there are Confidential Employees you can talk to on Grounds (See http://www.virginia.edu/justreportit/confidential_resources.pdf). The worst possible situation would be for you or your friend to remain silent when there are so many here willing and able to help.

Well-being: If you are feeling overwhelmed, stressed, or isolated, there are many individuals here who are ready and wanting to help. The Student Health Center offers Counseling and Psychological Services (CAPS) for all UVA students. Call 434-243-5150 (or 434-972-7004 for after hours and weekend crisis assistance) to get started and schedule an appointment. If you prefer to speak anonymously and confidentially over the phone, Madison House provides a HELP Line at any hour of any day: 434-295-8255.