# MAT2440 – Ganguli – Spring 2022

Discrete Structures & Algorithms

Coursera is a  massive open online course (“MOOC”) platform created by Stanford CS professors a decade ago. I just noticed they are offering a free Princeton University algorithms course: https://www.coursera.org/learn/algorithms-part1

Here is the course description:

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.

There is some overlap with what we are covering in Chapter 3, but it looks like this course will go much further in depth. It looks like it may also overlap somewhat with CST3650 (Data Structures).

If you are serious about continuing with computer science/programming, I would strongly suggest working through this course–perhaps this summer, if you have time.

Here are parts of the Coursera course which overlap with our course:

• Week 1:

For example, here is a very nice and relevant screenshot from the “Order-of-Growth Classifications” lecture:

You could also look at the Week 3 lectures, which cover two more advanced sorting algorithms:

Here is a screenshot from the lecture on mergesort, which is an example of a “recursive” algorithm (the topic of recursion and recursive algorithms is covered in MAT2540 and Sections 5.3 & 5.4 of the Rosen textbook; see also the wikipedia entry for Recursion):

Just a reminder that we will have our final exam on Monday, during our regular class time.

A handful of people logged on to Blackboard Collaborate for office hours earlier today. I recorded the session, so you can view the recording on Blackboard (go to our Collaborate Ultra page and click on the menu button in the upper left to switch to “Recordings”)

I went over a mathematical induction proof, reviewed some basic algorithms in pseudocode, and outlined what sort of topics/exercises to review for the final:

• propositional logic e.g., truth table: see Exam #1
• direct proofs and indirect proofs (i.e., proofs by contraposition): see Quiz #2 and Exam #2
• set operations and functions (including domain/range, definitions of one-to-one and onto functions): see Exam #2
• algorithms (writing simple algorithms in pseudocode; executing the basic search and sorting algorithms; big-O estimates of running-times): Exam #3 & Quiz #3
• proof by mathematical induction: Exam #3 & Sec 5.1

I will post solutions to Exam #3 and Quiz #3, so that you can review the solutions of those.

[Sorry for the delay in posting this class update]

Topics:

• reviewed HW#4 exercises from Sec 3.2 & 3.3:
• Sec 3.2: shortcuts to figuring out big-O estimates for given functions (in particular polynomials, and functions that “look like” polynomials)
• Sec 3.3: shortcuts to figuring out big-O estimates for given algorithms (in particular based on loops and nested loops)
• introduced Sec 5.1: Mathematical Induction
• framework for a proof by induction: used to to prove a statement P(n) is true for all positive integers n, consists of two steps:
• “base case” (usually P(1), i.e, show the statement holds for n = 1)
• “induction step”: show that “P(k) implies P(k+1)” (for an arbitrary positive integer k)
• sketched proof of “1 + 2 + 3 + … + n = n(n+1)/2”
• see slides and/or Example 1 in Sec 5.1
• handed out Exam #3 (take-home due Thursday) – pdf also available via OpenLab Files

Schedule for remainder of semester:

• Wed May 18: finish mathematical induction; address Exam #3 questions; review for final exam
• Thurs May 19: Exam #3 due (either submit hard copy to math dept office (N711) or submit pdf via Blackboard)
• Fri May 20: Office hours (via Blackboard Collaborate) for final exam review and Exam #1/#2 corrections: 12-2p
• Mon May 23: Final exam, 12p-1:40p (& Exam #1/#2 corrections due)

Topics:

• Review insertion sort algorithm (Sec 3.1), look at its time complexity (Sec 3.3: O(n^2))
• HW#4 exercises from Sec 3.1 & 3.2:
• Sec 3.1, #42 (insertion sort)
• Sec 3.2, #5 & 23 (showing “big-O” relationships using graphs)

Schedule for remainder of semester:

• Thurs May 12 & Fri May 13: Office hours (via Blackboard Collaborate) for questions re HW#4
• Thurs: 10a-11a
• Fri: 12p-2p
• Mon May 16: HW#4 due; hand out Exam #3 (take-home)
• Wed May 18: Exam #3 due
• Thurs May 19 & Fri May 20: Office hours (via Blackboard Collaborate) for final exam review (times TBA)
• Mon May 23: Final exam

Boardshots:

Theme by Anders NorenUp ↑