Dr. Feodor F. Dragan

Professor of Computer Science

Feodor F. Dragan received the M.S. degree in Applied Mathematics and Computer Science from Moldova State University, in 1985, and the PhD degree in Theoretical Computer Science from the Belorussian Academy of Sciences, in 1990. He was an Assistant and then an Associate Professor at the Mathematics and Computer Science Department of Moldova State University from 1988 to 1999. From 1994 to 1999, he was on leave of absence and worked in Germany as a Research Associate on a Volkswagen Foundation (VW) project and on a German Research Community (DFG) project. He was also awarded a DAAD Research Fellowship (Germany) from 1994 to 1995. During 1999 to 2000, he was a Research Associate at the Computer Science Department of University of California, Los Angeles. Since August 2000 he has been with Kent State University and he is currently a Professor of Computer Science. He held visiting positions in Germany (Technische Universitaet Berlin), in France (Universite de la Mediterranee, Marseille and Universite Paris Diderot - Paris 7), in Norway (Universitetet i Bergen), and in Chile (Universidad de Chile, Santiago). He has authored more than 150 refereed scientific publications. His research interests include design and analysis of network algorithms, algorithmic graph and hypergraph theory, computational geometry, computational biology, VLSI CAD, combinatorial optimization, discrete convexity and geometry of discrete metric spaces, distance location problems and operations research, data analysis.

Advanced Algorithms - CS 6/76101

Fall 2025

MW 05:30 pm - 06:45 pm

Instructor	Dr. Feodor Dragan
Office Hours	Room 254 MSB MW 3:30 - 5:30 pm or by appointment
Email	dragan at cs.kent.edu
Telephone	(330) 672-9058

• WWW http://www.cs.kent.edu/~dragan/CS6-76101-AdvAlgF25.html
• Prerequisites
  A firm prerequisite is a senior level algorithms course at approximately the same level as CS 4/56101 (Intro. to Design & Analysis of Algorithms). A combined Data Structures and Algorithms course like CS 23001 is not an adequate preparation for this course. This course assumes both CS 23001 and CS 4/56101 as background.
• Goals:  This course has several goals.
• Study important algorithm areas and techniques not normally covered in the first course.
• Develop ability to design efficient algorithms.
• Develop ability to prove correctness and evaluate efficiency of algorithms.
• To cover a number of additional topics not covered in CS 4/56101 (first algorithms course).
• Learning objectives: Students will learn (i) different advanced techniques and methods for designing efficient algorithms for solving computational problems; (ii) advanced techniques for analyzing computational complexities of algorithms and of algorithmic problems themselves; (iii) advanced techniques for proving correctness of algorithms; and (iv) new modern trends and challenges in design and analysis of algorithms.
• Text (CLRS)
  Thomas Cormen,  Charles Leiserson,  Ronald Rivest, and  Cliff Stein,  Introduction to Algorithms, McGraw  Hill Publishing Company and MIT Press, 2009 (3^rd edition).
  (The MIT Press web site for the textbook is http://mitpress.mit.edu/algorithms).
• Additional Book & Web References
•  Ellis Horowitz, Sartaj Sahni, and Sangurthevar Rajasekaran, Computer Algorithms, Computer Science Press, 1998. (HSR)
•  Gilles Brassard and Paul Bratley, Fundamental of Algorithmics, Prentice Hall, 1996. (BB)  
•  Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
•  J. O'Rourke, Computational Geometry in C, Cambridge  University Press, 1998 (Second Edition).
•  Michel Goemans, Advanced Algorithms Course Notes are available from this website.
• Some assumed topics from first algorithms course
• Reasonable knowledge of basic topics in CLRS textbook.
• Some maturity in designing, evaluating running time, and proving correctness of algorithms.
• Asymptotic notation and complexity.
• Recurrences and summations.
• Major Sorts (including quicksort and heapsort), linear time sorts, lower bound for sorting.
• Hash tables.
• Binary search trees, red-black trees.
• Graph algorithms including traversals, minimum spanning trees, and shortest path.
• Basic numeric routines, including matrix operations.
• Topics will include: 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).
• Dynamic Programming
• Optimal greedy algorithms
• Amortized analysis
• Parallel algorithms
• Computational geometry algorithms
• NP-hard and NP-complete problems
• Approximation algorithms
• Network flow algorithms
• Randomized algorithms
• String matching algorithms
• Online algorithms
• Course Requirements

Homeworks	-	-	-	-
Participation	-	-	-	4%
Midterm Exam #1	-	September, 2025	As 3 quizzes	32%
Midterm Exam #2	-	November, 2025	As 3 quizzes	32%
Final Exam	Monday	December 8, 2025	5:45 - 8:00 p.m.	32%

• Milestone for successful completion of the course
• Attend the classes regularly,
• Perform the homework thoroughly and independently,
• Read the book and slides carefully and several times.
• Make-up and Late policy:  Attendance at times exams are given is a course requirement. Missed tests are only excused if absence was essential and can be fully documented. Unexcused late homework is normally not accepted after 11:59:99 pm of due date. Class extensions on homework will be announced in class. They may also be announced by email and at the course website.
• Homework and Collaboration: 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 write-up and also to write up your solution independently.

• Registration Requirement:

The last day to add a full term class or change sections of a class is Aug. 24, 2025. [University policy requires all students to be officially registered in each class they are attending. Students who are not officially registered for a course 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 FlashFast) prior to the deadline indicated. Registration errors must be corrected prior to the deadline.]

The last day to withdraw from course before grade of "W" is assigned is Aug. 31, 2025.

The last day to withdraw from course with grade of "W" assigned is Oct. 26, 2025.

Fall Break: Thu, Oct 2, 2025 - Sun, Oct 5, 2025

Thanksgiving Recess: Wed, Nov 26, 2025 - Sun, Nov 30, 2025

• SSI is now online: The Student Survey of Instruction (SSI) is now online. You will be given time to complete that survey on-line during the last class meeting.

• Student Accessibility Policy: Kent State University is committed to inclusive and accessible educational experiences for all students. University Policy 3342-3-01.3 requires that students with disabilities be provided reasonable accommodations to ensure equal access to course content. Students with disabilities are encouraged to connect with Student Accessibility Services as early as possible to establish accommodations. If you anticipate or experience academic barriers based on a disability (including mental health, chronic medical conditions, or injuries), please let me know immediately.

Student Accessibility Services (SAS) Contact Information:

Location: University Library, Suite 100

Email: sas@kent.edu

Phone: 330-672-3391; VP 330-968-0490

Web: www.kent.edu/sas

Student Cheating and Plagiarism

University policy states that "students enrolled in the university, at all its campuses, are to perform their academic work according to standards set by faculty members, departments, schools and colleges of the university; and cheating and plagiarism constitute fraudulent misrepresentation for which no credit can be given and for which appropriate sanctions are warranted and will be applied. "Cheat" means intentionally to 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. Such misrepresentations may, but need not necessarily, involve the work of others. "Plagiarize" means to take and present as one's own a material portion of the ideas or words of another (e.g. person, persons, or Generative Artificial Intelligence), 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."

See the complete university policy regarding cheating and plagiarism, which in addition to the above contains detailed definitions and information about sanctions.

Title IX

Kent State is committed to fostering a safe, productive learning environment. As an instructor, one of my responsibilities is to help create a safe learning environment in our class. Kent State (and federal law Title IX) policy prohibit discrimination based on sex, which includes sexual misconduct - (sexual harassment, domestic and dating violence, sexual assault, and stalking). We understand that sexual violence can undermine students academic success and we encourage students who have experienced some form of sexual misconduct to talk to someone about their experience, so they can get the support they need.

It is my goal that you feel able to share information related to your life experiences in classroom discussions, in your written work, and in our one-on-one meetings. I will seek to keep the information you share private to the greatest extent possible. However, I also have a responsibility to notify the Title IX Coordinator when I become aware of incidents of sexual misconduct. Students may speak privately (without disclosing name) to the Center for Sexual and Relationship Violence Support Services (SRVSS) 330-672-8016. Learn more about SRVSS. Students may speak confidentially to Psychological Services 330-672-2487. Another resource available to help navigate issues and concerns is the Student Ombuds. (330-672-9494). Read a message from the Student Ombuds .

Request for Religious Accommodations

The University welcomes individuals from all different faiths, philosophies, religious traditions, and other systems of belief, and supports their respective practices. In compliance with university policy and the Ohio Revised Code, the University permits students to request class absences for up to three (3) days, per term, in order to participate in organized activities conducted under the auspices of a religious denomination, church, or other religious or spiritual organization. Students will not be penalized as a result of any of these excused absences.

The request for excusal must be made in writing during the first fourteen (14) days of the semester and include the date(s) of each proposed absence or request for alternative religious accommodation. The request must clearly state that the proposed absence is to participate in religious activities. The request must also provide the particular accommodation(s) you desire.

You will be notified by me if your request is approved, or, if it is approved with modification. I will work with you in an effort to arrange a mutually agreeable alternative arrangement. For more information regarding this Policy you may contact the Student Ombuds (ombuds@kent.edu).

---

F. Dragan
dragan at cs.kent.edu
Fall 2025