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

Piazza Discussion Board

piazza.com/marquette/spring2020/cosc3100

Week 1

Contents

Week 1

Homework

Programming Assignment

Module 0: Introduction

Monday, January 25, 2021

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

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

Week 2

Programming Assignment

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

February 3, 2021: Landau Notation

Module 3:

February 5 2021: Correctness of Algorithms.

Week 3

Assignments for Week 3

Module 4: Backtracking and Divide and Conquer

February 8, 2021: Backtracking and Divide and Conquer

February 10, 2021: Backtracking and Divide and Conquer

February 12, 2021: Divide and Conquer and Recurrences