Credit Hours:

3.0

Course Description:

Methods for analyzing algorithms are discussed including an introduction to asymptotic notation. Several approaches to designing algorithms are covered using theory, examples and problems. Those approaches include divide-and-conquer, dynamic programming, the greedy approach backtracking and branch-and-bound. Different approaches are applied to the same problem to illuminate the relative advantages.

Prerequisites:

CS-201 (minimum grade of C) and CS-304 (minimum grade of C).

Class Time:

N/A (online)

Instructor:

Rachel Trana

Office Hours:

Mondays, 6:00 p.m. - 8:00 p.m.
Wednesdays, 2:00 p.m. - 5:00 p.m.
Thursdays, 1:00 p.m. - 3:00 p.m.
Zoom office hours links available on D2L

Email:

r-trana@neiu.edu
All course-related questions should be posted on the Slack workspace.

Required Text:

Foundations of Algorithms, 5th Edition. Richard Neapolitan. Jones & Bartlett Learning 2015, ISBN 978-1-284-04919-0

Suggested Texts:

Algorithms, 4th Edition. Robert Sedgewick and Kevin Wayne. Pearson 2011, ISBN 978-0-321-57351-3
Java SE 11 Documentation

Websites:

Grades, Homework Submissions: D2L
Discussion Forum: Slack (link available on D2L)
Course Lectures, Homework Assignments: https://racheltrana.com/

• Describe the logics and concepts of algorithms.
• Deciding the correctness and efficiency of algorithms.
• Describe different types of algorithms like divide-and-conquer, dynamic programming, greedy, backtracking, and branch-and-bound.
• Analyze, critique, and discuss different types of algorithms.
• Write short programs to implement various algorithms.

• Introduction to time complexity analysis
• Divide-and-conquer: binary search, merge sort, and quick sort
• Dynamic programming: Floyd’s algorithm, and chained matrix multiplication
• The greedy approach: minimum spanning trees, Prim’s algorithm, Kruskal’s algorithm, and Dijkstra’s algorithm
• Backtracking: the n-Queens problem, graph coloring
• Branch-and-bound: the 0-1 Knapsack problem

Assignments:

Assignments: Homework will be assigned frequently, posted online and is worth 25% of the final grade. All assignments must be submitted to GitHub or D2L (pending assignment) by the specified due date and time. Homework assignments are graded as Pass/Fail (i.e. 0 vs 1 pts). To get Pass credit, the assignment must pass all GitHub tests and coding checks. Plagiarism is strictly not tolerated.

Quizzes:

There will be multiple online (D2L) open-book quizzes throughout the quarter, designed to reinforce core concepts worth a total of 15% of the final grade. These quizzes must be completed prior to the specified class meeting time.

Content Assessments:

Content assessment credit, worth a total of 15% of the final grade, can be earned via code reviews. You will be provided with another student’s homework problem (anonymously) and must assess that student’s solution to the code. Each assessment is worth 1% and you can do two code reviews per week.

Exams:

There will be three scheduled (online) exams, each worth 15% of your final grade.

Important Dates:

Monday, January 18, 2021: Martin Luther King, Jr. Birthday - No Classes, Office Hours
Friday, February 12, 2021: Lincoln's Birthday - No Classes
Monday, March 15, 2021 - Sunday, March 22, 2021: Spring Recess - No Classes
Friday, April 2, 2021: Last day to drop with a W

Week 1 (01/11/21):

Getting Started, Algorithms and Efficiency

Week 2 (01/18/21):

Divide and Conquer, recursion, combinations, numWays, Recursive Binary Search, MergeSort

Week 3 (01/25/21):

QuickSort, Large Integer Multiplication

Week 4 (02/01/21):

Catch-up!

Week 5 (02/08/21):

Review

Week 6 (02/15/21):

Exam #1

Week 7 (02/22/21):

Breathe, wait for exam results and decide about final project vs final exam.

Week 8 (03/01/21):

Dynamic Programming Part I: Dynamic Programmign Practice, Floyd’s Algorithm

Week 9 (03/08/21):

Dynamic Programming Part II: Chained Matrix Multiplication, Sequence Alignment

Week 10 (03/15/21):

Spring Recess

Week 11 (03/22/21):

Greedy Algorithms Part I: Coin Change Problem, Scheduling, Knapsack Problem

Week 12 (03/29/21):

Greedy Algorithms Part II: Prim's Algorithm, Kruskal's Algorithm, Dijkstra's Algorithm

Week 13 (04/05/21):

Backtracking Part I: N-Queens

Week 14 (04/12/21):

Backtracking Part II: Graph Coloring

Week 15 (04/19/21):

Complete Homework

Week 16 (04/26/21):

Final Project/Final Exam

Academic Integrity Policy:

By enrolling in this course, you are bound by the NEIU Student Code of Conduct. You will be informed by your instructor of any additional policy specific to your course regarding plagiarism, class disruptions, etc.

Cheating:

Cheating is a serious academic offense and violates the NEIU Student Code of Conduct (see University Policies below). All students will be required to turn off their electronic devices (phone, smart watches, etc) at the beginning of each exam. Failure to do so and/or any involvement in or suspicion of cheating will result in a failing grade for the final exam (and the course). Additionally, students involved in cheating will be reported for academic misconduct to the Dean of Students (two reports can result in expulsion from the university).

ADA Statement:

Northeastern Illinois University (NEIU) complies with the Americans with Disabilities Act (ADA) in making reasonable accommodations for qualified students with disabilities. To request accom- modations, students with special needs should make arrangements with the Student Disability Services (SDS) office, located on the main campus in room D104. Contact SDS via (773) 442-4595 or SDS online. It is your responsibility to have the Accessibility Center send me this information by the 3rd week of the semester.

Campus Safety:

Web links to Campus Safety: Emergency Procedures and Safety Information can be found on NEIUport on the MyNEIU tab or via the University Police Page on NEIU's website.

General Policies:

Because quizzes are online and open-book/note, no make-up quizzes will be given. However, one quiz will be dropped.

Cheating and/or plagiarism will not be tolerated. Students that violate the NEIU academic conduct policy may be subject to an F for that assignment, quiz, exam, project or any portion (or all) of the final course grade

Syllabus topics/content for this course may be changed/updated as deemed appropriate or necessary by the instructor.

Policies may be modified or added as deemed appropriate or necessary by the instructor.