"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.
While it is not required, it is highly encouraged that you participate in the ACM programming contests, first the one here at Kenyon on Sept. 24, and then in the one at YSU on November 4 and 5.
If you fully participate in the September 24 contest you will receive a 2% overall course bonus that will count against any points lost. If you participate in both the September 24 contest AND and November 5 contests you will receive a total % overall course bonus. (You cannot participate in the latter contest without being in the former).
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  Quiz  Slides  Assignment Due 

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

Review Material  
Aug 26  Introduction

Ch 1  Josephus  01intro.pptx  
Aug 29  Programming Environment

Bring Laptop to class! 

Aug 31  Proof By Induction

Ch 2  02induction.pptx  LeetCode0  
Sept 2  Present LeetCode 1 solutions Proof By Induction

03InductionPrograms.pptx  LeetCode1  
Sept 5  Proof By Induction:

AlgorithmProofs.pptx  
Sept 7  Graph Theory  Ch 22  GraphTheory.pptx  
Sept 9  Graph Theory Proof Example Present LeetCode 2 solutions  Ch 23  Course Project Instructions  LeetCode2  
Sept 12  Present Problem Set 1 Solutions  Problem Set 1  
Sept 14  Greedy Algorithms

dijkstra.pptx  
Sept 16  Greedy Algorithms

intervalScheduling.pptx knapsack.pptx 

Sept 19  Runtime Analysis

Ch 3  Problem Set 2 Solutions 

Sept 21  Runtime Analysis.  Ch 3  asymptotic.pptx  
Sept 23  Project Overview Runtime Analysis 

Sept 26  Greedy Algorithms

CH 16  greedyOverview.ppt  
Sept 28  Huffman Codes Heaps and Priority Queues 
Ch 17  LeetCode3 Problem Set 3 

Sept 30  Minimum Spanning Trees

Ch 22, 23  kruskal.pptx  Presentation Topic Submit  
Oct 3  More on UnionFind and MST Midterm Questions 
01UnionFind.pdf  
Oct 5  Exam 1  Exam Study Guide  
Oct 7  Midterm Break  
Oct 10  Divide and Conquer

Ch 4, 7  MidtermSolutions.pdf  DivideConquer.pptx  
Oct 12  Analyzing Recurrence relations  CH 4.5  recurences.pptx  LeetCode4  
Oct 14  A visit to the Art Show.  RAFAEL LOZANOHEMMER Navier–Stokes equations in JavaScript 
Problem Set 4 Moodle 

Oct 17  Analyzing Recurrence relations  CH 4  recurences.pptx  
Oct 19  Analyzing Recurrence relations  CH 4  Master Theorem  recurences.pptx  
Oct 21  Analyzing Recurrence relations  CH 4  
Oct 24  Divide and conquer

4  DivideAndConquerNotes.pdf  InversionCounting.pptx closestpoint.pptx  Problem Set 5 Moodle  
Oct 26  Linear Sorting  8  linearsorting.pptx  LeetCode5  
Oct 28  Dynamic Programming

15  dynamicprogramming.ppt  
Oct 31  Dynamic Programming

15  LeetCode6  
Nov 2  Dynamic Programming

15  rodcut.pptx  
Nov 4  Dynamic Programming

weighted_interval_selection.pptx  LeetCode7  
Nov7  Dynamic Programming

15  Russian Doll Envelope  Problem Set 6  
Nov 9  Searching

11  HashingIntro.ppt  LeetCode8  
Nov 11  Searching

11  HashingConsiderations.ppt  Presentation Outline  
Nov 14 

Exam 2 Study Guide  
Nov 16  Tree Structures  12&18  BTree Simulation B+ Tree Simulation 
Trees.pptx  
Nov 18  Problem Set 7  
Nov 2125  Thanksgiving Break  
Nov 28  Exam 2

LeetCode9  
Nov 30  P and NP, nondeterminism, reductions  34  AlgorithmicIntractability.pptx  
Dec 2  P and NP, nondeterminism, reductions  34  Reduction Video  AlgorithmicIntractability.pptx  
Dec 5  Reductions

SubsetSumProof.ppt  
Dec 7  Reductions  Problem Set 8 Moodle  
Dec 14  Final Presentations 1:30  Presentation Time Sign Up  Moodle link to turn in presentation 
Statement on Title XI
Kenyon College seeks to provide an environment that is free of gender bias, discrimination, and harassment. If you have been the victim of sexual harassment/misconduct/assault,
interpersonal violence, or stalking we encourage you to report this. If you report this to a faculty member, she or he must notify Kenyon's Title IX coordinator of any information about the incident that you provide. Kenyon College's Title IX and VAWA Policy is available at: http://www.kenyon.edu/directories/officesservices/titleix/policy/
I  Attachment  History  Action  Size  Date  Who  Comment 

01UnionFind.pdf  r1  manage  1274.0 K  20161003  10:20  JimSkon  
pptx  01intro.pptx  r2 r1  manage  17043.4 K  20160826  04:25  JimSkon  
pptx  02induction.pptx  r1  manage  255.0 K  20160831  12:05  JimSkon  
pptx  03InductionPrograms.pptx  r1  manage  1101.6 K  20160902  04:13  JimSkon  
jpg  411VkO1lL._SX359_BO1204203200_.jpg  r1  manage  30.1 K  20160814  20:20  TWikiAdminUser  Text 
pptx  AlgorithmProofs.pptx  r2 r1  manage  1128.5 K  20160905  09:40  JimSkon  
pptx  AlgorithmicIntractability.pptx  r1  manage  840.1 K  20161130  06:13  JimSkon  
DivideAndConquerNotes.pdf  r1  manage  3204.4 K  20161024  04:11  JimSkon  
pptx  DivideConquer.pptx  r1  manage  3156.8 K  20161010  10:28  JimSkon  
pptx  GraphInClassProof.pptx  r1  manage  357.5 K  20160907  11:36  JimSkon  
pptx  GraphTheory.pptx  r1  manage  1317.2 K  20160907  11:36  JimSkon  
ppt  HashingConsiderations.ppt  r1  manage  182.5 K  20161109  07:24  JimSkon  
ppt  HashingIntro.ppt  r2 r1  manage  1024.5 K  20161114  13:03  JimSkon  
pptx  InversionCounting.pptx  r1  manage  97.8 K  20161024  03:56  JimSkon  
MidtermSolutions.pdf  r1  manage  183.9 K  20161007  15:06  JimSkon  
PS01.pdf  r6 r5 r4 r3 r2  manage  111.0 K  20160905  02:23  JimSkon  
PS02.pdf  r1  manage  87.9 K  20160912  20:40  JimSkon  
PS02.sol.pdf  r1  manage  124.9 K  20160922  03:32  JimSkon  
PS03.pdf  r1  manage  113.3 K  20160919  02:21  JimSkon  
PS04.pdf  r2 r1  manage  155.8 K  20161010  20:21  JimSkon  
PS04n.pdf  r1  manage  155.8 K  20161010  20:24  JimSkon  
PS05.pdf  r1  manage  113.6 K  20161013  15:34  JimSkon  
PS06.pdf  r1  manage  109.6 K  20161031  06:58  JimSkon  
PS07.pdf  r3 r2 r1  manage  103.3 K  20161117  15:45  JimSkon  
PS08.pdf  r1  manage  115.7 K  20161202  11:56  JimSkon  
ppt  SubsetSumProof.ppt  r2 r1  manage  3469.5 K  20161207  13:04  JimSkon  
pptx  Trees.pptx  r1  manage  140.2 K  20161116  04:39  JimSkon  
pptx  asymptotic.pptx  r1  manage  519.2 K  20160921  11:47  JimSkon  
pptx  closestpoint.pptx  r1  manage  167.5 K  20161024  03:57  JimSkon  
pptx  dijkstra.pptx  r1  manage  205.4 K  20160914  11:33  JimSkon  
ppt  dynamicprogramming.ppt  r1  manage  564.5 K  20161028  11:18  JimSkon  
ppt  greedyOverview.ppt  r1  manage  2848.5 K  20160926  03:48  JimSkon  
pptx  intervalScheduling.pptx  r2 r1  manage  118.1 K  20160916  13:17  JimSkon  
pptx  knapsack.pptx  r1  manage  557.7 K  20160916  12:00  JimSkon  
pptx  kruskal.pptx  r1  manage  623.3 K  20160930  12:03  JimSkon  
pptx  linearsorting.pptx  r1  manage  225.7 K  20161025  02:49  JimSkon  
pptx  recurences.pptx  r1  manage  223.1 K  20161012  12:01  JimSkon  
pptx  review.basic_tools.pptx  r1  manage  229.7 K  20160814  01:37  TWikiAdminUser  Review Topics 
pptx  rodcut.pptx  r1  manage  1458.3 K  20161102  11:20  JimSkon  
pptx  weighted_interval_selection.pptx  r2 r1  manage  183.1 K  20161104  08:53  JimSkon 