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 2026
MW 05:30 pm - 06:45 pm
|
Instructor |
Dr. Feodor Dragan |
|
Office Hours |
Room 254 MSB MW 3:00 - 5:30 pm or by
appointment |
|
Email |
|
|
Telephone |
(330) 672-9058 |
- WWW http://www.cs.kent.edu/~dragan/CS6-76101-AdvAlgF26.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 (3rd 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,
- J. O'Rourke, Computational Geometry in
C,
- 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, 2026 |
As 3 quizzes |
32% |
|
Midterm Exam #2 |
- |
November, 2026 |
As 3 quizzes |
32% |
|
Final Exam |
Monday |
December 14, 2026 |
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. 30,
2026. [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
Sept. 6, 2026.
The last day to withdraw from
course with grade of "W" assigned is Nov. 1, 2026.
Labor Day: Mon, Sep 07, 2026 (no classes)
Fall Break: Thu, Oct 08, 2026 - Sun, Oct 11, 2026
Veterans Day: Wed, Nov 11, 2026 (no classes)
Thanksgiving Recess: Wed, Nov 25, 2026 - Sun, Nov 29, 2026
- 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 2026