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:

Wednesdays 4:30 p.m. - 5:30 p.m. (Optional Class Time)
Thursdays 5:30 p.m. - 6:45 p.m. (Optional Class Time)
Zoom links available on D2L.

Class Delivery Methodology:

Hybrid online, flipped active learning model. What is a flipped active learning model? A "pedagogical approach in which direct instruction moves from the group learning space to the individual learning space, and the resulting group space is transformed into a dynamic, interactive learning environment where the educator guides students as they apply concepts and engage creatively in the subject matter." (The Flipped Learning Network, 2014). This means that students are expected to read and watch the course materials prior to attending the online sessions. Online sessions will be used for active and problem-based learning activities that allow students to engage in higher cognitive levels of learning with peers and their instructor present.

Instructor:

Rachel Trana

Office Hours:

Mondays, 4:00 p.m. - 6:00 p.m.
Wednesdays, 2:00 p.m. - 4: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:

Homework will be assigned frequently, posted online and is worth 25% of the final grade. While assignment deadlines are flexible, all assignments must be submitted to GitHub or D2L (pending assignment) by the specified final due date and time (usually before exams). 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:

There will be multiple opportunities for content assessments, worth a total of 15% of the final grade. These opportunities include: (1) In-class pair programming (1%), (2) One-on-one 20-minute assessments (0.5%), (3) Slack content question answering (0.5%).

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:

Getting Started, Algorithms and Efficiency

Week 2:

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

Week 3:

QuickSort, Large Integer Multiplication

Week 4:

Strassen's Algorithm, Dynamic Programming, Combinations, numWays

Week 5:

Review

Week 6:

Exam #1

Week 7:

Floyd's Algorithm, Chained Matrix Multiplication, Sequence Alignment

Week 8:

Sequence Alignment, Greedy Algorithms, Coin Change Problem, Knapsack Problem

Week 9:

Prim's Algorithm, Kruskal's Algorithm

Week 10:

Spring Recess

Week 11:

Exam #2

Week 12:

Dijsktra's Algorithm, Backtracking, n-Queens Problem, Greedy Coloring Algorithm

Week 13:

Backtracking Graph Coloring, Fast Two-Coloring Algorithm, Knapsack Problem, Backtracking

Week 14:

Branch and Bound, Knapsack Problem, Depth First Search, Breadth First Search

Week 15:

Review

Week 16:

Exam #3

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.