CSc445 - Introduction to Algorithms - Fall 2017
Location and Times: TueThu 5-6:15 PM in GS 906
After a short illustration of algorithm design and analysis, the course begins by briefly reviewing basic analysis techniques (approximating functions asymptotically, bounding sums, and solving recurrences). We then study problems that are efficiently solvable, focusing on basic design techniques (divide-and-conquer, dynamic programming, randomizations, and others). We will review some graph algorithms (variants of shortest paths, maximum flow and stable marriage), geometric algorithms (finding the closest pair of points, spatial data structures) and other important applications. ‘
The emphasis is on learning algorithm design (the ability to synthesize correct and efficient procedures for new combinatorial problems), acquiring an algorithm repertoire (a toolbox of classic algorithms for well-solved problems), and applying algorithm reduction (the ability to reduce new problems to known problems from your repertoire). These skills are developed through written assignments containing challenging exercises.
CSc345
Alon Efrat,
Gould Simpson 742
Office Hours: Office Hours: Office Hours: TuesThu 2:45-3:45
Aaron Blumenfeld,
Gould Simpson 938
Office Hours: Thursday 2:30-5 PM
Zheng Tang,
Gould Simpson 903
Office Hours: Monday 2-3:15 PM Wednesday 8-9:15 AM
Homeworks could be found at this link. Homeworks will be assigned every Tuesday, and will be due the following Tuesday.
More web resources could be found in link
Videos of the lectures given during previous semesters could be found in the panopto folder of Course D2L page. (These topics are all identical to the ones discussed in this course, and emphasis might be different. Yet many are quite similar)
The student will:
Students are expected to attend class. It is the student's responsibility to be aware of material discussed in class in case of absence. Use of laptops and similar devices is allowed, but only to the level that your attention is focused on the discussion in class.The UA’s policy concerning Class Attendance, Participation, and Administrative Drops is available at http://catalog.arizona.edu/2015-16/policies/classatten.htm
The UA policy regarding absences for any sincerely held religious belief, observance or practice will be accommodated where reasonable: http://policy.arizona.edu/human-resources/religious-accommodation-policy.
Absences pre-approved by the UA Dean of Students (or dean’s designee) will be honored. See http://uhap.web.arizona.edu/policy/appointed-personnel/7.04.02
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, and Clifford Stein, Introduction to Algorithms, McGraw-Hill, Boston. |
Optional Texts
|
Homework: There are seven homeworks, which occur roughly after the conclusion of each chapter. The homework with the lowest score will be dropped from calculation of the final grade.
Midterm: Thursday 10/19/17, 5:00-6:15 PM
Final: Thursday 12/14/17, 3:30-5:30 PM
The course numeric_final_grade is computed based on the the formula:
46% Homework grade 21% MidTerm exam grade 21% Final exam grade 12% Max{MidTerm_exam_grade, Final_exam} |
Grade Distribution for this course: A: ≥ 90% B: ≥ 80% C: ≥ 70% D: ≥ 60% E: ≤ 59% |
Requests for incomplete (I) or withdrawal (W) must be made in accordance with University policies, which are available at http://catalog.arizona.edu/2015-16/policies/grade.htm#I and http://catalog.arizona.edu/2015-16/policies/grade.htm#W, respectively.
Scheduled Topics and Assignments
Topic | Handouts | Homework and posting date | Number of meetings |
Introduction. Overview of Big-O, Ω Θ, and recursion formula. | 1.5 | ||
Stable Marriage | HW1 (Aug 31) | 1.5 | |
SkipList | 2 | ||
Hash Table, Hash Functions and their applications | HW2, (Sep 18) | 3 |
------------ Material for the final starts here --------------
Single Source Shortest Path in Graphs (positive weights) | HW3 (Oct 2) | 2 | |
Single Source Shortest Path in Graphs (arbitrary weights) | HW4 (Oct 16) | 1 | |
Johnson’s algorithm | |||
Dynamic Programming | HW5 (Oct 30) | 1.5 | |
Quad Trees. Spatial Data Structure and some applications | |||
Tries and Suffix trees | HW6 (Nov 28) |
On homework, you are expected to think about and try to solve the problem for yourself. You may discuss general ideas with friends, but your solutions must be written up separately and represent individual work, and if ideas were developed during a collaborative discussion, list clearly with whom you brainstormed ideas. Use of solutions from previous offerings of the course (at UofA or any other university) is not permitted. Five points will be deducted per day for lateness, and late homework cannot be turned in after solutions have been discussed in class.
Use D2L to submit your homework. They should be .pdf files. You could use LaTeX, Word, Google Doc, etc, or you could write using your handwriting, scan and submit. It is your responsibility to verify that homework is legible. Please do not submit paper solutions. Neatness, and especially conciseness, is required to earn the highest marks. If you cannot solve a problem, state this in your write-up, and write down only what you know to be correct; rambling at length about ideas that don't quite work may cause additional points to be deducted.
The Department of Computer Science is committed to providing and maintaining a supportive educational environment for all. We strive to be welcoming and inclusive, respect privacy and confidentiality, behave respectfully and courteously, and practice intellectual honesty.
Disruptive behaviors (such as physical or emotional harassment, dismissive attitudes, and abuse of department resources) will not be tolerated. The complete Code of Conduct is available on our department web site. We expect that you will adhere to this code, as well as the UA Student Code of Conduct, while you are a member of this class.
To foster a positive learning environment, students and instructors have a shared responsibility. We want a safe, welcoming, and inclusive environment where all of us feel comfortable with each other and where we can challenge ourselves to succeed. To that end, our focus is on the tasks at hand and not on extraneous activities (e.g., texting, chatting, reading a newspaper, making phone calls, web surfing, etc.)
Inclusive Excellence is a fundamental part of the University of Arizona’s strategic plan and culture. As part of this initiative, the institution embraces and practices diversity and inclusiveness. These values are expected, respected and welcomed in this course.
Elective Name and Pronoun Usage
This course supports elective gender pronoun use and self-identification; rosters indicating such choices will be updated throughout the semester, upon student request. As the course includes group work and in-class discussion, it is vitally important for us to create an educational environment of inclusion and mutual respect.
The UA Threatening Behavior by Students Policy prohibits threats of physical harm to any member of the University community, including to oneself. See http://policy.arizona.edu/education-and-student-affairs/threatening-behavior-students.
Our goal in this classroom is that learning experiences be as accessible as possible. If you anticipate or experience physical or academic barriers based on disability, please let me know immediately so that we can discuss options. You are also welcome to contact the Disability Resource Center (520-621-3268) to establish reasonable accommodations. For additional information on the Disability Resource Center and reasonable accommodations, please visit http://drc.arizona.edu.
If you have reasonable accommodations, please plan to meet with me by appointment or during office hours to discuss accommodations and how my course requirements and activities may impact your ability to fully participate. Please be aware that the accessible table and chairs in this room should remain available for students who find that standard classroom seating is not usable.
Students are encouraged to share intellectual views and discuss freely the principles and applications of course materials. However, graded work/exercises must be the product of independent effort unless otherwise instructed. Students are expected to adhere to the UA Code of Academic Integrity as described in the UA General Catalog. See http://deanofstudents.arizona.edu/academic-integrity/students/academic-integrity.
Selling class notes and/or other course materials to other students or to a third party for resale is not permitted without the instructor’s express written consent. Violations to this and other course rules are subject to the Code of Academic Integrity and may result in course sanctions. Additionally, students who use D2L or UA e-mail to sell or buy these copyrighted materials are subject to Code of Conduct Violations for misuse of student e-mail addresses. This conduct may also constitute copyright infringement.
The University is committed to creating and maintaining an environment free of discrimination; see http://policy.arizona.edu/human-resources/nondiscrimination-and-anti-harassment-policy
Our classroom is a place where everyone is encouraged to express well-formed opinions and their reasons for those opinions. We also want to create a tolerant and open environment where such opinions can be expressed without resorting to bullying or discrimination of others.
UA Academic policies and procedures are available at http://catalog.arizona.edu/2015-16/policies/aaindex.html
Student Assistance and Advocacy information is available at http://deanofstudents.arizona.edu/student-assistance/students/student-assistance
http://www.registrar.arizona.edu/ferpa/default.htm
Information contained in the course syllabus, other than the grade and absence policy, may be subject to change with advance notice, as deemed appropriate by the instructor.