Algorithms

[Seiden’s:_Theoritical Computer Science Cheat Sheet]

[Link to Project Portfolio]

Feel free to use any code from the [Princeton Algorithms Code PortFolio]

Lecture Topic Slides
/Notes
Assignment
1  Analysis of Algorithms [PDF] Overleaf.com 
Write Up 0 [Thur]
[PDF] [Write Up 0]
2  Union-Find [PDF] LRU Constant Time [Mon]
3 Sorting and Comparators
(+Graham Scan(NT))
[PDF] Friend Circles [Thur]
4  Merge Sort/Heap Sort [PDF] Apple Sort [Thur]
5 Quick Sort & Quick Select [PDF] Nth place loser [Mon]
6 Solving Recurrence Relations [PDF] Notes From Scribe
[Recurrence Relations I] [Recurrence Relations II]
7 Master Theorem & Karatsuba (NL)  (Solve multiple) [PDF1]
[Notes]
[Recitation Work Sheet]
1  Write up [Feb 18]
[PDF] [Write Up 1]
8 Balance Search Trees
2-3/Red Black Trees,& B-Trees
[PDF] Notes from Scribe
[Substitution]
9 Geometric Search [PDF] Bird Scooters [Feb 25]
10 Strongly Connected Components [PDF] DDR Robot [Mar 4]
11 Back Tracking (NL) [collab] Cryptarithms [Mar 7]
12 Minimum Spanning Trees [PDF]
13 Shortest Path Dijkstra’s [PDF] Clustering [Mar 25]
14 Max Flow / Bipartite matching [PDF]
15 Radix Sorts []  Flow [Apr 8]
16 Tries []  
17 SubString Search [] Tries [Apr 11]
18 Dynamic Programming I (NL) []
19 Dynamic Programming I Shortest Path Bellman Ford [] DP problems 1(E)/ 2(H)
[Apr 15]
20 Dynamic Programming III (NL) []
21 Markov Models (NL) [] Beta Factor [Apr 18]
22 Skip Lists & Rainbow Tables (NL) []
23 Compression (NL) [] TCA Compression [Apr 25]
24 Linear Programming []
25 Intractability I
(P/ NP) & (Reductions)
[] Write Up 2 [Apr 29]
Feb 25 Midterm 1 Topics: 1 -8
April 3 Midterm 2 Topics 8 – 16

NL – New lecture

NT – Next Time

Meeting Times:

MoWe 2:00PM – 3:15PM Mechanical Engr Bldg 205

Grade Break Down

Writeup 10%
Midterm 1: 12.5%
Midterm 2: 12.5%
Final: 15%
Problem Portfolio: 50%

Break down of grading for portfolio:
Grade for portfolio is square root(number problems solved/ total number of problems) * 100 [Link to Project Portfolio]

Homeworks are due Every Monday &  Thursday at 10:00pm.  To submit follow the instruction in each Java Class in the portfolio.  There are 20 (including 3 bonus problems) implementation problems and 3 write ups.

All written homework assignments can be found on collab.
All programming homework assignments are located on https://autogradr.com. To access them, please make an autogradr student account and enroll in CS 4102: Algorithms using course code: HE206Y. You are responsible for all assignments posted to this course throughout the semester. You can enroll in and begin submitting assignments even if you are on the waitlist of the class.

Office Hours:

[Office Hour Tool: Written by Maxwell Patek

Head TA: Rohit Musti:

Recitations
Tuesday from 6:30 – 8:39 pm in Olsson 120
Saturday from 12:00(noon) – 2:00 pm in Olsson 120
Office Hours
Wednesday from 6:00 – 10:00 pm in Rice 504
Sunday from 12:00 – 2:00 pm, 6:00 – 8:00 pm in Rice 504

Please contact ro@virginia.edu for any issues with your grade or questions about course logistics

Daniel Graham Rice 411
Monday & Wednesday 4pm – 6pm

Info:

If you sign up for this class  off of the waitlist, you are responsible for all homework assignments that were due before you enrolled in class.  You will receive an appropriate extension on Assignment 0, however you will not receive extensions on the programming assignments. You do not need to be on the class roster to access the programming assignments, thus you are responsible for completing them and turning them in on time through the tool.

Students with disabilities or learning needs

It is my goal to create a learning experience that is as accessible as possible. If you anticipate any issues related to the format, materials, or requirements of this course, please meet with me outside of class so we can explore potential options. Students with disabilities may also wish to work with the Student Disability Access Center to discuss a range of options to removing barriers in this course, including official accommodations. Please visit their website for information on this process and to apply for services online: sdac.studenthealth.virginia.edu. If you have already been approved for accommodations through SDAC, please send me your accommodation letter and meet with me so we can develop an implementation plan together

Discrimination and power-based violence

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 I and the University 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 wish to report something that you have seen, you can do so at the Just Report It portalThe worst possible situation would be for you or your friend to remain silent when there are so many here willing and able to help.

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 directly to me by Piazza private message as far in advance as possible. Students who have questions or concerns about academic accommodations for religious observance or religious beliefs may contact the University’s Office for Equal Opportunity and Civil Rights (EOCR) at UVAEOCR@virginia.edu or 434-924-3200.