# 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

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)

There are four evaluations:

 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

### 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:
 Insertion Sort -- Solutions Analysis of Insertion Sort -- Solutions Merge Sort -- Solutions MergeSort.png Asymptotic Notation and Recurrence Equations -- Solutions

### 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:
 Heap Sort -- Solutions Quick Sort -- Solutions Stacks, Queues, and Linked Lists -- Solutions Hash Tables and Hash Functions -- Solutions

### 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:
 Binary Search Trees -- Solutions B-Trees -- Solutions Graphs -- Solutions

### 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:
 Minimum Spanning Tree -- Solutions Single-source Shortest Paths -- Solutions