Marquette University, view of Wissonsin Avenue  

Algorithms

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 6 class sessions. Your attendence is measured by your participation in the quizzes.

Homeworks are due on time. If your homework has mistakes, I might give you a chance to improve your answer.

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 MTW 1:10 pm - 2:00 or by appointment. (I am serious about the latter, just send me email.) I am going to host a zoom meeting with link https://us02web.zoom.us/j/81258461828?pwd=WElTYlJxRU8ybkhONyt6ZXlFOEZhUT09 and Passcode: 834069. Meeting ID: 812 5846 1828 Passcode: 834069

Piazza Discussion Board

piazza.com/marquette/spring2020/cosc3100

Week 1

Contents

Week 1

Homework

Programming Assignment

Module 0: Introduction

August 26, 2020

Materials

Module 1:

Contents: Finite State Machines and Regular Expressions.

Finite state machines and regular expressions are important software tools arising in a variety of settings. They are also important in theoretical computer science as for the definition of computability, the theory of languages, and the definition of Turing machines.

Learning Goals:

  • Capability to describe and program finite state machines.
  • Capability to use regular expressions to describe strings.
  • Capability to convert between deterministic and non-deterministic finite state machines and regular expressions.

Materials

August 28, 2020

Quiz for August 28 (pdf), -- click here --

Week 2

August 31, 2020

Quiz for August 31 (pdf), -- click here --

September 2, 2020

Quiz for September 2, 2020 (pdf) -- click here

Module 2:

Contents: Computation Models and Landau Notation

Algorithms are evaluated traditionally in a very simple computation model, the RAM model. We discuss some of their inherent inaccuracies and why this model is still important. We also discuss the Landau notation about the growth of functions.

Learning Goals:

  • Understanding of the RAM model and its limitations
  • Capability to evaluate simple pseudo-code in the RAM Model
  • Capability to compare the growth of analytic positive functions

Materials

  • Reading: Sections 2.2 and 2.3 of "Introduction to Algorithms"
  • Reading: Sections 3.1 and 3.2 of "Introduction to Algorithms"
  • MIT class 1 click here
  • MIT class 2 click here

September 2, 2020

September 4, 2020

There are two aspects to algorithms. First, an algorithm has to be correct, that is does the algorithm what the algorithm is supposed to do. Second, and of equal importance in disqualifying an algorithm, does the algorithm solve the problem with a reasonable amount of resources. In the next module, we analyze the Euclidean Algorithm for the greatest common divisor. This algorithm is not only a fundamental building block what is now called the Elementary Theory of Numbers in Mathematics, but it is also useful in analyzing number theoretical cryptography, especially public key systems. The analysis is surprisingly simple and introduces us to the idea of 'loop invariants' and other proof techniques used in Software Engineering.

Our next step is the investigation of divide and conquer algorithms that use recursion heavily. This class of algorithm is ubiquitous and usually is conceptually very simple.

Learning Goals:

  • Understanding the use of Mathematical Induction in Formal Methods for correctness.
  • An intuitive appreciation of loop invariants by example.

Week 3

Module 4: Divide and Conquer

Learning Goals:

  • Develop recursive thinking: ability to design and analyse recursive algorithms.

Assignments for Week 3

September 9, 2020

We look at recursion and backtracking. Recursion can be applied whenever we can build a solution from solutions to similar, but smaller problems. Recursion needs base cases and a recursive step, which makes it very similar to mathematical Induction.

September 11, 2020

Divide and conquer is a very powerful method to obtain good algorithms. It works by reducing a problem into smaller parts, but the smaller parts have the same structure as the original. A divide and conquer algorithm consists of a division / reduction step, that breaks the algorithm into parts, the application of the algorithm on the parts, and a merge step.

Materials

Week 4

Module 5: Master Theorem for Recursion

Learning Goals:

  • Understand and apply the Master Theorem.

September 14, 2020

A class of recurrence equations obtained from Divide and Conquer Algorithms can be solved using the Master Theorem.

Materials

September 16, 2020

Examples for recurrences and asymptotic behavior

September 18, 2020

On Sorting and Selecting: A review of permutations and sorting

Week 5

September 21, 2020

On Sorting and Selecting continued: Selection problems

September 23, 2020

Data Structures for Large Data Sets: Linear Hashing

September 25, 2020

Data Structures for Large Data Sets: Linear Hashing II

Week 6

September 28, 2020

Data Structures for Large Data Sets: B-trees I

September 30, 2020

Data Structures for Large Data Sets: B-trees II

October 2, 2020

Data Structures for Large Data Sets: B-trees and Linear Hashing

Week 7

October 5

Data Structures for Large Data Sets: B-trees and Linear Hashing

October 7

Ordered Lists and Skip Lists

October 9

Dynamic Programming

Week 8

October 12, 2020

Dynamic Programming

October 14, 2020

Midterm for those not in quarantine. Bring laptops to class. You can take the midterm today, but you do not have to. If you do, be on zoom at 9 am. You will get the same midterm, which will be posted here, and you get 10 more minutes to typeset. When you are done, immediately submit the midterm via dropbox as a pdf file.

I will bring paper in an unopened container, but you might prefer to bring your own paper. I will not grade the midterm before Friday to protect against infection.

Week 9

Weekly assignments due October 26, 2020

October 19, 2020

Dynamic Programming

October 21, 2020

Dynamic Programming

October 23, 2020

Greedy Programming: Change making and Scheduling

Week 10

Assignments for Week 10

October 26

Greedy Programming: Huffman Codes

October 28

Graphs: Definitions

October 30

Graphs: Tours, Circuits, Representations

Week 11

Assignments

November 2

Graphs: Topological Sort, Maze problems

November 4

Second Midterm

November 6

Searching in Graphs

Week 12

Assignments

November 9, 2020

Depth First Search and applications

November 11, 2020

Strongly connected components

November 13, 2020

Distances in Graphs

Week 13

Assignments

Distances in Graphs

November 16

Spanning Trees

November 18

Calculability

November 20

Calculability and the Halting Problem

Week 14

November 23

P vs. NP

Final

Finis