FINAL EXAM LOCATIONS - FRIDAY DEC 16 4:00PM - 6:00PM

Hervé's Section 0101:

BRB 1101 (Biosciences Research Building)

Justin's Section 0201:

If your last name starts with A - M you are in ARM 0126 (Armory)
If your last name starts with N - Z you are in ARM 0131 (Armory)

FINALS WEEK TA OFFICE HOURS

Monday as usual.
Tue 12:00 - 2:00
Wed 12:00 - 2:00
Thu 10:30 - 3:00
Fri 10:00 - 12:30

CO-TEACHING

Hervé Franceschi and Justin Wyss-Gallifent will be co-teaching this class in the sense that our homework and TAs are shared. We will be giving different exams, however, since they are on different days of the week. To keep things fair, though, Justin's exams will also be 50 minutes long.

ONLINE POSTING OF LECTURE MATERIAL

Justin will be using a tablet to write notes in class, broadcasted to the screens in the lecture hall. These notes will be posted to Canvas.
Hervé will be using powerpoint slides broadcasted to the screens in the lecture hall; these slides will also be posted on Canvas

MATERIAL

The official course material is the set of notes found here:

https://www.math.umd.edu/~immortal/CMSC351/

A frequent text for this course and a good resource for other problems and approaches is Introduction to Algorithms, 3rd Edition, by Cormen, Leiserson, Rivest, Stein.

BRIEF COURSE DESCRIPTION

The idea of this course is to cover the design and analysis of algorithms. We'll begin with an overview of big Ο, Ω, and Θ notation followed by an overview of aspects of the design process. Then we'll look at list-related algorithms, make sure we understand how they work and analyze time complexity as well as variations on those algorithms. After that we'll look at some calculation- and statistics-related algorithms with the same approach. Next we'll look at some basic graph theory and graph-theoretic algorithms. We'll finish the course with an overview of NP-completeness. During this we will, as much as possible, compare algorithms from various angles (speed versus transparency, for example).

HOMEWORK

There will be one homework per week, collected on Gradescope, due before 11:59pm on the Wednesday following the week we cover the material. You are welcome to talk with each other and use resources to help you understand the material but it is understood and implied that the homework you write up and submit is your own work, from your own brain, and that you understand what you are writing and submitting. It is assumed that by now you know how to properly upload and tag problems on Gradescope but if not, make sure you meet with one of us or a TA to go through the process with your first homework.

We will count only your highest 10 homeworks. The rest will be dropped.

Mistagged problems will earn no credit. You've all been submitting via Gradescope long enough to know how!

EXAMS

There will be three non-cumulative semester exams and a cumulative final exam.

TURNING HOMEWORK IN LATE

Homework will not be accepted late. There are no exceptions to this.

POINT TOTAL AND GRADING

Homework = 200
Exams = 3x100 = 300
Final = 200
Total = 700

OFFICE HOURS AND HELP

In order to make it clear what the TAs can and cannot do during office hours, especially regarding homework assistance, we have created guidelines so that both the TAs and students are aware. Please see

https://umd.instructure.com/courses/1328443/pages/ta-assistance-guidelines

Office Hours:

Piazza:

Please use the link on Canvas.

LINK TO UNIVERSITY POLICY ON LOTS OF THINGS

Please be aware of University policy on things like absences, religious observances, etc. Talk with Hervé or Justin if you have questions:

http://www.ugst.umd.edu/courserelatedpolicies.html

SCHEDULE

Date(s)	Topic
Week of Aug 29	Introduction Big Ο, Ω, and ϴ Notation
Week of Sept 5	Note: Monday is Labor Day - No Class Rigorous Time Maximum Contiguous Sum (Might Spill to the Next Week)
Week of Sept 12	Bubble Sort Selection Sort Insertion Sort
Week of Sept 19	Binary Search Review Exam 1 (Justin - Thursday, Hervé - Friday)
Week of Sept 26	Recursion Trees in preparation for the Master Theorem The Master Theorem
Week of Oct 3	Mergesort Heaps and Heapsort
Week of Oct 10	Quicksort Limitations on Comparison-Based Sorting Algorithms
Week of Oct 17	Countingsort Review Exam 2 (Justin - Thursday, Hervé - Friday)
Week of Oct 24	Radixsort Integer Addition and Multiplication Karatsuba's Algorithm
Week of Oct 31	K-th Order Statistics Median of Medians
Week of Nov 7	Introduction to Graphs Shortest Path Algorithm Dijkstra's Algorithm
Week of Nov 14	Spanning Trees - Prim and Kruskal Review Exam 3 (Hervé - Friday, Justin - Thursday)
Week of Nov 21	Monday, Tuesday: TBA Note: Wednesday, Thursday, Friday is Thanksgiving - No Class
Week of Nov 28	Breadth-First Traverse Depth-First Traverse P and NP stuff (Justin)
Week of Dec 5	P and NP stuff Review (Justin)
Week of Dec 12	Monday is the last day of classes. Review (Hervé) Final Exam 4:00pm - 6:00pm Friday - All Classes ARM 0126 and/or ARM 0131 - Specifics TBD