| layout | title |
|---|---|
default |
Syllabus - Algorithms |
Policy updated on 2/12: Policies on HWs and program submission etc. updated to reflect what was presented in class this week. Changes are marked below. Announcement on Collab has more details and an explanation.
Policy updated on 1/27: Max size of collaboration groups is 4 total (not 5).
Tom Horton
- Email: horton_at_virginia.edu
- Office: Rice 401
- Office Hours (in-person): Mon 1:30-2:00 pm; Tue. 10:00-11:30 am; Wed. 3:00-4:00 pm; Thu. 10:00-11:30 am
Robbie Hott
- Email: jrhott_at_virginia.edu
- Office: Rice 210
- Office Hours (Zoom-only): Mon 3:00-5:00 pm (4-5pm prioritizing 4102); Fri 12:00-2:00 (1-2pm prioritizing 4102); by appointment
Teaching Assistants: See course website. Office hours will be done in-person and using Discord.
Availability: It is important to us to be available to our students, and to address their concerns. If you cannot meet with either of us during our office hours, e-mail us and we will find the time to meet. That being said, like everybody else we are 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.---we are very interested in hearing about them. Please send Prof. Hott, Prof. Horton, or one of the TAs an e-mail or post privately on Piazza to the instructors. When sending email, include CS4102 in the subject line. If your question could be answered by either professor or even a TA, a post on Piazza to "instructors" may get a faster response.
Hott: Tuesday/Thursday 12:30-1:45pm
- Zoom (link available on Collab under Online Meetings) until Feb 4, 2022
- MEC 205 after Feb 4, 2022
Horton: Tuesday/Thursday 2:00-3:15pm
- Nau 101
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
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.
- Be exposed to 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.
Prerequisites: CS 2150 (or DSA2) with a grade of C- or higher (or Covid CR) and math knowledge from APMA 1090 or MATH 1210 or MATH 1310. (Prerequisites are important to this course and will be enforced!)
Introduction to Algorithms, Third Edition by Cormen, et. al. (ISBN 0262033844).
UVA Library makes a digital version of our textbook available online at https://search.lib.virginia.edu/catalog/u6757775.
We will use the standard grading scheme for this course.
| Grade | Lower Bound |
|---|---|
| A+ | 98.0 |
| A | 93.0 |
| A- | 90.0 |
| B+ | 87.0 |
| B | 83.0 |
| B- | 80.0 |
| C+ | 77.0 |
| C | 73.0 |
| C- | 70.0 |
| D+ | 67.0 |
| D | 63.0 |
| D- | 60.0 |
| F | 0 |
The course will be divided into four units, and for each there will be four items that together will count for your grade. Each unit's items will count for 25% of your final grade.
- An exam for that unit: 13% of your final grade
- Basic homework exercises (one or two) for that unit: 2% of your final grade
- Advanced homework exercises for that unit: 5% of your final grade
- A programming assignment for that unit: 5% of your final grade
Thus overall, for all four units, exams are worth 52% of your final grade, basic homeworks worth 8% of your final grade, advanced homeworks worth 20% of your final grade, and program assignments work 20% of your final grade.
Each item listed above will earn a numeric score from 0-100, and these will be combined to give you an overall course score. That score will map to a letter grade as shown elsewhere in this syllabus.
Here are more details about each of these:
-
Exams: These will given in-person in your assigned lecture section's meeting time. For the first three units, you will have a chance to re-take the exam to demonstrate you have learned the material better. The re-take opportunity for Unit A will be a few weeks after the first attempt. For Units B and C, the re-take opportunity will be during the final exam period. The one and only exam attempt for Unit D will be during the final exam period. If you re-take an exam, there is no penalty, and your highest of the two scores will be counted. The first-attempt for the exams for Units A, B and C will be given about one week after lectures on those topics end.
-
Basic Homework: The goal of basic homework is to reinforce fundamental topics and prepare you for the exams. These will be a number of relatively short questions, none harder or longer than something we might ask on an exam. They will be due shortly before the exam for that unit, and solutions will be released at that time. (Therefore late submissions for basic homework won't be accepted.) For most units there will be two problems sets of basic homework so that students can work problems as soon as they've seen the lectures on the topics.
-
Advanced Homework: These will be 2 or 3 more challenging problems per unit, problems that would be too long for an exam and that require more time and thought. They will not be due before the first exam for a unit.
-
Programming Assignments: Each unit will have a programming assignment that explores one or more topics for that unit. These will be submitted to GradeScope and run against test cases to determine your score. They will not be due before the first exam for a unit.
Here is information about how the assignments will be graded:
-
Basic Homework: Three scores are possible: Reasonably Successful (100), Partially Successful (83), Flawed or Incomplete (0). (Updated from original syllabus. )
Graders will review your assignments quickly to determine these scores. You may re-submit up until the deadline.Solutions will be released after the deadline and before the exam,so you may not get your score before the exam,and you won't get detailed feedback on your answers. -
Advanced Homework: These will be graded more carefully, and one of the following scores will be assigned: Excellent (100), Reasonably Successful (93), Partially Successful (83), Flawed Attempt (30), No Credit (0). (Here's more detail that was not in the original syllabus. ) There will be a soft deadline and a hard deadline.
- If you submit by the soft deadline, we will commit to giving you feedback within about a week, which will give you a few days to update your solution before the hard deadline.
- If you submit after the soft deadline, we will try but won’t guarantee you’ll get feedback before the hard deadline.
- You may submit solutions at most twice: once to get some feedback, and the second as your final submission.
-
Programming Assignments: The possible grades will be the same as for Advanced Homeworks. Grades will primarily be based on passing test-cases, but we may also review your code to make sure you've followed the problem constraints (for example, you actually implemented the algorithm we specified). (Here's is detail that was not in the original syllabus. ) Resubmissions to GradeScope will be allowed to run against our test cases. If there will be any restriction on the number, it will be announced when GradeScope is set up for that assignment.
Deadlines and policies on possible resubmissions for Advanced Homeworks and Programming Assignments will be announced when those assignments are released.
-
Exams are always individual assignments; collaboration with others is not allowed. Any solutions that share similar text or code will be considered in breach of this policy.
-
Homeworks and Programming Assignments: You are encouraged to collaborate with up to 3 other students in the course on these, but all work submitted must be your own independently written solution. While you may discuss techniques and collectively solve the problems in your group, you may not share any files or look at each others’ write-up or code. For instance, sharing source code files or Overleaf or Google Docs is not allowed. Likewise, pair programming or sharing the debugging of code are not allowed. Any solutions that share similar text or code will be considered in breach of this policy. You must list the names and computing IDs of all of your collaborators in your submitted files.
We encourage you not to seek published or online solutions for any assignment, since this is not a good way to learn. Studying code examples online is permitted, but only for getting ideas about how to address a programming solution. Copying or reusing large portions of code from an online source to solve a significant part of the assignment violates the honor pledge for that homework. You must cite sources of any online code you use in this way in a comment in your source file(s).
Any submission which is discovered to be similar to a published solution or one found online will be considered in breach of this policy.
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 and to use tools like Moss etc. to detect shared code.
If course staff detect violations to our collaboration policy, such as cheating, plagiarism, improperly sharing, copying another solution to an assignment (including portions thereof), or other dishonest behavior and honor code infractions, they may impose any penalty up to and including a failing grade (F) in the course. This is independent of and in addition to the operations of the Honor Code.
- 1st Offense: You will receive zero (0) points on that assessment, and your final grade will be reduced by one full letter grade (e.g. B goes down to C)
- 2nd Offense: Automatic F in the course
In this course, there will be a focus on working well together and learning about programming languages and web design. Students and staff are all expected to treat each other with respect. This includes, but certainly is not limited to:
- Misuse of class platforms (Discord, Piazza, YouTube comments, etc.)
- Disrespectful language or actions to course staff or other students
- Promptness for all deadlines and class meetings
- Quality work
- Not working well with your partners
- Collaborating with other teams
- Not following University COVID-19 regulations or being mindful of others
Students can and will be penalized for unprofessional behavior.
In this course, we will diligently follow all University regulations in effect at that time. I (Prof. Hott) also respectfully ask that we follow some additional safety precautions with regard to COVID-19, since my son is too young to get vaccinated. (He just turned 1 year old!) So to protect him and keep us a little extra safe, I will continue to wear a mask when lecturing and ask that you wear a mask as well in the classroom, too. Important: We will interpret wearing a mask as being considerate and caring of others in this classroom, not that you're sick.
If you're not feeling well, for all our safety and health, please watch the recorded lecture--whether you might think it's actually a cold or just seasonal allergies. We will ensure that staying home does not impact your grade compared to being in person, so that you can take the time you need to get better, quarantine, or isolate.
Q: I am worried about the virus: will I know if there is an unvaccinated students in the class?
In this message coronavirus.virginia.edu/updates/important-information-about-fall-2021, the University announced that all students who live, learn, or work in person at the University during the next academic year must be fully vaccinated before returning to Grounds unless they have obtained a medical or religious exemption from the University. Therefore, you can expect that students in your class are vaccinated. A very small number of students have received vaccination exemptions, so the likelihood that an unvaccinated student is in your class is slight. Note that you may not ask a student if they have been vaccinated as that is private health information.
Q: How will you accommodate a student who needs to isolate/quarantine?
If a student informs us that they cannot attend class in-person because they have been requested to isolate or quarantine due to possible exposure to COVID-19, we will treat you as we would any other student absent due to illness. You will have access to the recordings of the lecture, either synchronously or asynchronously. You can also continue to interact with your partner and access other online tools.
Q: What if the Professor has to isolate/quarantine (either for themselves or because of a family member)?
If Prof. Hott or Prof. Horton has to isolate or quarantine, we may have a virtual class session, recording, or guest lecture.
Q: Can I just not come to Rice 130 and just watch the lecture over Zoom or watch the recordings?
Yes, that is allowed. Just know you should continue to do any in-class activities to practice what we have learned in class. We encourage you to find a partner to work with remotely.
Q: Are office hours going to be in-person or online?
We anticipate offering a mix of in-person and online office hours. Some staff may only offer online office hours. We will make this clear on the calendar found on the course webpage.
Q: Do I have to wear a mask?
Our class will diligently follow all University regulations in effect at that time. If masks are required during a certain period, then they are absolutely required for class. If policy has changed, then we will adjust accordingly. Failure to mask if a regulation is in effect will result in reporting to UJC and a professionalism penalty for the class.
Note that some members of the staff and class will continue to mask for the entire semester for various reasons. They also may request that you remain distant (or wear a mask as a courtesy) as well. Please be kind to each other!
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 [email protected]. 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 studenthealth.virginia.edu/sdac.
For this course, we ask that students with special circumstances let us know as soon as possible, preferably 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 eocr.virginia.edu/accommodations-religious-observance or contact the University's Office for Equal Opportunity and Civil Rights (EOCR) at [email protected] 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 we and the University hold as critically important:
- Power-based personal violence will not be tolerated.
- 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 we 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 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.
You have many resources available to you when you experience academic or personal stresses. In addition to your professor, the School of Engineering and Applied Science offers free tutoring, and has three staff members located in Thornton Hall who you can contact to help manage academic or personal challenges. Please do not wait until the end of the semester to ask for help!
- Lisa Lampe, Director of Undergraduate Education (academic), [email protected]
- Blake Calhoun, Director of Undergraduate Success (academic), [email protected]
- Alex Hall, Assistant Dean of Students (non-academic issues), [email protected]
In addition to having an Assistant Dean of Students embedded in Engineering, we are also fortunate to have two CAPS counsellors embedded in our School. You may schedule time with Elizabeth Ramirez-Weaver or Katie Fowler through Student Health (https://www.studenthealth.virginia.edu/getting-started-caps). When scheduling, be sure to specify that you are an Engineering student. You are also urged to use TimelyCare for either scheduled or on-demand 24/7 mental health care.
Finally, the Center for Diversity in Engineering facilitates free tutoring during the academic year, helps students locate internships and research opportunities, and connects students with the many organizations on Grounds that provide information and support. The center also engages with student organizations, particularly those serving students who are traditionally underrepresented in engineering.
Your career development path may take you beyond the confines of UVA. Perhaps you applied for an internship and your interview is taking place in-person across the country. Maybe you submitted an abstract to a national technical conference and you have been asked to present your work. These are not only necessary steps on your path but are also invaluable lessons in and of themselves. We wish to encourage and support you in travel related to your career development. To that end, if you notify us at least one-week in advance of such an event, we will offer you the choice of either:
- completing assignments remotely, or
- delaying assignment, exam, or quiz dates until at least 48 hours after your return.
This offer comes with caveats: (1) Extensions will not normally be granted for a team activity when only one member is traveling. (2) The delay will not extend beyond the last day of finals for the semester.
Syllabus Note: This syllabus is to be considered a reference document that may be adjusted throughout the course of the semester to address necessary changes. This syllabus can be changed at any time without notification; it is up to the student to monitor the website for news of any changes. Final authority on any decision in this course rests with the professor, not with this document.
Research: Your class work might be used for research purposes. For example, we may use anonymized scores from student assignments to compare to other student performance data. Any student who wishes to opt out can contact the instructor or TA to do so after final grades have been issued. This has no impact on your grade in any manner.