EECE 431 Syllabus, Fall 2017

EECE 431 Design and Analysis of Algorithms August 30, 2017 Lectures • Time: MWF 10:00 - 11:00 am. • Place: Bechtel 204 • Lecturer: Professor Louay Bazzi Becthel 412, AUB extension: 3550 Louay.Bazzi@aub.edu.lb Office hours: Mondays and Wednesdays 11:15 am - 1:15 pm. Catalog Description This course covers techniques for the design and analysis of efficient algorithms. Topics include: sorting algorithms including merge-sort, quick-sort, and counting-sort; median and order statistics algorithms; sorting lower bound; divide-and-conquer design strategy; polyno- mial and matrix multiplication algorithms; balanced search trees; hash tables; augmenting data structures; number-theoretic algorithms; dynamic programming; greedy algorithms; graph algorithms including graph traversal algorithms and applications, minimum spanning tree, shortest path algorithms; distributed algorithms; network flows; introduction to NP- completeness and intractability. 3 Cerdits. Prerequisites By course: EECE 330. By topic: programming and elementary data structures. 1 Textbook “Introduction to Algorithms”, by Cormen, Leiserson, Rivest, and Stein, MIT press, third edition. Course objectives • Teach the student the fundamental algorithms • Teach the student how to analyze the performance of algorithms • Teach the student the fundamental algorithmic design strategies Topics 1. Foundations 8 hours • Introduction: design and analysis of algorithms, insertion-sort, merge-sort • Asymptotic notations, solving recurrences • Divide-and-conquer algorithms: modular exponentiation; Strassen’s algorithm. • Polynomials and long integers multiplication; division algorithm; Euclid’s algo- rithm. 2. Dynamic programming 3 hours Longest common subsequence, and Matrix chain multiplication 3. Introduction to graphs and trees 1 hour Proofs 3. Sorting and order statistics 8 hours • Quick-sort, randomized algorithms • Sorting lower bounds, and counting-sort • Medians and order statistics algorithms 4. Data structures 8 hours • Review of elementary data structures, binary-search trees, and priority queues • Red-Black trees 2 • Augmenting data structures: dynamic order statistics. • Hash functions 5. Graph algorithms 10 hours • Elementary graph algorithms Breadth-first search, depth-first search, and applications. • Minimum spanning tree: Greedy algorithms, Prim’s minimum spanning tree algorithm • Shortest path algorithms Dijkastra’s algorithm, Bellman-Ford algorithm, and Floyd-Warshall algorithm • Network Flow 6. Introduction to complexity theory 3 hours Tractable and intractable problems, definition of the classes P and NP, NP-completeness, standard NP-complete problems. 7. Selected topics as time permits 2 hours Problem sets, exams, and grading We will have around 9 problem sets, a midterm, and a final exam. The following grading system will be adopted: • Weekly problem sets: 25 % The problem sets are intended to help you understand the material. If you do not work on the problem sets, do not expect to pass the exams. • Exams: 70 % – Midterm (35%): TBA – Final (35%): TBA • Assessment of the instructor: 5 % Web Course webpage on Moodle. 3