CSE 373-01 (#89329), MAT 373-01 (#80878): Analysis of Algorithms, Fall 2014

Lecture Time and Location. TuTh 4:00 pm - 5:20 pm, Light Engineering Lab 102, West Campus

Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. TuTh 2:00 pm - 3:30 pm, 1421 Computer Science Building

TA. Ibrahim Hammoud (firstname.lastname{at}stonybrook{dot}edu)
Office Hours. MoWe 2:00 pm - 3:30 pm, 2110 Computer Science Building

Course Description. We will explore techniques for designing and analyzing efficient algorithms, including algorithms for sorting and searching, greedy algorithms, divide-and-conquer algorithms, dynamic programming, graph algorithms, randomized algorithms, parallel algorithms and multithreaded computations, NP-completeness and approximation algorithms.

Prerequisites. AMS 210 or Mat 211; CSE 214 or CSE 260 (or consent of instructor).

Textbooks. Only the first one is required.

  1. Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms (3rd Edition), MIT Press, 2009.
  2. Steven Skiena. The Algorithm Design Manual (2nd Edition), Springer, 2008.
  3. Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms (1st Edition), McGraw-Hill, 2006.
  4. Jon Kleinberg and Éva Tardos. Algorithm Design (1st Edition), Addison Wesley, 2005.

Course Requirements. The course grade will be based on the following.

Each homework problem set and exam will include additional problems for graduate students taking the course as CSE 587. Graduate and undergraduate students will be graded separately.

Blackboard. Some course documents (e.g., homework solutions) will be available through Blackboard.

Lecture Schedule.

Date Topic Notes / Reading Material
Tue, Aug 26 Introduction
  • [optional] Algorithmic Puzzles by Anany Levitin and Maria Levitin, Oxford University Press, 2011.
Thu, Aug 28 Asymptotic Analysis of Algorithms
( continued to next lecture )
  • Chapter 3 (Growth of Functions), Section 3.1 (Asymptotic Notation), Introduction to Algorithms (3rd Edition) by Cormen et al.
Tue, Sep 2 No Classes in Session -
Thu, Sep 4 Asymptotic Analysis of Algorithms
( continued )
  • [review yourself] Chapter 3 (Growth of Functions), Section 3.2 (Standard Notations and Common Functions), Introduction to Algorithms (3rd Edition) by Cormen et al.
Tue, Sep 9 Asymptotic Analysis of Algorithms
( continued )
  • [review yourself] Appendix A (Summations), Section A.1 (Summation Formulas and Properties), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • [review yourself] Appendix A (Summations), Section A.2 (Bounding Summations), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Sep 11 Correctness of Algorithms
( continued to next lecture )
  • Chapter 2 (Getting Started), Section 2.1 (Insertion Sort), Introduction to Algorithms (3rd Edition) by Cormen et al.
Tue, Sep 16 Correctness of Algorithms
( continued )
  • Chapter 2 (Getting Started), Section 2.2 (Analyzing Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Sep 18 Correctness of Algorithms
( continued )
  • Chapter 2 (Getting Started), Section 2.3 (Designing Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • HW1 out
Tue, Sep 23 Correctness of Algorithms
( continued )		 -
Thu, Sep 25 Heaps, Heapsort and Priority Queues
( continued to next lecture )
  • Chapter 6 (Heapsort), Section 6.1 (Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 6 (Heapsort), Section 6.2 (Maintaining the Heap Property), Introduction to Algorithms (3rd Edition) by Cormen et al.
Tue, Sep 30 Heaps, Heapsort and Priority Queues
( continued )
  • Chapter 6 (Heapsort), Section 6.3 (Bulding a Heap), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 6 (Heapsort), Section 6.4 (The Heapsort Algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 6 (Heapsort), Section 6.5 (Priority Queues), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • HW1 due
Thu, Oct 2 Quicksort and Average Case Analysis
( continued to next lecture )
  • Chapter 7 (Quicksort), Section 7.1 (Description of Quicksort), Introduction to Algorithms (3rd Edition) by Cormen et al.
Tue, Oct 7 Quicksort and Average Case Analysis
( continued )
  • Chapter 7 (Quicksort), Section 7.2 (Performance of Quicksort), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • HW2 out
Thu, Oct 9 Quicksort and Average Case Analysis
( continued )		 -
Tue, Oct 14 Sorting Lower Bound
and Review of Sample Midterm Exams
  • Chapter 8 (Sorting in Linear Time), Section 8.1 (Lower Bounds for Sorting), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Oct 16 Midterm ( 4:00pm - 5:30pm, in-class ) -
Tue, Oct 21 Review of Background for HW2 -
Thu, Oct 23 Selection
  • Chapter 9 (Median and Order Statistics), Section 9.3 (Selection in Worst Case Linear Time), Introduction to Algorithms (3rd Edition) by Cormen et al.
Tue, Oct 28 Dijkstra's Single-Source Shortest Paths Algorithm
( continued to next lecture )
  • [review yourself] Appendix B (Sets, Etc.), Section B.4 (Graphs), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • [review yourself] Appendix B (Sets, Etc.), Section B.5 (Trees), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 24 (Single-Source Shortest Paths), Section 24.3 (Dijsktra's Algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • HW2 due
Thu, Oct 30 Dijkstra's Single-Source Shortest Paths Algorithm
( continued )
  • Chapter 24 (Single-Source Shortest Paths), Section 24.5 (Proofs of Shortest-Paths Properties), Introduction to Algorithms (3rd Edition) by Cormen et al.
Tue, Nov 4 Prim's Minimum Spanning Tree Algorithm
( continued to next lecture )
  • Chapter 23 (Minimum Spanning Trees), Section 23.1 (Growing a Minimum Spanning Tree), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • HW3 out
Thu, Nov 6 Prim's Minimum Spanning Tree Algorithm
( continued )
  • Chapter 23 (Minimum Spanning Trees), Section 23.2 (The Algorithms of Kruskal and Prim), Introduction to Algorithms (3rd Edition) by Cormen et al.
Tue, Nov 11 Kruskal's Minimum Spanning Tree Algorithm
  • Chapter 23 (Minimum Spanning Trees), Section 23.2 (The Algorithms of Kruskal and Prim), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Nov 13 Kruskal's Minimum Spanning Tree Algorithm
( continued )		 -
Tue, Nov 18 Iterated Log, Inverse Ackermann,
and the Union-Find Data Structure
  • Chapter 21 (Data Structures for Disjoint Sets), Section 21.1 (Disjoint-set Operations), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Nov 20 Iterated Log, Inverse Ackermann,
and the Union-Find Data Structure
( continued )
  • Chapter 21 (Data Structures for Disjoint Sets), Section 21.3 (Disjoint-set Forests), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • HW3 due
  • HW4 out
Tue, Nov 25 Dynamic Programming
( continued to next lecture )
  • Chapter 15 (Dynamic Programming), Page 359, Introduction to Algorithms (3rd Edition) by Cormen et al.
  • [optional] Chapter 15 (Dynamic Programming), Section 15.1 (Rod Cutting), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 15 (Dynamic Programming), Section 15.3 (Elements of Dynamic Programming), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 24 (Single-Source Shortest Paths), Section 24.2 (Single-Source Shortest Paths in Directed Acyclic Graphs), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Nov 27 Thanksgiving Break -
Tue, Dec 2 Class Canceled -
Thu, Dec 4 Dynamic Programming
( continued )
  • Chapter 15 (Dynamic Programming), Section 15.4 (Longest Common Subsequence), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 25 (All-Pairs Shortest Paths), Section 25.2 (The Floyd-Warshall Algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • HW4 due
Mon, Dec 15 Final Exam ( 2:15pm - 5:00pm, location: Light Engineering Lab 102, West Campus ) -

Homeworks.

Exams.