Syllabus
Algorithms
 Contact Information Course Description Course Goals and Objectives Course Outline Calendar Course Materials Grading Attendance and Participation Assignments Honesty

## Contact Information

 Professor Richard J. Povinelli, Ph.D. E-mail richard.povinelli@marquette.edu Homepage http://povinelli.eece.mu.edu D2L https://d2l.mu.edu/ Phone 414.288.7088 Office Hours Haggerty Hall 221

## Course Description and Prerequisites

Introduction to the analysis of algorithms. topics include: asymptotic complexity notation, recursion analysis, basic and advanced data structures, sorting methodologies, dynamic programming, and graph algorithms, including heuristic search techniques such as best-first and A* algorithms. Advanced topics include NP-completeness theory and linear programming.

Prerequisites: Data Structures and Discrete Mathematics.

## Course Goals

By the end of this course, you should...
• Provide graduate students with a solid foundation in computer algorithms, with the emphasis on how they are applied to solving real-world problems in a variety of science, engineering, and other fields.

## Course Objectives

By the end of this course, you should...
• Understand the fundamental concepts of algorithms, and the problem solving methodologies using algorithms in science and engineering fields.
• Understand the concepts of Time and Space Complexity and know how to represent the complexity in Asymptotic Notations.
• Be capable of applying Master Theorem to analyze recurrent algorithms.
• Understand how the data structures are applied to the algorithm design, and how to use them given the problem to be solved.
• Be familiar with sorting and searching algorithms, and their time and space complexity.
• Understand how Greedy algorithms and Dynamic Programming work.
• Understand and be capable of applying Linear Programming in solving optimization problems.
• Be familiar with intelligent algorithms such as A-star, and the concept of AI and Machine Learning.
• Understand the concept of NP-Completeness.
• Be capable of programming the algorithms in Matlab and other selected programming languages, such as JAVA and C#.

## Course Outline

What When
Role of Algorithms (CLRS 1) wk 1
Getting Started (CLRS 2) wk 1
Growth of Functions (CLRS 3) wk 2
Divide and Conquer (CLRS 4) wk 2
Probabilistic Analysis and Randomized Algorithms (CLRS 5) wk 3-4
Quicksort (CLRS 7) wk 5
Sorting in Linear Time (CLRS 8) wk 6
Red-Black Trees (CLRS 13) wk 7
Augmenting Data Structures (CLRS 14) wk 9
NP-Completeness (CLRS 34) wk 10-11
Dynamic Programming (CLRS 15) wk 12-13
Greedy Algorithms (CLRS 16) wk 14
Approximation Algorithms (CLRS 35) wk 15

## Course Materials

### Required Texts

What Number Value per Total
Homeworks 14 ~2% 30%
Midterm Exam 1 30% 30%
Final Exam 1 40% 40%
Total 100%

NOTE: All dates and numbers are subject to change as deemed necessary!

 93+ A 90-93 A- 87-90 B+ 83-87 B 80-83 B- 77-80 C+ 73-77 C 70-73 C- 67-70 D+ 60-67 D 0-60 F

The grading scale is the most stringent one you will be held to, i.e. I can give you a higher letter grade than shown on the scale, but never a lower one. If you have missing assignments, you are inelligible to receive a higher grade.

### Late Assignments

I will deduct 5% for assignments up to one day late, 10% for two days late, and 15% for up to three days late, and so on up to a maximum of 50% off. Assignments are due at the beginning of class. They are late after that. Assignments are not accepted after solutions have been distributed, nor after the last day of class. In class assignments are only accepted during the class period they are assigned.

## Attendance and Participation

I have always enjoyed teaching classes where the students actively participate - a conversation is more fun than a monologue! Although there is no specific credit assigned for attending, it is still expected. There may be in class graded assignments. These may be turned in only during the class period they are given.

## Assignments

You should expect to spend, on average, from twelve (12) to fifteen (15) hours on reading, homeworks, and other preparation for this class. This time is in addition to the three (3) hours of lecture you are expected to attend every week.

Homework assignments must be hand written. Code and other portions must be submitted in the proper electronic format. I will deducted 5% from incorrectly formatted assignments.

All assignments must be turned in via D2L. The handwritten portions must be electronically scanned and coverted to pdf. Assignments are due according to the time specified in the calendar .

All written portions of assignments must be created using a word processor. No part of the writeup may be hand drawn. The assignments are to be well written with proper spelling and grammar. Points will be deducted for poorly written assignments. Written portions of assignments must be turned in as MS Word documents (.docx format). Code and other portions must be submitted in the proper electronic format. I will deducted 5% from incorrectly formatted assignments.

All assignments must be turned in via D2L. Assignments are due according to the the time specified in the D2L calendar.

### Homeworks

There will be 14 homeworks, which will be collected and graded. The homework assignments will be scaled to 330% of your grades. The homeworks will be combinations of questions from the book and programming problems. You must cite, using IEEE format, your references including online ones.

## Exams

There will be a midterm exams each worth 30% and a final exam worth 40% points.