Fall 2020 - COMP.4040 - Analysis of Algorithms

Instructor: Matteo Cimini (email: matteo_cimini [A_T] uml [DOT] edu)
Session 201: Monday Wednesday Friday 2:00PM - 2:50PM
Session 202: Monday Wednesday Friday 12:00PM - 12:50PM
First class: 2nd September.
Instructor's office hours: Monday Wednesday Friday 12:55PM - 1:55PM

Readings


Textbook: Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.

Lectures



(This schedule may be subject to small changes)

Evaluation and Grade Calculation


There are four evaluations:
  • Test #1 will receive a grade between 0 and 1.
  • Midterm will receive a grade between 0 and 1.
  • Test #2 will receive a grade between 0 and 1.
  • Final Exam will receive a grade between 0 and 1.

    Test #1  20% score x 0.2 +
    Midterm 30% score x 0.3 +
    Test #2  20% score x 0.2 +
    Final Exam 30% score x 0.3 =
    Your numeric grade

    Letter Grades are computed from numeric grades as follows:

    Your numeric grade >= 0.94 A
    Your numeric grade >= 0.9 A-
    Your numeric grade >= 0.86 B+
    Your numeric grade >= 0.82 B
    Your numeric grade >= 0.8 B-
    Your numeric grade >= 0.76 C+
    Your numeric grade >= 0.72 C
    Your numeric grade >= 0.7 C-
    Your numeric grade >= 0.66 D+
    Your numeric grade >= 0.6 D
    Your numeric grade  <  0.6 F


    Test #1 - (Part 1 of the course: Basics of Analysis of Algorithms)


    When: 25th September, during class
    Where: VIRTUAL, on Blackboard
    Test #1 will cover the following topics:
    Insertion sort - Analysis of Insertion sort - Merge sort - Asymptotic notation - Standard functions - Recurrences equations

    Exercises:

    Midterm - (Part 2 of the course: Advanced Sorting Algorithms and Basic Data Types)


    When: 23rd October, during class
    Where: VIRTUAL, on Blackboard
    Midterm will cover the following topics:
    Heap sort - Quick sort - Stacks, Queues, Linked List - Hash Tables - Hash Functions

    Test #2 - (Part 3 of the course: Advanced Data Types)


    When: 18th November, during class
    Where: VIRTUAL, on Blackboard
    Test #2 will cover the following topics:
    Binary Search trees - B-trees - Graphs

    Final Exam - (Part 4 of the course: Algorithms on Graphs and NP-completeness)


    When: TBD
    Where: VIRTUAL, on Blackboard
    Final Exam will cover the following topics:
    Graphs: strongly connected components - Graphs: minimum spanning tree - Graphs: single-source shortest path - NP-completeness - Approximation Algorithms