[ Syllabus | Homeworks | Web Resources | Notes ]
| CSc 445 | Introduction to Algorithms |
| Time and place |
Tue Thu 5-6:16 ILC 150 | |
| Update | ||
| Instructor |
Alon Efrat alon@cs.arizona.edu Gould-Simpson 742 (520) 626-8047 Office hours: TueThu 1:15-2:30, or by an appointment |
|
| TA | ||
| Description |
After a short illustration of algorithm design and analysis, the course begins by 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, greedy, and others), We will review some graph algorithms (variants of shortest paths, maximum flow and stable marriage). Geometric algorithms (convex hull, closest point-pair) and other cool applications. We will discuss some techniques for dealing with approximation algorithms and branch-and-bound algorithms.
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. |
|
| Required text |
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, and Clifford Stein,
Introduction to Algorithms, McGraw-Hill, Boston. |
|
| Optional text |
|
|
| Resources | ||
| Schedule |
There are two exams.
|
|
| Grading |
|
|
| Grading Policies |
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. Homework is due at the start of class; homework turned in once class begins is considered late. 5 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 handwiting, 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. |
|
| Homeworks |
There are seven homeworks, which occur roughly after the conclusion of each of the chapters. The two
homeworks with the lowest scores will be dropped from calculation of the final grade.
Grade Distribution for this course: A: ≥ 90% B: ≥ 80% C: ≥ 70% D: ≥ 60% E: ≤ 59% Failing the final exam might result in failing the course. | |
| Attendance Policy |
Attandance in classes is not mandatory. It is the student's responsibility to be aware of material discussed in class. 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 and Administrative Drops is available at this link The UA policy regarding absences on and accommodation of religious holidays is available at this link. A Dean's Excuse provides excused absences for university-sponsored events/activities for academic, non-academic, and recognized student organizations. The Dean of Students Office does not have oversight of academic departments or faculty members and does not grant individual excused absences. Each faculty member manages his or her classroom in the manner in which they see fit and are the only ones who may determine what constitutes an excused absence. Therefore, we are unable to excuse absences for students, grant extensions, require that professors allow students to make-up missed work, or ensure students may miss class and submit late work without penalty, etc. The best thing to do is for you to communicate directly with your professor regarding your absence. Your professor is the only person who can excuse your absence, and determine if alternatives or make-up work is an option. Your professor may also request documentation of your situation. If your professor will not excuse your absence or grant make-up work the Dean of Students Office is not able to require them to do so. |
|
| Academic Integrity | 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 - link
.
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 email to sell or buy these copyrighted materials are subject to Code of Conduct Violations for misuse of student email addresses. This conduct may also constitute copyright infringement. | |
| Accessibility and Accommodations |
It is the University's goal 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 Disability Resources (520-621-3268) to establish
reasonable accommodations. For additional information on
Disability Resources 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. |
|
| Additional Resources | ||
Subject to Change Statement |
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. |