Introduction to the Course
Algorithms is an important as well as difficult topic that demands of its students a certain mathematical sophistication. I will try to provide additional resources in case that your class in Discrete Mathematics did not touch on certain topics, but these resources a no substitute for taking the full class.
To underline the importance of algorithms, I will be mining collections of programming interviews such as the book "Elements of Programming Interviews in Python" by Aziz, Lee, and Prakash for quiz and exam questions. You can use Python, C, or C++ to submit your code.
As Marquette students, you should have signed the honor's code. Violation of the honor's code will be dealt with in the humane way that the university committee on academic misconduct offers. If you collaborate with a person on homework, make a statement to this purpose. If you collaborate with a person on examinations or quizzes, you are violating the honor's code.
This class is intended to be an inverted class and I expect you to study the topic of the class before we meet. As we might have to move to a complete on-line format, you will have to attend zoom meetings at the scheduled class time. We will spend the class time deepening your understanding by lectures on particular difficult topics, activities, and quizzes. There is no make-up for missed quizzes.
The university has a policy of automatic drops for non-attendance, equivalent to two weeks of classes. This means that you will be dropped from the class, if you have not attended 4 class sessions. Your attendence is measured by your participation in the quizzes.
Homeworks are due on time. If your homework has mistakes, you can resubmit within one week for a discount of 33% of the missing points. (E. g.
Please monitor your grading, the interface of D2L makes it easy to loose freshly entered grades.
Syllabus
Here is the complete syllabus. --Click here.--
Office Hours
- Thomas Schwarz TTh 3:30 pm - 4:30 or by appointment. (I am serious about the latter, just send me email.)
Contents
Homework
- Homework 1 -- Click here -- , due September 3 via D2L
- Homework 1 Solutions -- Click here --
- Homework 2 -- Click here -- , due September 10 via D2L
- Homework 2 Solutions -- Click here --
- Homework 3 -- Click here -- , due September 17 via D2L
- Homework 3 Solutions -- Click here --
- Homework 4 -- Click here -- , due September 24 via D2L
- Homework 4 Solutions -- Click here --
- Homework 5 -- Click here -- , due October 1 via D2L
- Homework 5 Solutions -- Click here -- , due October 1 via D2L
- Homework 6 -- Click here -- , due October 8 via D2L
- Homework 6 Solutions -- Click here --
- Homework 7 -- Click here -- , due October 29 via D2L
- Homework 7 Solutions -- Click here --
- Homework 8 -- Click here -- , due November 6 via D2L
- Homework 8 Solutions -- Click here --
- Homework 9 -- Click here -- , due November 12 via D2L
- Homework 9 Solutions -- Click here --
- Extra Credit Homework: No collaboration at all, no web searches: -- Click here -- , due Dec 8, 2024
- Homework 10 -- Click here -- , due November 19 via D2L
- Homework 11 -- Click here -- , due November 26 via D2L
- Homework 12 -- Click here -- , due December 8 via D2L
Midterm
- Midterm Preparation -- Click here -- , due October 13 (Sunday Evening!) via D2L
- Midterm Prep 1 -- Click here --
- Midterm Prep 1 Solution -- Click here --
- Midterm Prep 2 -- Click here --
- Midterm Prep 3 -- Click here --
- Midterm Prep 3 Solution -- Click here --
- Midterm Prep 4 -- Click here --
- Midterm Prep 4 Solution -- Click here --
- Midterm Prep Q and A Recording -- Click here --
- Midterm Preparation Solution -- Click here --
- Midterm -- Click here --
- Midterm Solutions -- Click here
Final
Programming Assignment
- Programming Assignment 1 -- Click here -- , due September 10, 2024 via D2L via D2L
- Programming Assignment 1 Presentation -- Click here --(mp4)
- Programming Assignment 1 -- Click here --(mp4)
- Programming Assignment 1 -- Click here --
- Programming Assignment 2 -- Click here -- , due September 17, 2024 via D2L
- Programming Assignment 2 -- Click here for hints--
- Programming Assignment 3 -- Click here -- , due September 24, 2024 via D2L
- Programming Assignment 4 -- Click here -- , due October 1, 2024 via D2L
- Programming Assignment 4 code -- Click here --
- Programming Assignment 6 -- Click here -- , due October 1, 2024 via D2L
- Programming Assignment 6 code -- Click here --
- Programming Assignment 6 Presentation -- Click here --
- Programming Assignment 6 Presentation (mp4) -- Click here --
- Programming Assignment 6 -- Click here -- , due October 1, 2024 via D2L
- Programming Assignment 7 -- Click here -- , due October 29, 2024 via D2L
- Programming Assignment 8 -- Click here -- , due November 6, 2024 via D2L
- Programming Assignment 9 -- Click here -- , due November 12, 2024 via D2L
- Programming Assignment 10 -- Click here -- , due November 19, 2024 via D2L
- Programming Assignment 10 LH -- Click here --
- Programming Assignment 10 Trace -- Click here --
- Programming Assignment 11 -- Click here --
Contents
- August 27, 2024: Overview -- Click here --
- August 29, 2024: DFA -- Click here --
- September 3, 2024: Regular Expressions -- Click here --
- September 5, 2024: Measuring Complexity and Asymptotic Growth Classes -- Click here --
- September 10, 2024: Correctness: Euclidean Algorithm, Loop Invariants -- Click here --
- September 12, 2024: Recursion -- Click here --
- September 12, 2024: Backtracking -- Click here --
- September 17, 2024: Divide and Conquer -- Click here --
- September 19, 2024: Recurrence Relations -- Click here --
- Quiz, September 19, 2024: -- Click here --
- September 24, 2024: Sorting, Maxima, Minima, Media -- Click here --
- September 26, 2024: Sorting, Maxima, Minima, Media -- Click here --
- October 1, 2024: Data Structures: B-Trees -- Click here --
- October 3, 2024: Data Structures: Linear Hashing -- Click here --
- October 8, 2024: Data Structures: Skip Lists -- Click here --
- October 10, 2024: Greedy Algorithms -- Click here --
- October 15, 2024: Midterm
- October 22, 2024: Dynamic Programming -- Click here --
- October 24, 2024: Dynamic Programming -- Click here --
- October 29, 2024: Dynamic Programming -- Click here --
- October 29, 2024: Strings -- Click here --
- October 31, 2024: Graphs -- Click here --
- November 5, 2024: Searching in Graphs -- Click here --
- November 7, 2024: Applications of Depth-First Search -- Click here --
- November 12, 2024: Distances -- Click here --
- November 14, 2024: Spanning Trees -- Click here --
- November 14, 2024: Maximum Flows -- Click here --
- November 19, 2024: Turing and Halting Problem -- Click here --
- November 21, 2024: Complexity Classes -- Click here --
- November 26, 2024: Reductions -- Click here --
- December 3 2024: Travelling Salesman Problem: How to deal with difficult problems -- Click here --