"People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.'' Donald E. Knuth 
This course introduces students to the analysis and design of computer algorithms. Upon completion of this course, students will be able to do the following:

Class Attendance/Participation  10% 
Problem Sets  30% 
LeetCode Assignments  20% 
Exams  20% 
Final Project/Presentation  20% 
While students are encouraged to use office hours instead of email, the instructor will respond to short questions when appropriate. In order to ensure that they will be correctly handled by the instructor’s filter, the subject of all emails must start with “MATH 391:”; any email without this header runs the risk of being filtered.
Lecture slides will be available on this site by the day of the presentation. They are intended to help you reconstruct the work from class, but are not intended as a substitute for taking notes.
It is expected that you have read the assigned reading BEFORE class. We will be discussing the topic, and each student is expected to contribute to the conversations. Your participation grade will be partially dependent on your involvement in the discussions.
Due date: Unless otherwise stated, Problem Sets are due by 5:00pm the day before they will be presented in class. There will be a 12 hour grace period during which the student will received a penalty equal to 5% of the value of the assignment; any assignments submitted more than 12 hours late will not be accepted. Exception: Each student may have a 24 hour extension on one assignment without penalty. This extension will be applied to the first assignment submitted outside the grace period (or retroactively used to cancel one graceperiod penalty if not used by the end of the semester.)
Submission Methods: Assignments must be typed and submitted through the Moodle website. The instructor will not accept submissions through email, Moodle submissions in any format other than pdf, or hard copies submitted directly to him.
Missing Assignments: Problem sets are an important part of this class; the effort spent on them is a crucial part of the learning process. Failure to submit assignments is unacceptable: students earning 0s on two assignments cannot receive a grade higher than a B for the course; students earning three 0s will receive an automatic F for the course.
Problem Set Work Teams: Two person teams may be randomly assigned for some problem sets. The teams should work together, discussing the solutions. However, each team member is responsible to write up their own solution and turn is in. Thus while teams may share the same solution, they also may might be the same. Each assignment will include an estimation of the percentage of work done but each member (from the perspective of each person). For example: "Work distribution: Carmen: 55%, myself: 45%". The instructor will monitor this for patterns across multiple partners.
Problem Set Presentations: Each team must prepare to make a presentation of each problem. The instructor will review these before class, and determine which team will present which problems. The students class participation grade will depend in part of the level of preparation for the solution presentation.
Presentations: Students should be prepared to present and discuss their solutions formally in class the day specifies in the schedule.
Due Date: As with problem sets, the assignments are due by 5:00pm the day before they will be presented in class, with wth same rules for lateness.
Submission Methods: Assignments ust be submitted online with source code, runs showing a variety of test cases that demonstrate all major aspects of the problem space, a writeup of the computational and space complexity as requested in the assignments.
Collaboration: Students should conform to the "group work" policy below.
Presentations: Students should be prepared to present and discuss their solution formally in class the day specifies in the schedule. Be prepared to justify the solutions correctness as well as it computational analysis.
In order to facilitate learning, students are encouraged to discuss homework and LeetCode problems amongst themselves. Copying a solution is not, however, the same as “discussing.'' A good rule of thumb is the “cup of coffee'' rule. After discussing a problem, you should not take away any written record or notes of the discussion. Go have a cup of coffee or cocoa, and read the front page of the newspaper. If you can still recreate the problem solution afterward from memory, then you have learned something, and are not simply copying. (The “group problems” are exempt from this, as they are intended to be done together.)
20% of your grade will consist of a semester long research project, collimating in a 30 minute presentation at the end of the class. This project can be one of the following two types:
Two person teams can be considered for this project, but you must justify this option with clear evidence that it is significantly more work then a single person project. For example, you could explore and compare two distinct approaches, or do a combination of 1 & 2 above, or explore something that has significant complexity in and of itself.
Possible Sources: link
All work turned in is expected to be your own. It is likely that proof, algorithm and code solutions for most problems exist online. Generally you should not search for any of these solutions. If you do use online or written documents, you must fully disclose and reference everything used, and be prepared to lose some credit if the help is deemed to be beyond that which you should used. The rule of thump is you can use references to help understand the problems and terminology, but should not use (and copy or modify) complete or partial solutions found online. Plagiarism detection methods may be used for detection of copying, and student will be subject to AIB notification in such cases.
Date  Lecture Content  Reading  Notes/Links  Slides  Assignment Due 

Review the slides. It is you responsibility to be familiar with the following:

Review Slides  
Jan 14  Introduction

Ch 1  Josephus Information Form 
Introduction  
Jan 16  Programming Environment

Bring Laptop to class! 

Jan 18  Proof By Induction

Ch 2  Induction  LeetCode0  
Jan 21  Algorithm Proof by Loop Invarient  Ch 2  Proofs of Algorithms  
Jan 23  Present LeetCode1 solutions Algorithm Proof By Induction: 
Proofs of Algorithms  LeetCode1  
Jan 25  Graph Theory  Ch 22  Graph Theory  
Jan 28  Graph Theory Proof Example  Ch 23  Course Project Instructions  
Jan 30  Cold Day!  Problem Set 1, tex, Teams Moodle 

Feb 1  Present Problem Set 1 Solutions Greedy Algorithms

Dijkstra's Algorithm  Problem Set 1, tex, Teams Moodle 

Feb 4  Greedy Algorithms

Interval Scheduling Fractional Knapsack 

Feb 6  Runtime Analysis

Ch 3  
Feb 8  Present LeetCode2 solutions Runtime Analysis. 
Ch 3  Asymptotic Analysis  LeetCode2  
Feb 11  Runtime Analysis Present Problem Set 2 Solutions 
Asymptotic Analysis BigO, LittleO, Theta, Omega 
Problem Set 2, Teams, moodle  
Feb 13  Runtime Analysis  CH 16  Greedy Algorithms  
Feb 15  Presentation Overview Runtime Analysis 
Ch 17  
Feb 18  Huffman Codes Heaps and Priority Queues 
Ch 22, 23  Kruskal  LeetCode3 

Feb 20  More on UnionFind and MST Midterm Questions 
01UnionFind.pdf  Kruskal  Problem Set 3, Teams, moodle  
Feb 22  Minimum Spanning Trees Prim’s Algorithm UnionFind Structure 
Exam Study Guide  Presentation Topic Submit  
Feb 25  Ch 4, 7  
Feb 27  Exam 1  CH 4.5  
Mar 1  Art Gallary Visit  Art and Algorithms  
Spring Break  
Mar 18  Divide and conquer

CH 4  https://repl.it/@JimSkon/findmaxsubarraypy  
Mar 20  Sorting with divide and conquer  CH 4  DivideAndConquerNotes.pdf  Divide & Conquer sorting  Problem Set 4, Teams Moodle 
Mar 22  Analyzing Recurrence relations  CH 4  Bounding Recurrences Relations  
Mar 25  Analyzing Recurrence relations  4  Master Theorem  LeetCode4  
Mar 27  Divide and Conquer  8  InversionCounting Code (n^2) InversionCountingMerge 
InversionCounting ClosestPoint 

Mar 29  Linear Sorting  15  Linear Sorting 
Problem Set 5, Teams, Moodle  
Apr 1  Dynamic Programming

15  Dynamic Programming  
Apr 3  Dynamic Programming

15  RodCutting  LeetCode5  
Apr 5  Dynamic Programming

weighted_interval_selection  LeetCode6  
Apr 8  Dynamic Programming

15  Russian Doll Envelope  LeetCode7  
Apr 10  Searching

11  Hashing Animation  Hashing  Problem Set 6 , Teams , Moodle 
Apr 12  Searching

11  HashingConsiderations  LeetCode8  
Apr 15 

Exam 2 Study Guide  Trees  Presentation Outline  
Apr 17  Tree Structures  12&18  BTree Simulation B+ Tree Simulation 
Trees  
Apr 19  Problem Set 7, Moodle, Teams This problem set is optional and extra credit. 

Apr 22  Exam 2


Apr 24  P and NP, nondeterminism, reductions  34  AlgorithmicIntractability  LeetCode9  
Apr 26  P and NP, nondeterminism, reductions  34  Reduction Video  AlgorithmicIntractability  Problem Set 7B 
Apr 29  Reductions

SubsetSumProof  
May 1  Final Presentations  
May 3  Final Presentations  Problem Set 8 (Extra Credit) Moodle  
May 9  Final Presentations 8:30  Presentation Time Sign Up  Moodle link to turn in presentation 
Statement on Title XI
Kenyon College does not discriminate in its educational programs and activities on the basis of race, color, national origin, ancestry, sex, gender, gender identity, gender expression, sexual orientation, disability, age, religion, medical condition, veteran status, marital status, genetic information, or any other characteristic protected by institutional policy or state, local, or federal law. The requirement of nondiscrimination in educational programs and activities extends to employment and admission.
All employees, including faculty, are considered Responsible Employees and must notify the College's Civil Rights & Title IX Coordinator with any relevant information.
For further information, please refer to the following Kenyon College policies:
Sexual Misconduct & Harassment: Title IX, VAWA, Title VII:
Discrimination & Discriminatory Harassment Policy (non sex or gender):
https://www.kenyon.edu/directories/officesservices/ocr/discrimination/
ADA & Section 504:
https://www.kenyon.edu/directories/officesservices/ocr/discrimination/504adagrievance/studentgrievanceprocedureresolvingcomplaintsunderadasection504/
I  Attachment  History  Action  Size  Date  Who  Comment 

jpg  Algorithms.jpg  r1  manage  30.1 K  20181217  03:10  JimSkon  
PS01.pdf  r3 r2 r1  manage  114.2 K  20190116  20:39  JimSkon  
zip  PS01.zip  r1  manage  2.2 K  20190116  19:23  JimSkon  
PS02.pdf  r1  manage  90.2 K  20190128  18:26  JimSkon  
PS03.pdf  r2 r1  manage  114.8 K  20190211  17:21  JimSkon  
PS04.pdf  r1  manage  158.0 K  20190211  17:26  JimSkon  
PS05.pdf  r1  manage  103.3 K  20190324  19:18  JimSkon  
PS06.pdf  r1  manage  120.6 K  20190324  19:47  JimSkon  
PS07.pdf  r1  manage  107.1 K  20190324  20:00  JimSkon  
PS07B.pdf  r1  manage  90.0 K  20190418  20:02  JimSkon  
PS08.pdf  r1  manage  119.8 K  20190422  12:39  JimSkon 