CSc445 - Introduction to Algorithms - Spring 2018

Location and Times: TueThu 3:30-4:45 PM in GS 906

        

Course Description:

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.

Course Prerequisites or Co-Requisites

CSc345

Instructor and Teaching Assistants

Alon Efrat,

alon@cs.arizona.edu

Gould Simpson 742

Office Hours: Mon 9:30-10:20. Thu 12:00-1:15

Savan Kiran
        
savankiran@email.arizona.edu

Gould Simpson 938

Office hours: Tue, Fri 11:30am-12:30pm

 

 Carlos Carbajal

bcarbajal23@email.arizona.edu

Gould Simpson 934

Office Hours: Mon, Wed 11:00am-12:00pm

Aryan Agrawal
        
aryanagrawal@email.arizona.edu

Gould Simpson 942

Office hours: Mon, Wed 12:30pm- 1:30pm

 

Web information 

Homeworks could be found at this link. Homeworks will be assigned around the end of every chapter, and will be due mostly after 12-15 days.    

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)

Course Objectives and Expected Learning Outcomes

The student will:

Absence and Class Participation Policy

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 

Required Texts or Readings

Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, and Clifford Stein, Introduction to Algorithms, McGraw-Hill, Boston.

Optional Texts

Assignments and Examinations: Schedule/Due Dates

Homework: There are six to 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:   3/15/2018   3:30-4:45

Final:   5/9/2018 3:30-5:30

Grading Scale and Policies

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%

Department of Computer Science Grading Policy:

  1. Instructors will explicitly promise when every assignment and exam will be graded and returned to students.  These promised dates will appear in the syllabus, associated with the corresponding due dates and exam dates.
  2. Graded homework will be returned before the next homework is due.
  3. Exams will be returned "promptly", as defined by the instructor (and as promised in the syllabus).
  4. Grading delays beyond promised return-by dates will be announced as soon as possible with an explanation for the delay.

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.

 link

1-1.5

Hash Table, Hash Functions and their applications

link

HW1, (January 22)

3-4

Finding the closest pair of points  

Link

2

Stable Marriage

link

HW2 (February 2)

1.5

SkipList

Link

2

Graphs.   BFS Single Source Shortest Path in Graphs (positive weights)

Link

Single Source Shortest Path in Graphs (arbitrary weights)

Link

1

Dynamic Programming

[Floyd-Warshall, LCS, ED, DTW, Frechet]

Link

HW4 (March 20)

5

Linear Programming

Link

HW5 (April 3)

3

More LP in low dimension

Link

HW6 (April 15)

Union/Find Data Structure and Kruskal Algorithm

Link

tries

Link

Homeworks Ethics and Instructions

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.

Department of Computer Science Code of Conduct

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.

Classroom Behavior Policy

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.)

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.

Threatening Behavior Policy

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.

Accessibility and Accommodations

At the University of Arizona we strive to make learning experiences as accessible as possible. If you anticipate or experience physical or academic barriers based on disability or pregnancy, you are welcome to let me know so that we can discuss options.  You are also encouraged to contact Disability Resources (520-621-3268) to explore reasonable accommodation.

If our class meets at a campus location: 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.

Code of 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. 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.

UA Nondiscrimination and Anti-harassment Policy

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.

Additional Resources for Students

UA Academic policies and procedures are available at http://catalog.arizona.edu/policies

Student Assistance and Advocacy information is available at http://deanofstudents.arizona.edu/student-assistance/students/student-assistance

Confidentiality of Student Records  

http://www.registrar.arizona.edu/ferpa/default.htm

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.