Design & Analysis of
Algorithms - CS 4/56101
Spring 2025
MW 9:15 am - 10:30 am
MSB 228
|
Instructor
Office Hours
Email
Telephone
|
Dr. Feodor Dragan
Room 254 MSB
MW 10:30 AM - 12:30 PM
or by appointment
dragan at cs dot
kent dot edu
(330) 672-9058
|
Grading Assistant
Office Hours
Email
|
Li, Xinyu
Room 136 MSB
MW 10:30 am to 12:30 pm
or by appointment
xli74@kent.edu
|
- WWW: http://www.cs.kent.edu/~dragan/CS4-56101-D&AofAlgS25.html
- Prerequisites: Data
Structures - CS 23001
- Course Description: 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 23001. 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.
- Learning objectives: 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.
- Goals: This course
has several goals.
- Study important data structures and algorithmic
techniques not normally covered in CS 23001.
- Develop ability to design efficient algorithms.
- Develop ability to prove correctness and
evaluate efficiency of algorithms.
The main
goal of the course is to learn to think algorithmically like a ``real''
computer scientist.
Algorithm
Design: Foundations, Analysis, and Internet Examples, Wiley, 2002, ISBN 0-471-38365-1
(by Michael T. Goodrich and Roberto Tamassia)
- 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).
- Algorithm Analysis
- Data Structures (Elementary Data Structures, Vectors, Stacks,
Queues, Sequences, Trees, Heaps, Priority Queues, Hash Tables,
Dictionaries)
- Searching (Binary Search Trees, AVL Trees, Red-Black
Trees, Skip Lists, Locators)
- Sorting (Merge Sort, Quick Sort, Sorting Lower Bound,
Sets, Radix Sort, Selection)
- Fundamental
Techniques (Greedy Method,
Divide-and-Conquer, Dynamic Programming)
- Graphs Algorithms (Graphs, Depth-First Search, Breadth-First
Search, Biconnectivity, Directed Graphs)
- Weighted Graphs (Shortest Paths, Minimum Spanning Tree)
- Text Processing (Pattern Matching)
- NP-Completeness
- Course Requirements
|
Homework
|
-
|
-
|
-
|
30%
|
|
Attendance
|
-
|
-
|
-
|
4%
|
|
Midterm Exam
|
???????
|
March ??, 2025
|
9:15 - 10:30 a.m.
|
33%
|
|
Final Exam
|
Friday
|
May 9, 2025
|
10:15 - 12:30 p.m.
|
33%
|
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.
- Milestone for successful completion of the course
- Attend the classes regularly,
- Perform the homework thoroughly and
independently,
- Read the book 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. Homework must be turned in before or after the class on a due
date (otherwise, there will be some penalty points). 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 on 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 writeup
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 Jan. 19,
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
Jan. 26, 2025.
The last day to withdraw from course with grade of "W"
assigned is March 30, 2025.
- Spring
Recess (No Classes): Mon-Sun, Mar 10-16, 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
F. F. Dragan
dragan at cs dot kent
dot edu
Spring 2025