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. I personally hate Java and the program does not teach C++, so I prefer to use Python. You can do programming assignments usually in other languages, but sometimes, for example when you measure performance, Java is not allowed.

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.

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 MWF 14:10 - 15:00 or by appointment.

Piazza Discussion Board

piazza.com/marquette/spring2020/cosc3100

Homework

Homework Homework link Due Data
Homework 1 (Module 0) -- Click here >-- January 20, 2020
Homework 2 (Module 1) -- Click here -- February 3, 2020
Homework 3 (Module 2) -- Click here -- February 10, 2020
Homework 3 (Module 3) -- Click here -- February 10, 2020
Homework 4 (Module 4) -- Click here -- February 17, 2020
Homework 4 (Module 5) -- Click here -- February 24, 2020
Homework 5 (Module 6) -- Click here -- March 2, 2020

Examination Preparations

Examination Link
Midterm Sample 1 -- Click here --
Midterm Sample 2 -- Click here --
Midterm Sample 1 Solution -- Click here --
Midterm Sample 3 -- Click here --
Midterm Sample 3 Solution -- Click here --
Midterm B-tree Worksheet -- Click here --
Midterm B-tree Worksheet Solutions -- Click here --
Midterm with Solutions -- Click here --

Contents

Week 1

Module 0: Introduction

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

Week 2

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

Week 3

There are two aspects of quality for an algorithm. Most importantly, does the algorithm do 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.

Module 3: Formal Methods

Learning Goals:

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

Materials

Week 4

Module 4: Divide and Conquer

Learning Goals:

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

Materials

Module 5: Master Theorem for Recursion

Learning Goals:

  • Understand and apply the Master Theorem.

Materials

Module 6: Sorting and Selection

We present and analyze several sorting related algorithms, such as min-max extraction and median finding. Some are of more theoretical interest (such as optimal min-max extraction) and are used to school the analysis of run-times via recursion.

Learning Goals:

  • Capability to use inductive reasoning in the design of an algorithm.
  • Capability to use recurrence relations in order to determine asymptotic runtimes.

Materials

Module 7: Data Structures

This class presumes familiarity with the data structures that are the topic of the Data Structures class at Marquette. We briefly discuss the design criteria for data structures and then concentrate on the two most important data structures for key-value stores, namely the B+ - tree and Linear Hashing. We are also look at skip-lists as an alternative to linear lists with faster look-up times.

Learning Goals:

  • Capability to determine the appropriatness of a data structure to solve specific solutions
  • Understanding of and capability to manipulate the data structures:
    • B-trees
    • B+-trees
    • Linear Hashing
    • Skip Lists

Materials

Asynchronous Distance Learning

Week 1

March 16, 2020: Linear Hashing

March 18, 2020: Linear Hashing

March 20, 2020: Skip Lists

Virtual office hour now on MWF at 14:30 - 17:00

Find the latest information at zoom.html. Please remember to refresh pages.

Week 2

March 23, 2020: Skip Lists 2

March 25, 2020: Dynamic Programming 1

March 27, 2020: Dynamic Programming 2

Week 3

March 30, 2020: Dynamic Programming 3

April 1, 2020: Dynamic Programming 3

Homework for Wednesday, April 9, 2020

Please submit via dropbox on D2L.

April 3, 2020: Greedy Algorithms 1

April 7, 2020: Greedy Algorithms 2

Practice Problem: Palindromic Substrings

Homework due April 17 via dropbox

April 15, 2020: Graph Algorithms: Graph Definition

April 17, 2020: Graph Algorithms: Breadth and Depth First Search Algorithms

April 20, 2020: Uses of Search Algorithms

April 22, 2020: Graph Algorithms: Spanning Trees

April 24, 2020: Graph Algorithms: Distance Calculations

Homework due April 29, 2020

Please submit via dropbox.

April 27, 2020: Impossibilitiy Results

April 29, 2020: Complexity Classes: Definition

May 1, 2020: Complexity Classes: Reduction

Homework due May 6, 2020

Please submit via dropbox.

Final

At the beginning of final's week, you will receive a two-hour take-home final to be submitted by Thursday evening of Final's week. The exam includes a promise by students that they will only use written or electronically published materials, but refrain from using communication to solve the problem.

Incompletes

If you want to obtain an Incomplete because of the disruptions due to the COVID virus, please send me email before Thursday evening.

Finis