Design & Analysis of
Algorithms - CS 4/56101
Spring 2024
MW 9:15 am - 10:30 pm
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&AofAlgS24.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 ??, 2024
|
9:15 - 10:30 a.m.
|
33%
|
|
Final Exam
|
Thursday
|
May 9, 2024
|
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 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 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 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. 22, 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
Jan. 29, 2024.
The last day to withdraw from course with grade of "W"
assigned is Apr. 1, 2024.
- Spring
Recess (No Classes): Mon-Sun, Mar. 25 - Mar.
31, 2024.
- 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 2024