Marquette University, view of Wisconsin Avenue  

Algorithms

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