Advanced Algorithms - CS 6/76101

Fall 2024

 

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-AdvAlgF24.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, 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

-

October, 2024

As 3 quizzes

32% 

Midterm Exam #2

-

November, 2024

As 3 quizzes

32%

Final Exam

Monday 

December 9, 2024

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. 25, 2024. [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. 2, 2024.

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

Fall Break: Oct. 3-6, 2024

Thanksgiving Recess: Nov. 27 - Dec. 1, 2022

  • 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: University Policy 3342-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).
  • STUDENT CHEATING AND PLAGIARISM: Condensed Version [For the complete policy and procedure, go to https://www.kent.edu/policyreg/administrative-policy-regarding-student-cheating-and-plagiarism

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:

1.       Obtaining or retaining partial or whole copies of examinations, tests or quizzes before these are distributed for student use;

2.       Using notes, textbooks or other information in examinations, tests and quizzes, except as expressly permitted;

3.       Obtaining confidential information about examinations, tests or quizzes other than that released by the instructor;

4.       Securing, giving or exchanging information during examinations;

5.       Presenting data or other material gathered by another person or group as one's own;

6.       Falsifying experimental data or information;

7.       Having another person take one's place for any academic performance without the specific knowledge and permission of the instructor;

8.       Cooperating with another to do one or more of the above;

9.       Using a substantial portion of a piece of work previously submitted for another course or program to meet the requirements of the present course or program without notifying the instructor to whom the work is presented; and

10.    Presenting falsified information in order to postpone or avoid examinations, tests, quizzes, or other academic work.

 

"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:

 

a.        The copying of words, sentences and paragraphs directly from the work of another without proper credit;

b.       The copying of illustrations, figures, photographs, drawings, models, or other visual and nonverbal materials, including recordings of another without proper credit; and

c.        The presentation of work prepared by another in final or draft form as one's own without citing the source, such as the use of purchased research papers.

 

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:

 

1.       Refuse to accept the work for credit; or

2.       Assign a grade of "F" or zero for the project, test, paper, examination or other work in which the cheating or plagiarism took place; or

3.       Assign a grade of "F" for the course in which the cheating or plagiarism took place; and/or;

4.       Recommend to the department chair or regional campus dean that further action specified in the rule be taken. The department chairperson or regional campus dean shall determine whether or not to forward to the academic dean or to the vice president for the extended university a recommendation for further sanction under this rule.

 

Procedures for invoking sanctions. (From Section E)

 

(1)           Academic administrative procedures pertaining to paragraph (D)(1)(a) of this rule. In the event that an instructor determines that it is more probable than not that a student in a course or program under the instructor's supervision has presented work for university credit which involves an act of cheating, plagiarism or cooperation in either, then the instructor shall:

 

(a)            Inform the student as soon as is practical, in person or by mail, of the belief that an act of cheating or plagiarism has occurred. If the student cannot be reached in a reasonable period of time, the instructor may proceed with sanctions, notifying the student in writing as promptly as possible of the belief and the procedural steps the instructor has taken.

(b)           Provide the student an opportunity to explain orally, in writing, or both, why the student believes the evaluation of the facts is erroneous.  

(c)            If the explanation is deemed by the instructor to be inadequate or if no explanation is offered, the instructor may impose one of the academic sanctions listed in paragraph (D)(1)(a) of this rule. Where appropriate, the instructor may recommend the imposition of academic sanctions listed in paragraph (D)(1)(b) of this rule. In addition, the instructor may refer the matter to the dean of the college, campus, or school in which the student is enrolled for imposition of academic sanctions listed in paragraph (D)(1)(b) of this rule.  

(d)           The instructor shall notify the office of judicial affairs of the circumstances and action taken. Such notification will be used as background information in the event that formal conduct charges are initiated against the student.  

(e)            The instructor shall inform the student in writing of the right to appeal, and the procedure to follow.  

(f)             The instructor shall keep the evidence of cheating or plagiarism in a secure place and provide it upon request to any appeals officer or the conduct officer. The instructor shall provide copies on request to the student at the student's expense.  

(g)           The instructor shall cooperate with academic and student conduct personnel in any appeal of the decision, and/or in adjudication of any disciplinary proceedings.

 

o    Diversity, Equity, and Inclusion Statement 

Endorsed by Faculty Senate, 2/14/2022 

Kent State University is committed to the creation and maintenance of equitable and inclusive learning spaces. This course is a learning environment where all will be treated with respect and dignity, and where all individuals will have an equitable opportunity to succeed. The diversity that each student brings to this course is viewed as a strength and a benefit. Dimensions of diversity and their intersections include but are not limited to: race, ethnicity, national origin, primary language, age, gender identity and expression, sexual orientation, religious affiliation, mental and physical abilities, socio-economic status, family/caregiver status, and veteran status. 

 

o    Land Acknowledgement Statement 

Endorsed by Faculty Senate 10/10/2022 

We acknowledge that the lands of Kent State University were the previous homes of people who were removed from this area without their consent by the colonial practices of the United States government. Before removal, these groups created networks that extended from Wyoming to the Florida Coast and Appalachia and to the northern reaches of Lake Superior. These societies included people of the Shawnee, Seneca-Cayuga, Delaware, Wyandots, Ottawa and Miami. We honor their lives - both past and present - and strive to move beyond remembrance toward reflection and responsibility through honest accounts of the past and the development of cultural knowledge and community. 

 

o    Religion Accommodations in compliance with H.B. 353 

Endorsed by Faculty Senate on 5/8/23 

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 2024