## 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

- Homework 1 -- Click here -- , due September 4, 2020 via D2L

### Programming Assignment

- Programming Assignment 1 -- Click here -- , due September 4, 2020 via D2L
- Programming Assignment Presentation -- Click here --(mp4)

### Module 0: Introduction

August 26, 2020

#### Materials

- Presentation (keynote) -- Click here --
- Presentation (ppt) -- Click here --
- Presentation (pdf) -- Click here --
- Models of computing (mp4 / 10 min) -- Click here --
- Evaluation of algorithms (mp4 / 8 min) -- Click here --
- Overview of class (mp4 / 2 min) -- Click here --

### 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 --

- Presentation (keynote) -- Click here --
- Presentation (ppt) -- Click here --
- Presentation (pdf) -- Click here --
- Presentation (mp4, 7min) Transitions -- Click here --
- Presentation (mp4, 10min) Definition of Automata -- Click here --
- Presentation (mp4, 10min) Non-deterministic Finite Automata -- Click here --
- Worksheet (pdf) -- Click here --

## Week 2

- Programming Assignment 2 -- Click here -- , due September 11, 2020 via D2L
- Programming Assignment Presentation (mp4) -- Click here --(mp4)
- Programming Assignment Presentation (pdf) -- Click here --(mp4)
- Homework 2 -- Click here --(mp4) , due September 11, 2020 via D2L

### August 31, 2020

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

- Regular Expressions Presentation (keynote) -- Click here --
- Regular Expressions Presentation (pdf) -- Click here --
- Regular Expressions Presentation (mp4) -- Click here --
- Regular Expressions Worksheet -- Click here --
- Regular Expressions to NFA (keynote) -- Click here --
- Regular Expressions to NFA (pdf) -- Click here --
- Regular Expressions to NFA (mp4) -- Click here --

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

- DFA to Regular Expression (keynote) -- Click here --
- DFA to Regular Expression (pdf) -- Click here --
- DFA to Regular Expression (mp4) -- Click here --
- Moody and Mealy machines (mp4) -- 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

- The RAM model of computing (key) -- click here
- The RAM model of computing (pdf) -- click here
- The RAM model of computing (mp4) -- click here
- Growth of Functions and Landau Notation (key) -- click here --
- Growth of Functions and Landau Notation (pdf) -- click here --
- Growth of Functions and Landau Notation (mp4) -- click here --

### 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.

- Loop Invariants and the Euclidean Algorithm (key) click here
- Loop Invariants and the Euclidean Algorithm (pdf) click here
- Loop Invariants and the Euclidean Algorithm (mp4) click here
- A Mathematical View: Georgia Tech Open Resources: Induction and Euclidean Algorithm -- Click here --
- The correctness proof (MIT Open Courseware) -- Click here --

## Week 3

### Module 4: Divide and Conquer

#### Learning Goals:

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

### Assignments for Week 3

- Homework 3 -- Click here --
- Programming Assignment 3 -- Click here --
- Code from Programming Assignment 3 -- Click here

### 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.

- Presentation on Recursion (keynote) -- Click here --
- Presentation on Recursion (pdf) -- Click here --
- Presentation on Recursion (mp4) -- Click here --
- Presentation on Backtracking (keynote) -- Click here --
- Presentation on Backtracking (pdf) -- Click here --
- Presentation on Backtracking (mp4) -- Click here --

### 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

- Presentation (keynote) -- Click here --
- Presentation (ppt) -- Click here --
- Presentation (pdf) -- Click here --
- A conceptual introduction to integer arithmetic for background: -- Click Here --
- Divide and conquer -- MIT Open Courseware: -- Click Here --

## Week 4

- Homework 4 [click here]
- Programming Assignment 4 [click here]
- A maybe helpful additional example (pdf click here)

### 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

- Presentation (keynote) -- Click here --
- Presentation (ppt) -- Click here --
- Presentation (pdf) -- Click here --
- Master Method (MIT): -- Click Here --

### September 16, 2020

Examples for recurrences and asymptotic behavior

- Worksheet (pdf) -- Click here --

### September 18, 2020

On Sorting and Selecting: A review of permutations and sorting

- Presentation (keynote) -- Click here --
- Presentation (ppt) -- Click here --
- Presentation (pdf) -- Click here --

## Week 5

- Programming Assignment [click here]
- Homework (optional) [click here]

### September 21, 2020

On Sorting and Selecting continued: Selection problems

- Presentation (keynote) -- Click here --
- Presentation (ppt) -- Click here --
- Presentation (pdf) -- Click here --

### September 23, 2020

Data Structures for Large Data Sets: Linear Hashing

- Presentation (keynote) -- Click here --
- Presentation (ppt) -- Click here --
- Presentation (pdf) -- Click here --

### September 25, 2020

Data Structures for Large Data Sets: Linear Hashing II

- Presentation (keynote) -- Click here --
- Presentation (ppt) -- Click here --
- Presentation (pdf) -- Click here --

### 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: Skip Lists

## Week 7

### October 5

Dynamic Programming

### October 7

Dynamic Programming

### October 9

Dynamic Programming

## Week 8

### October 12, 2020

Greedy Programming

### Octoboer 14, 2020

Greedy Programming