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, at this Zoom link

Readings


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

Lectures


You can find a Zoom link of the recording of each lecture in the calendar of the course on Blackboard (not here).
A quick way to access that: Log in Blackboard, click your name in grey color at the top right, click the calendar icon.



(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

    Exercises:

    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

    For graph visists BFS and DFS, we use these procedures.

    Exercises:

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


    If you are enrolled in Session 201 with classes 2pm-2:50pm: Final exam is on Friday 18th December 8:00am - 8:50am
    If you are enrolled in Session 202 with classes 12pm-12:50pm: Final exam is on Thursday 17th December 8:00am - 8:50am
    Where: VIRTUAL, on Blackboard
    Final Exam will cover the following topics:
    Graphs: minimum spanning tree - Graphs: single-source shortest paths
    Part 4 also covered the topic: NP-completeness, but it is not going to be part of the Final Exam.
    For the topic of NP-completeness, we use the following slides: NP-completeness 1 NP-completeness 2.

    Exercises: