Tags:
create new tag
view all tags

MATH 391 ST:Design & Analysis Algorithms

James Skon
Fall 2016
Location: Hayes 203, Time: 8:10-9:00, Days: MWF

"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

Objectives

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:

  1. analyze the asymptotic performance of algorithms;
  2. demonstrate a familiarity with major algorithms and data structures;
  3. apply important algorithmic design paradigms and methods of analysis; and
  4. synthesize efficient algorithms in common engineering design situations.
Prerequisite: MATH 222 and SCMP 118 or PHYS 270 or equivalent.

Course Information

  • James Skon
  • Office Hayes Hall 303
  • Office Hours: MTWHF 10:00-11:00
  • Phone: (740) 427-5369
  • Textbook: Introduction to Algorithms, 3rd Edition, MIT Press, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, ISBN 0262033844
  • Room and Time: Hayes 203, Time: 8:10-9:00, Days: MWF
  • Paperless: This course is intentionally paperless. All assignments are turned in online through Moodle. The instructor will normally not accept work written or printed on paper. (Any exceptions must be pre-approved by the instructor).
41-1VkO1lL._SX359_BO1204203200_.jpg

Course Grades

Class Attendance/Participation 10%
Problem Sets 30%
LeetCode Assignments 20%
Exams 20%
Final Project/Presentation 20%

Email help

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.

Lectures and Lecture Slides

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.

Readings

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.

Problem Sets

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 grace-period 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.

LeetCode Assignments

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.

Programming Contest (extra credit)

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).

Collaboration

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 re-create 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.)

Term Project

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:

  1. (Theory) A review, analysis, and presentation of a relatively recent algorithm of some notability (something from the past 5-10 years). This should include a comprehensive explanation of the algorithm operation and complexity (space and time), a comparison with other techniques, and a review of the proof of both the analysis and the correctness of the algorithm.
  2. (Practice) The implementation, analysis, and testing of some significant algorithm technique or method not explored in this class. You find a problem from this class, or from work you have done or are doing elsewhere, and explore the use of one or more advanced algorithmic technique. This should also include an actual comparative runtime comparison with other techniques varying both the problem size, and the type, of the datasets.
The results of either will be presented during the finals period in a 30 minute time slot. The presentation will be evaluated by both the instructor, and the other students.

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

Plagiarism

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.

Links

Date Lecture Content Reading Notes/Links Quiz Slides Assignment Due
  Review the slides. It is you responsibility to be familiar with the following:
  • Logarithms
  • Graphs
  • Proof notation
  • Pseudocode
  • Heaps
  • Array v. Lists
      review.basic_tools.pptx  
Aug 26 Introduction
  • Joseph Flavius
  • Course Details
Ch 1 Josephus   01intro.pptx  
Aug 29

Programming Environment

  • NetBeans
  • LeetCode
  Bring Laptop to class!
     
Aug 31 Proof By Induction
  • Proof: Tiling
  • Proof: A tree of n nodes has n-1 edges
Ch 2     02induction.pptx LeetCode0
Sept 2

Present LeetCode 1 solutions

Proof By Induction

  • (Faulty) Proof: Right-handed people do not exist
  • Proof: Candy Bars
      03InductionPrograms.pptx LeetCode1
Sept 5 Proof By Induction:
  • Proving programs correct 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
  • Disjkstra's Algorithm
      dijkstra.pptx  
Sept 16

Greedy Algorithms

  • Classroom Scheduling
      intervalScheduling.pptx
knapsack.pptx
 
Sept 19 Runtime Analysis
  • Asymptotic notation
  • Worst-case analysis
  • Binary search
  • Problem bounds
Present Problem Set 2 Solutions
Ch 3       Problem Set 2
Solutions
Sept 21 Runtime Analysis. Ch 3     asymptotic.pptx  
Sept 23 Project Overview
Runtime Analysis
         
Sept 26 Greedy Algorithms
  • Overview
  • Huffman Codes
CH 16     greedyOverview.ppt  
Sept 28 Huffman Codes
Heaps and Priority Queues
Ch 17       LeetCode3
Problem Set 3
Sept 30

Minimum Spanning Trees

  • Prim’s Algorithm
  • Kruskal’s Algorithm
  • Union-Find Structure
Ch 22, 23     kruskal.pptx Presentation Topic Submit
Oct 3 More on Union-Find and MST
Midterm Questions
  01UnionFind.pdf      
Oct 5 Exam 1   Exam Study Guide      
Oct 7 Midterm Break          
Oct 10

Divide and Conquer

  • Sorting
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
LOZANO-HEMMER

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

  • Inversion Counting
  • Minimum Distance
4 DivideAndConquerNotes.pdf InversionCounting.pptx closestpoint.pptx   Problem Set 5 Moodle

Presentation Status Report

Oct 26 Linear Sorting 8   linearsorting.pptx LeetCode5
Oct 28

Dynamic Programming

  • Introduction
15     dynamic-programming.ppt  
Oct 31

Dynamic Programming

  • Linear Sorting
15       LeetCode6
Nov 2

Dynamic Programming

  • Rodcutting
15     rodcut.pptx  
Nov 4

Dynamic Programming

  • Weighted Interval Selection
      weighted_interval_selection.pptx LeetCode7
Nov7

Dynamic Programming

  • Russian Doll Envelope
15 Russian Doll Envelope     Problem Set 6
Nov 9 Searching
  • Hashing
11     HashingIntro.ppt LeetCode8
Nov 11

Searching

  • Hashing Consideration
11     HashingConsiderations.ppt Presentation Outline
Nov 14
  • Present Problem Set 6 Solutions
  • Present LeetCode 8 solutions
  Exam 2 Study Guide      
Nov 16 Tree Structures 12&18 B-Tree Simulation
B+ Tree Simulation
  Trees.pptx  
Nov 18           Problem Set 7
Nov 21-25 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
  • Subset Sum
  • Hamiltonian Path
*
      SubsetSumProof.ppt  
Dec 7 Reductions         Problem Set 8 Moodle
Dec 14 Final Presentations 1:30   Presentation Time Sign Up  

PresentationGradingRubric

PresentationPeerEvaluation

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/offices-services/title-ix/policy/

Team Selector - Students

-- Jim Skon - 2016-08-08

Comments


  • : Review Topics

  • : 02induction.pptx

  • : knapsack.pptx

Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf 01UnionFind.pdf r1 manage 1274.0 K 2016-10-03 - 10:20 JimSkon  
PowerPointpptx 01intro.pptx r2 r1 manage 17043.4 K 2016-08-26 - 04:25 JimSkon  
PowerPointpptx 02induction.pptx r1 manage 255.0 K 2016-08-31 - 12:05 JimSkon  
PowerPointpptx 03InductionPrograms.pptx r1 manage 1101.6 K 2016-09-02 - 04:13 JimSkon  
JPEGjpg 41-1VkO1lL._SX359_BO1204203200_.jpg r1 manage 30.1 K 2016-08-14 - 20:20 TWikiAdminUser Text
PowerPointpptx AlgorithmProofs.pptx r2 r1 manage 1128.5 K 2016-09-05 - 09:40 JimSkon  
PowerPointpptx AlgorithmicIntractability.pptx r1 manage 840.1 K 2016-11-30 - 06:13 JimSkon  
PDFpdf DivideAndConquerNotes.pdf r1 manage 3204.4 K 2016-10-24 - 04:11 JimSkon  
PowerPointpptx DivideConquer.pptx r1 manage 3156.8 K 2016-10-10 - 10:28 JimSkon  
PowerPointpptx GraphInClassProof.pptx r1 manage 357.5 K 2016-09-07 - 11:36 JimSkon  
PowerPointpptx GraphTheory.pptx r1 manage 1317.2 K 2016-09-07 - 11:36 JimSkon  
PowerPointppt HashingConsiderations.ppt r1 manage 182.5 K 2016-11-09 - 07:24 JimSkon  
PowerPointppt HashingIntro.ppt r2 r1 manage 1024.5 K 2016-11-14 - 13:03 JimSkon  
PowerPointpptx InversionCounting.pptx r1 manage 97.8 K 2016-10-24 - 03:56 JimSkon  
PDFpdf MidtermSolutions.pdf r1 manage 183.9 K 2016-10-07 - 15:06 JimSkon  
PDFpdf PS01.pdf r6 r5 r4 r3 r2 manage 111.0 K 2016-09-05 - 02:23 JimSkon  
PDFpdf PS02.pdf r1 manage 87.9 K 2016-09-12 - 20:40 JimSkon  
PDFpdf PS02.sol.pdf r1 manage 124.9 K 2016-09-22 - 03:32 JimSkon  
PDFpdf PS03.pdf r1 manage 113.3 K 2016-09-19 - 02:21 JimSkon  
PDFpdf PS04.pdf r2 r1 manage 155.8 K 2016-10-10 - 20:21 JimSkon  
PDFpdf PS04n.pdf r1 manage 155.8 K 2016-10-10 - 20:24 JimSkon  
PDFpdf PS05.pdf r1 manage 113.6 K 2016-10-13 - 15:34 JimSkon  
PDFpdf PS06.pdf r1 manage 109.6 K 2016-10-31 - 06:58 JimSkon  
PDFpdf PS07.pdf r3 r2 r1 manage 103.3 K 2016-11-17 - 15:45 JimSkon  
PDFpdf PS08.pdf r1 manage 115.7 K 2016-12-02 - 11:56 JimSkon  
PowerPointppt SubsetSumProof.ppt r2 r1 manage 3469.5 K 2016-12-07 - 13:04 JimSkon  
PowerPointpptx Trees.pptx r1 manage 140.2 K 2016-11-16 - 04:39 JimSkon  
PowerPointpptx asymptotic.pptx r1 manage 519.2 K 2016-09-21 - 11:47 JimSkon  
PowerPointpptx closestpoint.pptx r1 manage 167.5 K 2016-10-24 - 03:57 JimSkon  
PowerPointpptx dijkstra.pptx r1 manage 205.4 K 2016-09-14 - 11:33 JimSkon  
PowerPointppt dynamic-programming.ppt r1 manage 564.5 K 2016-10-28 - 11:18 JimSkon  
PowerPointppt greedyOverview.ppt r1 manage 2848.5 K 2016-09-26 - 03:48 JimSkon  
PowerPointpptx intervalScheduling.pptx r2 r1 manage 118.1 K 2016-09-16 - 13:17 JimSkon  
PowerPointpptx knapsack.pptx r1 manage 557.7 K 2016-09-16 - 12:00 JimSkon  
PowerPointpptx kruskal.pptx r1 manage 623.3 K 2016-09-30 - 12:03 JimSkon  
PowerPointpptx linearsorting.pptx r1 manage 225.7 K 2016-10-25 - 02:49 JimSkon  
PowerPointpptx recurences.pptx r1 manage 223.1 K 2016-10-12 - 12:01 JimSkon  
PowerPointpptx review.basic_tools.pptx r1 manage 229.7 K 2016-08-14 - 01:37 TWikiAdminUser Review Topics
PowerPointpptx rodcut.pptx r1 manage 1458.3 K 2016-11-02 - 11:20 JimSkon  
PowerPointpptx weighted_interval_selection.pptx r2 r1 manage 183.1 K 2016-11-04 - 08:53 JimSkon  
Edit | Attach | Watch | Print version | History: r92 < r91 < r90 < r89 < r88 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r92 - 2017-12-29 - JimSkon
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback