Algorithm Analysis and Design

CMPT 435 | Spring 2018
112 Tuesdays and Fridays | 8 am - 9:15 am | LT 013
800 Wednesdays | 8 am | HC 2017
801 Fridays | 11 am - 12:15 pm | HC 2017

Think. Code. Sleep. Repeat.

Comic Image
Comic Image
Comic Image
Comic Image
Comic Image
Comic Image
Comic Image

Course Description

This course continues the study of data structures and algorithm complexity from a more mathematically formal viewpoint. Time complexity of algorithms will be examined using Big Oh notation for worst-, best-, and average-case analyses. The ideas of polynomial-time, NP, exponential, and intractable algorithms will be introduced. Elementary-recurrence relation problems relating to recursive procedures will be solved. Sorting algorithms will be formally analyzed. Strategies of algorithm design such as backtracking, divide and conquer, dynamic programming, and greedy techniques will be emphasized. We will be using the Java programming language as our base language.

Prerequisites:

CMPT 221 - Software Development II
MATH 205 - Discrete Mathematics

This course requires proficiency in some of the basic areas of mathematics such as arithmetic and algebra. Please make sure you feel confident in all these subjects prior to starting this course.

Credit Hours: 3


Not sure if this course is right for you?

Quite honestly, this is a difficult course. My recommendation is to attend lectures, write Java programs, study hard, code some more, start projects early, and seek help from the professor when you need it. If this is something you are committed do, this course might be right for you.

Textbook

Mandatory textbooks: The following books are classics that have also proven to be useful for students: Further resources include:

Objectives

At the completion of this course, students will be able to:
  • Further know the science of designing algorithms.[1,2]
  • Understand and correctly use complex data structures.[1,2]
  • Read programming problems and identify feasible algorithms to solve them.[1,2]
  • Believe in the nature of objects as consisting of data and methods.[1,2]
  • Combine mathematical analysis and algorithms for problem solving.[1,2]
  • Enjoy declaring and manipulating arrays.[1,2]
  • Look at a computer program and determine its complexity.[1,2]
  • Practice finding some answers for themselves, because capable problem solvers never stop learning.[1,2]
Numbers in square brackets indicate the specific goals of the Department of Computing Technology that are being fulfilled.

Schedule

The weekly coverage might change as it depends on the progress of the class. However, you must keep up with the reading assignments.

Week Date Content
1 1/15-1/19 Overview, Java review.
Reading assignment: Ch. 1.1 - 1.6
Project 0, Homework 0, and Project 1 assigned.
2 1/22-1/26 Algorithm analysis.
Reading assignment: Ch. 2.
3 1/29-2/2 Algorithm analysis.
Homework 1, and Project 2 assigned.
4 2/5-2/9 ADTs, lists, stacks, queues.
Reading assignment: Ch. 3.1-3.3, 3.6-3.7.
5 2/12-2/16 Trees.
Reading assignment: Ch. 4.
Homework 2, and Project 3 assigned.
6 2/19-2/23 Trees.
7 2/26-3/2 Heaps.
Reading assignment: Ch. 6.
Homework 3, and Project 4 assigned.
8 3/5-3/9 Midterm Exam.
Heaps.
3/12-3/16 No class. Spring break.
9 3/19-3/23 Hashing.
Reading assignment: Ch. 5.
10 3/26-3/30 Hashing.
Homework 4, and Project 5 assigned.
3/30 No class. He is risen.
11 4/2-4/6 Sorting.
Reading assignment: Ch. 7 (skip 7.4).
12 4/9-4/13 Sorting, Graphs.
Reading assignment: Ch. 9.1-9.5.
Homework 5, and Project 6 assigned.
4/17 No class. Assessment day.
13 4/16-4/20 Graphs.
14 4/23-4/27 Graphs.
15 4/30-5/4 Disjoint set, Algorithm design.
Reading assignment: Ch. 8 and 10.
800 5/9 Final Exam at 8 am.
801 5/9 or 5/11 Final Exam at 1 pm.
112 5/11 Final Exam at 8 am.

Policies

Grade Distribution

Grades will be assigned based on the following breakdown:
Homework 25%
Projects 30%
Midterm exam 20%
Final exam 25%

Important: Each project not completed by the end of the semester will result in a drop of one letter grade. For example, if you would have received a 'B', but you did not complete two of the projects, then your letter grade will be a 'D'.

This course also involves quizzes for some classes at random. Such quizes will be either given in printed form, or will be made available on iLearn and you should take them and answer them by hand or electronically on iLearn. The quizzes are not directly counting toward your grade (see percentages above), but they will count as extra knowledge toward your course preparation. The main idea of the quizzes is that they will help you prepare for the projects, and the accuracy with which you answer them will give you an idea of the grade you could expect in your projects or homework. To prepare for the quizzes and the class, you must do the required reading indicated in the tentative course outline for that week, and you must be making timely progress toward your assigned homework, reading, and projects. That is all you need to be successful in each quiz.

Letter Grade Distribution

Final letter grades will be assigned at the discretion of the instructor, but here is a minimum guideline for letter grades:
A: 100-95, A-: <95-90, B+: <90-87, B: <87-83, B-: <83-80,
C+: <80-77, C: <77-73, C-: <73-70, D+: <70-65, D: <65-60,
F: <60

Course Policies

General

  • The class website contains the official course information (reev.us/cmpt435s18). Please check it regularly for updates.
  • All work in this course is strictly individual, unless the instructor explicitly states otherwise. While discussion of course material is encouraged, collaboration on assignments is not allowed. Collaboration includes (but is not limited to) discussing with anyone (other than the professor) anything that is specific to completing an assignment. You are encouraged to discuss the course material with the professor, preferably in office hours, and also by email.
  • Bring any grading correction requests to your professor's attention within 2 weeks of receiving the grade or before the end of the semester, whichever comes first.

Grades

  • Grades in the C range represent performance that meets expectations; Grades in the B range represent performance that is substantially better than the expectations; Grades in the A range represent work that is excellent.
  • Grades will be maintained in the LMS course shell. Students are responsible for tracking their progress by referring to the online gradebook.

Attendance and Absences

  • Attendance is expected and will be taken each class. You are allowed to miss 2 classes (1 class for hybrid) during the semester without penalty. Any further absences will result in point and/or grade deductions.
  • A total of 6 absences (3 for hybrid) absences will automatically cause an F grade.
  • Students are responsible for all missed work, regardless of the reason for absence. It is also the absentee's responsibility to get all missing notes or materials.

Academic Honesty

Introduction

In addition to skills and knowledge, Marist College aims to teach students appropriate Ethical and Professional Standards of Conduct. The Academic Honesty Policy exists to inform students and Faculty of their obligations in upholding the highest standards of professional and ethical integrity. All student work is subject to the Academic Honesty Policy. Professional and Academic practice provides guidance about how to properly cite, reference, and attribute the intellectual property of others. Any attempt to deceive a faculty member or to help another student to do so will be considered a violation of this standard.

Instructor's Intended Purpose

The student's work must match the instructor's intended purpose for an assignment. While the instructor will establish the intent of an assignment, each student must clarify outstanding questions of that intent for a given assignment.

Unauthorized/Excessive Assistance

The student may not give or get any unauthorized or excessive assistance in the preparation of any work.

Authorship

The student must clearly establish authorship of a work. Referenced work must be clearly documented, cited, and attributed, regardless of media or distribution. Even in the case of work licensed as public domain or Copyleft, (See: http://creativecommons.org/) the student must provide attribution of that work in order to uphold the standards of intent and authorship.

Declaration

Online submission of, or placing one's name on an exam, assignment, or any course document is a statement of academic honor that the student has not received or given inappropriate assistance in completing it and that the student has complied with the Academic Honesty Policy in that work.

Consequences

An instructor may impose a sanction on the student that varies depending upon the instructor's evaluation of the nature and gravity of the offense. Possible sanctions include but are not limited to, the following: (1) Require the student to redo the assignment; (2) Require the student to complete another assignment; (3) Assign a grade of zero to the assignment; (4) Assign a final grade of "F" for the course; and (5) Notify the Dean of the School of Computer Science and Mathematics about the issue. A student may appeal these decisions according to the Academic Grievance Procedure. (See the relevant section in the Student Handbook.) Multiple violations of this policy will result in a referral to the Conduct Review Board for possible additional sanctions.

To Conclude

Dr. Rivas takes academic honesty very seriously, after all, he also teaches Ethics. Many studies, including one by Sheilah Maramark and Mindi Barth Maline have suggested that "some students cheat because of ignorance, uncertainty, or confusion regarding what behaviors constitute dishonesty" (Maramark and Maline, Issues in Education: Academic Dishonesty Among College Students, U.S. Department of Education, Office of Research, August 1993, page 5). In an effort to reduce misunderstandings, here is a minimal list of activities that will be considered cheating in this class:
  • Using a source other than the optional course textbooks, the course website, or your professor to obtain credit for any assignment.
  • Copying another student's work. Simply looking over someone else's source code is copying.
  • Providing your work for another student to copy.
  • Collaboration on any assignment, unless the work is explicitly given as collaborative work. Any discussion of an assignment or project is considered collaboration.
  • Plagiarism.
  • Studying tests or using assignments from previous semesters.
  • Providing someone with tests or assignments from previous semesters.
  • Turning in someone else's work as your own work.
  • Giving test questions to students in another class.
  • Reviewing previous copies of the instructor's tests without permission from the instructor.

Data for Research Disclosure

Any and all results of in-class and out-of-class assignments and examinations are data sources for research and may be used in published research. All such use will always be anonymous.

About The Professor

Pablo Rivas is a professional member of the ACM and IEEE. His degrees are in computer science (B.S. '03), electrical engineering (M.S. '07), and electrical and computer engineering (Ph.D. '11 from the University of Texas at El Paso). Currently, He is an Assistant Professor of Computer Science at Marist. Before that, he was a postdoc at Baylor University.

At Baylor he had the opportunity to work on different aspects of machine learning, data science, big data, and large-scale pattern recognition. Perhaps you have heard on NPR about one of his most recent projects on the detection of leukocoria (see leuko.net for more info), where they used deep learning and image-processing techniques, which he loves. Another recent research project originated after an internship at NASA Goddard Space Flight Center where he worked in the detection of a particular kind of atmospheric particle using different machine learning methods. He currently works to make that remote sensing project available on-line in real time.

In the past he worked as Software Engineer for about 8 years; thus, he is quite familiar with programming languages, particularly C++, Java, and Python, but he likes to use MATLAB in order to save time when developing the prototypes of his algorithms.

He has been recognized for his creativity and academic excellence; for instance, he received the IEEE Student Enterprise Award in 2007, and the Research Excellence Award from the Paul L. Foster Health Sciences School of Medicine of Texas Tech University in 2009. In 2011, he had the honor of being inducted to the International Honor Society Eta Kappa Nu (HKN).

When he is not having fun doing research or teaching, he also likes to play basketball, code, eat pizza with friends, or go to the movie theater with his beautiful wife Nancy.

How to Contact The Professor

Dr. Rivas' office number is 3040 @ the Hancock Center, and office hours are:
  • Tuesdays 9:30 AM - 11:30 AM
  • Wednesdays 5:00 PM - 6:00 PM
  • Fridays 2:00 PM - 3:00 PM

He is glad to talk to students during and outside of office hours. If you can't come to his office hour, please make an appointment for another time, or just stop by if you see the door open. If you are going to stop by it is a good idea to check his schedule and call first to make sure he is there; the number is (845) 575 3000 x2086.


If extra help is needed, there are private tutors available at the student's expense at Marist's Academic Learning Center.


Note: Any student who needs learning accommodations should inform Dr. Rivas immediately at the beginning of the semester. The student is responsible for obtaining appropriate documentation and information regarding needed accommodations from the Office of Accommodations and Accessibility in Donnelley 226 (or online here) and providing it to the professor early in the semester.