Computer Science 430

Algorithm Design and Analysis

Course Description:

Introduction to algorithm design principles, techniques for the analysis of algorithms, problem-solving methodologies, and advanced data structures.  Topics include searching and sorting, divide and conquer, greedy algorithms, dynamic programming, graph algorithms, asymptotic analysis of algorithms, proofs of correctness, and advanced data structures.

Textbook:

1. Required: Introduction to Algorithms, Cormen et. al., 3rd Edition, MIT Press 2009.  ISBN-13 978-0262033848.

• Note: You may be able to get by (and save a bit) with the second edition, but be careful as exercise numbers, wordings, and content may vary slightly.  Please ensure that whatever answers you submit are correctly answering the intended problem.

2. Recommended: Discrete Mathematics with Applications , Epp, 4th Edition, Brooks-Cole 2011.  ISBN-10 0495391328

• This text is recommended for any students who may need a reference for any Discrete Mathematics topics (proof techniques, logic, set theory, etc.).

Coordinator:        Dr. Joshua T. Guerin

Prerequisites:

CSCI 302 and CSCI 325.

Program Educational Objectives--This course addresses the following program educational objectives:

A.        An ability to apply knowledge of computing and mathematics appropriate to the discipline.

B.        An ability to analyze a problem, and identify and define the computing requirements appropriate to its solution.

C.        An ability to design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs.

I.         An ability to use current techniques, skills, and tools necessary for computing practice.

J.        An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices.

K.        An ability to apply design and development principles in the construction of software systems of varying complexity.

Expected Course Outcomes:  The student will be able to

1. Find/prove O/o, Ω/ω, and Θ bounds for iterative and recursive algorithms.
2. Prove the correctness of algorithms.
3. Design efficient algorithms for solving varied computational problems.
4. Describe and employ multiple algorithm design paradigms including divide and conquer, dynamic programming, and greedy.
5. Implement algorithms from pseudocode in a modern, high-level programming language.

Topics:

1. Proofs of correctness/loop invariants
2. Algorithm runtime analysis

1. Growth of functions
2. Analysis of recursive algorithms and recurrence relations
3. The Master Theorem

3. Sorting algorithms

1. Comparison-based sort
2. Non-comparison-based sort

4. Basic search algorithms

1. Breadth-first search, depth-first search

5. Algorithm design paradigms

1. Divide-and-conquer
2. Dynamic programming
3. Greedy Algorithms/Huffman codes

6. Additional algorithms, paradigms, and advanced data structures as time permits

Computer Science 430                                                                Fall 2017

Algorithm Design and Analysis

Instructor:        Dr. Joshua T. Guerin        email: jguerin@utm.edu        Phone: (731) 881-7246

        Office: EPS 101A        Web page: www.utm.edu/staff/jguerin        

Office hours:        See My Schedule

Grading:        Letter grades in this course are assigned using the following scale:

A - 90%--100%

B - 80%--89%

C - 70%--79%

D - 60%--69%

F - 59% or below.

Your grade is calculated based on the following weights:

Assignments

Homework:

Homework assignments will be assigned every 1-2 weeks (roughly corresponding to book sections covered).  Homework assignments will consist primarily of paper homework from the class textbook or other sources.  Students will be given approximately one week to work on homework assignments, after which late work will typically not be accepted.  Homeworks are to be turned in at or before the start of class on the day in which it is due.  The professor will assess a representative sample of questions from each homework for a grade.  If a homework assignment is collected and not stapled the professor is likely to assess a small penalty.

To ensure appropriate understanding of topics that build as the semester progresses the student is expected, and is crucial for all students to complete all homework assignments in full.

It is the student’s responsibility to make sure that all homework assignments are completed in full prior to their due date, and will be ready to turn in.  Successful completion of homework assignments is key to a proper understanding of the materials covered in this course.

Programming Assignments:

The primary goals of this course are largely theoretical in nature (design/analysis of algorithms, understanding/applying algorithms from various algorithmic paradigms).   The Programming Assignments category is intended to help students develop a deeper level of understanding (both practical and theoretical) of these fundamentals.  Most assignments in this category will involve the implementation of classical algorithms that are representative of the algorithms and paradigms covered during the semester.

Quizzes:

Traditional exams this semester will not be given in favor of short, regular quizzes.  Quizzes will be delivered roughly once per week on Thursdays.  Quizzes are closed book and closed notes unless otherwise instructed.  Quizzes will be individual assignments unless otherwise instructed.  Use of electronic or communication devices (cell phones, PDAs, laptops, etc.) is strictly prohibited unless otherwise indicated by the professor.  Quizzes will typically be pen-and-paper and will consist of a small number of questions similar to those that would be on a homework assignment.

Tools and Development Environment:

Due to the nature of this course, homework assignments will be most/all based on pen-and-paper based assignments from textbooks or other sources.  Because of the theoretical/mathematical nature of this course (relying heavily on mathematical language, symbols, and graphics), students will be introduced to industry standard tools for mathematical/scientific writing, including (but possibly not limited to) the LaTeX typesetting toolchain.

Some instruction will be given in class about the use of these packages/languages, but due to the high (Junior-Senior) level of this course students are expected to gain proficiency in their use through regular practice outside of class, particularly when working on homework assignments.  Questions about the use of these tools should be directed to Piazza.

Note: All assignments are expected to be properly typeset (using the correct toolchain) and printed for grading prior to their respective due date or they will not be accepted.

Collaboration on Assignments:

Various facets of computer science theory tend to be quite abstract, and are often best learned through discussion.  Students are not only permitted, but encouraged to work on homework assignments in study groups.  Regardless of whether students choose to work alone or in groups it is expected that work is turned in on individual papers and all work should be the product of one’s own work and thought (your words).  If you choose to work in study groups on homework it is the individual student’s responsibility to ensure that they understand how all problems are solved.  Also, please note on homeworks which students you worked with.

Note that while equal participation in group studying can have great benefits to learning, over reliance on outside sources (other students, answers on the Internet, “study guides”) may result in completion of assignments but is likely to have a detrimental effect on learning outcomes.  As this is an upper division course, an adequate understanding of materials this semester is the responsibility of the individual student.  Failure to master course materials will likely result in failure on exams, and possibly the entire course.

Attendance:

Because of the way that new concepts build upon previous tools and skills attendance in a computer science or math class is particularly important to ensure mastery of material.  Attendance will be recorded at the beginning of most lecture periods, and will count as a portion of your final grade.  Students who arrive after attendance is taken up may not sign in for the day for credit for any reason unless otherwise instructed to do so.  Any attempt to modify the attendance sheet after the fact or to sign in for another student will be considered a breach of academic integrity.

When you are absent or tardy it is your responsibility to make sure that you learn the materials covered in class, and you are still responsible for any assignments that are announced that day, or are due that day.  It is the student’s responsibility to find out what was missed during class.  It is the instructor’s very strong recommendation that students acquire notes from at least one other students for any days missed.

Late work:

All assignments must be turned in before their respective deadline.  In the event of a documented, university approved absence (illness, class outings, military service, etc.) the professor may allow submission of late homework or exams.  Those having to miss class due to official school functions (such as athletic events or school trips) may make up missed items, provided that they check with the teacher ahead of time and schedule the make up work ahead of time.

Those who miss a class period or exam due to illness should contact me as soon as possible by email, and bring a doctor's excuse if they wish to make up their work.  Timing of made up work will be arranged outside of class with the professor.

Use of Electronic Devices:

In order to provide the best possible learning environment for all students you are asked to forgo the use of electronic devices (laptops, tablets, cell phones, recording devices, etc.) during class.  Special permission to use a specific electronic device may be granted on an individual basis, but it is the student’s responsibility get special permission from the instructor before use.

Piazza:

This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the SI Leader, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com.

Find our class page at: https://piazza.com/utm/fall2017/csci430/home.

Email:

Outside of class, I consider email to be another primary form of communication.  I will use your university provided email address for a number of possible course-related reasons including adjusting minor assignment parameters or providing clarifications.  You are expected to remain current with your university email.

Best practice concerning university email is to check at least once a day.

Academic Integrity:

Academic integrity is the hallmark of University studies, and is key to a successful professional career.  Students are permitted to work together on written homework in study groups, however all work turned in must be the student’s own work.  This includes all computer code, calculations, figures, proofs, or other work.  Copying the work of another student or any other source directly is not allowed, and is considered plagiarism.

Students are allowed to discuss programming related concepts at a high-level.  Discussions related to programming methods and solutions to assignments are also allowed in general terms.  However, you must design and write your own code.  

As a rule of thumb: if it can be discussed in plain English (including discipline-related technical jargon) it is probably OK.  If you are viewing another student’s work directly, or editing their work, or allowing someone else to do the same you are probably in violation.

Violations of Academic Integrity:

If one or more students are found to be in violation of the academic honesty policy the professor reserves the right to seek disciplinary action as allowable by university policy.  Such actions may include (but are not limited to) giving the student a zero on the assignment and reporting them to the office of student affairs.

In order to ensure your safety please direct all questions related to academic integrity to your professor before a (potential) infraction is committed.

In the event of a breach of academic integrity between one or more parties the instructor reserves the right to assign guilt to all involved parties.  In other words, sharing or allowing access to one’s work on individual assignments is also considered a breach of academic integrity and is punishable by the same terms.

Please protect yourself and your work: don’t share files, allow others to gain access to your work, publish your work online during the semester in any way that is publicly viewable, leave your workstation unlocked, or leave print-outs of work in accessible areas.

Academic Accommodation:

Any student eligible for and requesting an academic accommodation should provide to the instructor a letter of accommodation from the Student Success Center within the first two weeks of the semester, or as soon as can be accomplished.