University of New York, Tirana

Komuna e Parisit (pranë Kopshtit Botanik), Tirana, Albania Tel: 00355-(0)4-273056-8 – Fax: 00355-(0)4-273059

Web Site Address: http://www.unyt.edu.al

Design and Analysis of Algorithms Spring 2012

Faculty: Elton Ballhysa

E-mail: eltonballhysa@unyt.edu.al

Course Description

This course introduces basic methods for the design and analysis of efficient algorithms emphasizing methods useful in practice. Different algorithms for a given computational task are presented and their relative merits evaluated based on performance measures. The following important computational problems are included: sorting, searching, elements of dynamic programming and greedy algorithms, advanced data structures, graph algorithms (shortest path, spanning trees, and tree traversals), string matching, elements of computational geometry, NP completeness.

Course Outcomes

Upon course completion, the students will have demonstrated the ability to do the following:

- Argue the correctness of algorithms using inductive proofs and loop invariants.
- Analyze worst-case running times of algorithms using asymptotic analysis. Compare the
asymptotic behaviors of functions obtained by elementary composition of polynomials, exponentials, and logarithmic functions. Describe the relative merits of worst-, average-, and best-case analysis.

- Analyze average-case running times of algorithms whose running time is probabilistic. Employ indicator random variables and linearity of expectation to perform the analyses. Recite analyses of algorithms that employ this method of analysis.
- Describe the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize divide-and- conquer algorithms. Derive and solve recurrences describing the performance of divide- and-conquer algorithms.
- Explain the major algorithms for sorting. Recite the analyses of these algorithms and the design strategies that the algorithms embody. Synthesize algorithms that employ sorting as a sub procedure. Derive lower bounds on the running time of comparison-sorting algorithms, and explain how these bounds can be overcome.
- Describe main graph algorithms and specifically shortest path algorithms.
- Describe the greedy programming paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize greedy
algorithms, and analyze them.

Understand the complexity classes P and NP and the notions of reducibility and NP- completeness. Be able to use approximation algorithms for specific NP-complete problems.

Textbook

“Algorithms,” by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani. McGraw- Hill Science/Engineering/Math, 2006. (As of this day, a draft version of this book is made available at Vazirani’s website: http://www.cs.berkeley.edu/~vazirani/algorithms.html.)

Other useful reference textbooks:

- Introduction to Algorithms,” by Thomas H. Cormen, Charles Leierson, Ronal Rivest and
Clifford Stein, The MIT Press, 2001

- “Algorithms: Sequential, Parallel and Distributed,” by Kenneth Berman and Jerome Paul,
Thomson – Course Technology, 2005

- “Introduction to the Design and Analysis of Algorithms,” by Anany Levitin , Addison
Wesley, 2006

MIT Open CourseWare website features an “Introduction to Algorithms” course with a complete set of audio and video lectures at http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and- Computer-Science/6-046JFall-2005/CourseHome/index.htm

Also, check Sanjoy Dasgupta’s (one of the textbook’s co-authors) course web site at http://cseweb.ucsd.edu/~dasgupta/101/index.html for slides and other useful information.

Tentative Course Outline

Topics |

Asymptotic Notation, Number Algorithms |

Divide and Conquer Algorithms |

Sorting algorithms |

Graph Algorithms |

Paths in graphs |

Greedy Algorithms |

Dynamic Programming |

Linear Programming |

NP completeness |

(Tentative) |

Materials

The student will be given links to lecture notes, video and audio materials needed for each topic.

Evaluation

- Mid-Term Exam:
- Assignments:
- Project
- Final Exam:

25 % 20% 20% 35 %

Grading Scale and Quality Points:

A-F (UNYT standard grading scale).

Grade |
Percentage |
Quality points |

A |
96-100 |
4.00 |

A- |
90-95 |
3.67 |

B+ |
87-89 |
3.33 |

B |
83-86 |
3.00 |

B- |
80-82 |
2.67 |

C+ |
77-79 |
2.33 |

C |
73-76 |
2.00 |

C- |
70-72 |
1.67 |

D+ |
67-69 |
1.33 |

D |
63-66 |
1.00 |

D- |
60-62 |
0.67 |

F |
0-59 |
0.00 |

General Policies

- Assignments should be submitted timely.
- Any form of unethical activity, e.g. cheating, will result in an automatic F on assignments
and/or exam. The University’s rules on academic dishonesty (e.g. cheating, plagiarism, submitting false information) will be strictly enforced. Please familiarize yourself with STUDENT HONOR CODE.

- Make-up exams will be given in the case of a confirmed medical excuse. Whenever possible, please advise the instructor in advance by email.