MATH 425: Algorithm Design and Analysis
Syllabus
| Title: | MATH 425 "Algorithm Design and Analysis" University of Wisconsin - Superior, Spring 2024 | ||||
| Mode of delivery: | on campus and asynchronous online via Zoom | ||||
| Meeting: | MTWF, 11 - 11:50am in SW1017 (on campus) | ||||
| Text: | Introduction to Algorithms (2nd edition) by T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein (ISBN: 0-07-013151-1) | ||||
| Prerequisites: | Successful completion of MATH 320 "Discrete Structures". | ||||
| Instructor: | Dr. Sergei Bezrukov | Office: Swenson 3022 | Schedule and Office hours | ||
 (715) 394-8523 | 
sbezruko@uwsuper.edu | ||||
Catalog Description
Study of the design and analysis of algorithms that are based on elementary data structures such as queues, stacks and trees. Some graph and network algorithms (shortest paths, connectivity, coloring, flows, matchings), geometric algorithms (convex hulls, range search, nearest neighbors), NP-complexity, approximation algorithms (vertex cover, traveling salesman, scheduling), and introduction to randomized algorithms. Introduction to algorithm design techniques, including greedy algorithms, divide-and-conquer, and dynamic programming. Lower and upper bounds of program complexity are analyzed. Introduction to algorithms used in the area of information security.
Learning Objectives
- Provide a knowledge on efficient algorithms from various areas.
- Develop student's skills in complexity analysis of algorithms.
- Build an understanding which problems are computationally hard and why.
Course Outcomes
Upon completion of this course the students will be able to do:- Use various techniques for developing efficient algorithms.
- Evaluate time complexity of algorithms.
- Apply their course experience to prove the correctness of algorithms.
Experiential Learning
In this course, experiential learning will occur in Units 2 - 7 with assignments devoted to various aspects of computer architecture design.
Evaluation and Grading
- Scores and grade
- The final grade for the course depends on the averaged score for home work assignments (this score is denoted by hw), scores for two midterm exams (denoted by ex1 and ex2), score for the final exam (ex3), and some amount of bonus points.
- The total score will be computed according to the formula:
total score = (25*hw + 25*ex1 + 25*ex2 + 25*ex3) / 100 + bonus
- The total score will be translated into the final grade according to
the following table:
A : 93 - A- : 90 - 92 B+ : 87 - 89 B : 83 - 86 B- : 80 - 82 C+ : 77 - 79 C : 73 - 76 C- : 70 - 72 D+ : 67 - 69 D : 63 - 66 D- : 60 - 62 F : 0 - 59
- Assignments (25%)
Take home exercises will be regularly assigned, collected, graded and returned. The students are allowed to discuss the problems in groups, however writings must be done strictly individually. Returning identical work is qualified as cheating (see below).- Usually in-class quizzez with 1-2 problems will be given within the first 15-20 minutes on the assignment due day. The quizzez are restricted to the topics of the current assignment. They must be done strictly individually and returned in class on the same day.
- Maximum score for each assignment+quizz is 100 points.
- If hw1, hw2, ... ,
hw8 are the scores for these assignments (each number
in the range 0 to 100), then the total score for the assignments is the
average of these scores, that is
hw = (hw1 + hw2 + ... + hw8) / 8rounded off to the nearest integer from above.
- Midterm exams (two of them, each worth
25%)
One exam will be given after 3-5 weeks of the beginning of the course, and another one will be given about 2-4 weeks before the end of the course. The maximum score for each midterm exam is 100 points.- The first exam covers the material from the first part of the course.
- The second exam emphasizes on the material covered after the first exam.
- The midterm exams, including possible take-home parts, must be done strictly individually, so no collective solutions or discussions are allowed.
- No late submission of the take-home part (if assigned) is accepted.
- Final exam (25%)
Date/time in Final Examination Schedule. The maximum score for the final exam is 100 points.- The final exam is comprehensive. So, any course content from the entire semester is fair game.
- The final exam must be done strictly individually, so no collective solutions or discussions are allowed.
- No late submission of the take-home part (if assigned) is accepted.
- Bonus points (0-6)
Bonus points will be issued during the last week of classes for:- participation in course related discussions in class (0-2 points)
- quality and completeness of homeworks (0-2 points)
- overall progress in class (0-2 points)
Class Policies
- No class work is accepted after the Final Exam.
- Problems in late homework assignments are accepted within two days after the assignment was due. In this case a student will be penalized on 10 points pro assignment. However, if a solution to a problem is discussed in class or posted online, no late solution to this problem will be accepted after this. A submission is qualified as late if it is returned after the specified date and time.
- Representing someone else's work as your own without referencing or
permitting another student to do so with your work is cheating.
Cheating might result in administrative actions described in UWS14.03 UW-System Administrative Code Student Academic Disciplinary Procedures. - A make up of an exam is allowed if an unavoidable absence occurs. A reason for absence must be documented.
- Students are required to check with the instructor if they find some of these rules unclear, before taking an action.
Attendance and absences
- On-campus tudents are expected to attend all class periodsa
except in the case of illness such as COVID-19 or other illness that causes
poor physical health and precludes you from attending in-person or online.
Care-giving such as caring for a child or a family member with COVID-19 is
also an acceptable reason for your absence.
Online students are expected to watch every class recording - If you are absent from a class period for either an on-campus course or a synchronous online course it is your responsibility to contact and communicate with your instructor for any missed periods or resulting delays on classwork. Contact your instructor before you are absent if possible. You will not need a formal doctor's note to excuse an absence caused by illness or caregiving for COVID-19 in this course.
- If you are absent from classes for reasons related to illness or caregiving and have notified your instructor, you will not be penalized through grades, missing points, or be deprived of the chance to make-up assignments. But you must still work with your instructor to make up any missed work - either in-class or out-of-class - within the timeframe designated by the instructor.
- Students who are not ill, but are in quarantine and/or isolation during testing wait periods due to COVID-19 exposure should attend class online or complete substitute activities at the direction of the instructor.
Generative AI Use Policy
Generative artificial intelligence (AI), including ChatGPT or similar tools used for creating text, images, computer code, audio, or other media, are not permitted for use in any work in this class. Using these tools in any way for this course is a violation of course expectations and will be addressed through UW-Superior's academic misconduct policy. If you are in doubt as to whether you are using a tool appropriately in this course, I encourage you to discuss your situation with me.
Suggestions for Success in Class
- Do not miss classes. The class discussions emphasize on many particular aspects, a good number of them is not in the textbook or spread out over several chapters in the book so that it might be difficult to find them. These details may be very helpful for your work on the assignments.
- Ask right away in class or after the class if something is not clear.
- Read in the books the topics that are covered in class on the same day after the class. Just working on the material during the class hours is far from being enough. It is expected that a student would spend at least 2 hours in average working through the material after each class.
- Prepare yourself for the next class. That is, read in advance the material to be explained in class. Refer to the Course Outline to figure out what will be covered (it will also be announced at the end of each class). It would be much easier for you then to follow the discussion in class. In addition you would know what to pay a particular attention on and what questions to ask.
- Come to the instructor's office hours (or make a special appointment) and do not let the unclear stuff to accumulate.
- Try to find time to solve as many problems as possible (even more than it is assigned). Solving the problems is the only way to learn how to solve them.
UNIVERSITY INFORMATION
Diversity and Inclusion at UW-Superior
Diversity and inclusion is integral to the educational mission of the University of Wisconsin-Superior. As a community we commit to recognize, include and value inherent worth and dignity of each person; foster tolerance, sensitivity, understanding, mutual respect, and justice among its members; and encourages each individual to strive to reach their own potential. The institution recognizes these experiences are crucial for developing the requisite skills to thrive as a member of a pluralistic society and as a responsible global citizen.
In pursuit of its goal of inclusive excellence, the University actively seeks to attract students, faculty, and staff from diverse backgrounds and life experiences, including but are not limited to: race, ethnicity, sex, gender identity, gender expression, sexual orientation, age, socio-economic background, cognitive ability, physical ability, religion and spirituality, value system, national origin, immigration or refugee status, veteran status, and political beliefs.
The University believes that diversity among its members strengthens the institution, stimulates creativity, promotes the exchange of ideas, and enriches campus life. The University of Wisconsin-Superior views, evaluates, and treats all person in any University related activity or circumstance in which they may be involved, solely as individuals.
For more information about Equity, Diversity, and Inclusion and/or to report bias, discrimination or harassment, please email edi@uwsuper.edu or call 715-394-8015.
Policies and Practices to Help Your Learning and Growth
The University of Wisconsin-Superior is dedicated to a safe, supportive and nondiscriminatory learning environment. It is the responsibility of all undergraduate and graduate students to familiarize themselves with University policies regarding special accommodations, academic misconduct, religious beliefs accommodation, discrimination and absence for University- sponsored events.
Please review the Student Information Module provided in Canvas. This includes policies and information related to:
- Student characteristics, including policies and services related to those who are active military/veterans, those who are pregnant or expecting new family members, and students seeking services for differing abilities and accommodations student services, and others.
- Academic integrity, including information on plagiarism and steps that an instructor can take.
- Campus policies, including how to sign up for Safe Alerts, information on course evaluations, process for submitting a formal grievance regarding academics and/or discrimination, and others.
Please refer to the University Catalog or the UW-Superior Web page for full description of these and other policies.