| Course: | CS:4/56101 Design and Analysis of Algorithms - Section 001 | Instructor: | Heather M. Guarnera |
|---|---|---|---|
| Class Time: | TR 3:45 - 5:00 pm @ SMH 108 | Office Hours: | TR 1:30 - 3:30 pm @ MSB 352, and by appointment |
| Semester: | Fall 2019 | Contact: | hmichaud@kent.edu (330)-672-9106 |
This syllabus, and deadlines, are subject to change.
This course is an introductory undergraduate/graduate course on the design and analysis of algorithms. The course builds on the study of the analysis and implementation of data structures and algorithms from CS 33001. The goal is to introduce a number of important algorithm design techniques as well as basic algorithms that are interesting both from a theoretical and also practical point of view. We will cover basic algorithm design techniques such as divide-and-conquer, dynamic programming, and greedy techniques for optimization. We will cover techniques for proof of the correctness of algorithms and also asymptotic analysis of algorithm time bounds by the solution of recurrence equations. We will apply these design and analysis techniques to derive algorithms for a variety of tasks such as sorting, searching, and graph problems. Some specific algorithm topics include: deterministic and randomized sorting and searching algorithms, depth and breadth first search graph algorithms for finding paths and matchings, and algebraic algorithms for fast multiplication and linear system solving.
Students will learn (i) advanced data structures and their analysis; (ii) to think algorithmically like a "real" computer scientist; (iii) different techniques and methods for designing efficient algorithms for solving computational problems. Students will develop (i) the ability to design efficient algorithms; (ii) the ability to prove correctness and evaluate efficiency of algorithms.
Students in the course who do not have the proper prerequisites risk being deregistered from the class. Prerequisites include:
Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley, 2002, ISBN 0-471-38365-1 (by Michael T. Goodrich and Roberto Tamassia) Book's web site
We will cover the following topics (the topics and order listed are tentative and subject to change; some topics may only be quickly surveyed to add breadth, while others will be covered in reasonable depth).
| Homework | 35% |
| Midterm Exam (tentatively, Oct. ??) | 30% |
| Final Exam (Friday, Dec. 13 @ 7:45 - 10:00am) | 30% |
| Participation | 5% |
Homework is very important. It is expected that most of your learning will come from the process of solving the homework problems. Exams will in large part be based on the homework.
Participation points are accumulated via attendance, questions asked and answered on piazza, and correct completion of in-class assignments. You will be given the opportunity to obtain extra participation points at times noted during class. All extra participation points are applied at the end of the semester. At most 2 can be applied to attendance and any remaining extra participation points are applied to your midterm or final exam.
Final Grading Scale is as follows.
| Scale: | 0% | 60% | 67% | 70% | 73% | 77% | 80% | 83% | 87% | 90% | 93% |
| Grade: | F | D | D+ | C- | C | C+ | B- | B | B+ | A- | A |
| GPA: | 0.00 | 1.00 | 1.30 | 1.70 | 2.00 | 2.30 | 2.70 | 3.00 | 3.30 | 3.70 | 4.00 |
Attendance is a course requirement. Missed exams and missed homework are only excused if absence was essential and can be fully documented. Homework must be turned in by the end of class on due date, either typed and printed or hand-written. Unexcused late homework is not accepted. Class extensions on homework will be announced in class. They may also be announced by email and at the course website.
You will need to devote a considerable amount of time to homework. You may discuss the homework with other students, but you must write your solutions independently. Study groups should limit their size to 2-3 so that each collaborator can participate in solution. If you obtain a solution to a homework problem through research (e.g., from books or journals), you are expected to acknowledge your sources in your writeup and also to write up your solution independently.
The official registration deadline for this course is August 28. University policy requires all students to be officially registered in each class they are attending. Students who are not officially registered for a course by published deadlines should not be attending classes and will not receive credit or a grade for the course. Each student must confirm enrollment by checking his/her class schedule (using Student Tools in FlashLine) prior to the deadline indicated. Registration errors must be corrected prior to the deadline.
The last day to withdraw before a grade of "W" is assigned is September 4. No approval is necessary before this date. The last day to withdraw with a grade of "W" assigned is October 30.
The Student Survey of Instruction (aka, SSI, teaching evaluations, Flash Surveys, etc.) will take place electronically. It will be available between 12:01 AM November 24 and 11:59PM December 8.
University Policy 3-01.3 requires that students with disabilities be provided reasonable accommodations to ensure their equal access to course content. If you have a documented disability and require accommodations, please contact the instructor at the beginning of the semester to make arrangements for necessary classroom adjustments. Please note, you must first verify your eligibility for these through Student Accessibility Services (contact 330-672-3391 or visit www.kent.edu/sas for more information on registration procedures).
In the event that you choose to write or speak about having survived sexualized violence, including rape, sexual assault, dating violence, domestic violence, or stalking Kent State requires that, as your instructor, I share this information with Title IX. Someone from Title IX will contact you to let you know about accommodations and support services as well as options for holding accountable the person who harmed you. You are not required to speak with them.
If you do not want Title IX notified, instead of disclosing this information to your instructor, you can speak confidentially with the following people on campus and in the community.
They can connect you with support services and help explore your options now, or in the future.
University policy 3-01.8 deals with the problem of academic dishonesty, cheating, and plagiarism. None of these will be tolerated in this class. The sanctions provided in this policy will be used to deal with any violations. If you have any questions, please read the policy at https://www.kent.edu/policyreg/administrative-policy-regarding-student-cheating-and-plagiarism and/or ask.
Cheating and plagiarism constitute fraudulent misrepresentation for which no credit can be given and for which appropriate sanctions are warranted and will be applied. The university affirms that acts of cheating and plagiarism by students constitute a subversion of the goals of the institution, have no place in the university and are serious offenses to academic goals and objectives, as well as to the rights of fellow students.
"Cheat" means to intentionally misrepresent the source, nature, or other conditions of academic work so as to accrue undeserved credit, or to cooperate with someone else in such misrepresentation. Cheating includes, but is not limited to:
`Plagiarize` means to take and present as one`s own a material portion of the ideas or words of another or to present as one`s own an idea or work derived from an existing source without full and proper credit to the source of the ideas, words, or works. As defined, plagiarize includes, but is not limited to:
Academic Sanctions (from Section D). The following academic sanctions are provided by this rule for offenses of cheating or plagiarism. Kent campus instructors shall notify the department chairperson and the student conduct office each time a sanction is imposed. Regional campus instructors shall notify the regional campus dean and the student conduct officer each time a sanction is imposed. Regional campus student conduct officer shall notify the Kent student conduct office each time a sanction is imposed by a regional campus Instructor. The following academic sanctions are provided by this rule for offenses of cheating or plagiarism. In those cases the instructor may: