COMP 340: Analysis of Algorithms, Spring 2018

This syllabus is subject to change based on specific class needs, especially the schedule. Significant deviations will be discussed in class.

Logistics

Content

The study of algorithms is one of the most crucial areas of in Computer Science. In this course, students will learn the basic tools of algorithm design and analysis through the study of some of the most well known and important algorithms. By the end of the semester, students will have developed not only a firm grounding in the analysis and design of algorithms, but working knowledge of the algorithms that have made computing what it is today.

There are too many algorithms topics to cover fully in a one semester course. To compensate, students will complete an in-depth research project on an algorithms-related topic of their choice, providing not only further depth but also project management skills. While this class focuses mostly on the theoretical design and analysis of algorithms, students will have opportunities to implement algorithms in the language of their choice.

Topics

This course will emphasize the first eight chapters of the main text (TADM) interleaved with selections from ADPS:

Time permitting, we’ll examine TADM chapter 9 and some basic issues in NP-Completeness and reductions.

Sources

The required course textbook is:

We will also pull some parallel algorithms material from the online textbook draft Algorithm Design: Parallel and Sequential (ADPS), by Umut Acar and Guy Blelloch, available at http://www.parallel-algorithms-book.com/. Any other required readings will be posted on this webpage as needed.

I encourage you to take advantage of the wealth of algorithms study resources that can be found online. This material can be difficult; exposure to multiple sources is always useful and sometimes necessary to fully grasp it. I will list here some resources that may be useful (and fun!). Please suggest links to add as you find them.

Policies

Assessment

Assignments

The course workload is as follows:

Category Number of Assignments Final Grade Weight
Problem Sets 6-8 20%
Quizzes 5-6 25%
Paper+Presentation 1 20%
Midterm 1 10%
Final 1 15%
Participation - 10%

Generally problem sets and quizzes will alternate weeks. There will be a research projects on any algorithms-related topic, culminating in a paper and presentation to the class. The final exam will focus primarily, but not exclusively, on material covered since the midterm.

Grading

Your final grade is based on a weighted average of particular assignment categories, with weights shown above. You can estimate your current grade based on your scores and these weights. You may always visit the instructor outside of class to discuss your current standing.

This courses uses a standard grading scale. Assignments and final grades will not be curved except in rare cases when its deemed necessary by the instructor. Percentage grades translate to letter grades as follows:

Score Grade
94–100 A
90–93 A-
88–89 B+
82–87 B
80–81 B-
78–79 C+
72–77 C
70–71 C-
68–69 D+
62–67 D
60–61 D-
0–59 F

You are always welcome to challenge a grade that you feel is unfair or calculated incorrectly. Mistakes made in your favor will never be corrected to lower your grade. Mistakes made not in your favor will be corrected. Basically, after the initial grading your score can only go up as the result of a challenge.

Workload

The weekly workload for this course will vary by student and over the semester, but on average should be about 13 hours per week. The follow table provides a rough estimate of the distribution of this time over different course components for a 16 week semester.

Category Total Time Time/Week (Hours)
Lectures   3.3
Problem Sets 72 4.5
Exam/Quiz Study 27 1.7
Research Project 24 1.5
Reading+Unstructured Study   2
    13

Schedule

The following tentative calendar should give you a feel for how work is distributed throughout the semester. Assignments and events are listed in the week they are due or when they occur. This calendar is subject to change based on the circumstances of the course.

Unless otherwise specified, the readings come from TADM.

Date Topic Assignment
Mon 01/15 Intro to Algorithm Design Read 1.1-1.4 (optionally 1.5-1.6)
Tue 01/16 Interval Scheduling, Correctness  
Wed 01/17 Induction Examples, RAM Model Read 2.1
Fri 01/19 Asymptotic Notation PS 1 out, Read 2.2-2.7
Mon 01/22 Parallel Analysis Read ADPS 1.1-1.2
Tue 01/23 Divide and Conquer  
Wed 01/24 Master Theorem Read TADM 4.5,4.10, ADPS 8.1-8.2
Fri 01/26 Prefix Sums (Scan) Quiz 1, Read 8.3
Mon 01/29 More Scan, Contraction Read ADPS 7
Tue 01/30 Faster Scan with Contraction  
Wed 01/31 MCSS Read ADPS 9
Fri 02/02   PS 2 out
Mon 02/05 Basic Data Structures Read TADM 3.1-3.2
Tue 02/06 Dictionaries, Trees, Priority Queues Read 3.3-3.5
Wed 02/07 Heaps and Heapsort Read 4.3 (optionally 4.1-4.2)
Fri 02/09   Quiz 2
Mon 02/12 Meldable Priority Queues Read ADPS 21
Tue 02/13 Leftist Heaps  
Wed 02/14 Quicksort PS 3 out, Read 4.6
Fri 02/16 Basic Probability Read ADPS 10
Mon 02/19 Expected Bounds vs. High Probability Read ADPS 11.1
Tue 02/20 Finding the Top Two Read ADPS 11.2
Wed 02/21 Quickselect Analysis Read ADPS 11.3
Fri 02/23 Quicksort Analysis Read ADPS 11.4
Mon 02/26 Basic Hashing PS 3 due, Read 3.7
Tue 02/27 Review  
Wed 02/28 Midterm PS 4 out
Fri 03/02 (No Class) Project out
(03/05–03/09) (Spring Break) (Spring Break)
Mon 03/12 Midterm Review, Graphs Read ADPS 14.1-14.2, TADM 5.1-5.2
Tue 03/13 Data Structures for Graphs Read TADM 5.6
Wed 03/14 BFS and Applications Read TADM 5.7
Fri 03/16 Two Coloring Quiz 3
Mon 03/19 DFS Read TADM 5.8
Tue 03/20 Finding Cycles and Articulation Vertices Read TADM 5.9
Wed 03/21 Topological Sort  
Fri 03/23 MST, Prim’s Algorithm PS 5 out, Read TADM 6.1.1
Mon 03/26 Kruskal’s Algorithm Read TADM 6.1.2-6.1.4
Tue 03/27 Shortest Paths Topic claiming begins, Read TADM 6.3
Wed 03/28   Quiz 4
(03/30–04/02) (Easter Break) (Easter Break)
Tue 04/03 Backtracking Read TADM 7.1-7.3
Wed 04/04 Backtracking with Pruning Read TADM 7.4, Topic and Focus must be approved
Fri 04/06 Heuristic Search PS 6 out (data files), Skim TADM 7.5
Mon 04/09 Intro to Dynamic Programming Read TADM 8.1.1-8.1.3
Tue 04/10 Binomial Coefficients, APSP Read TADM 8.1.4, 6.3.2
Wed 04/11 Edit Distance Read 8.2.1-8.2.3
Fri 04/13 Edit Distance Variants, Quiz Quiz 5, Read 8.2.4, 8.3
Mon 04/16 Parallel Edit Distance, Knapsack with DP  
Tue 04/17 TSP with DP, Limitations of DP Anno. Bib. due, Read TADM 8.7
Wed 04/18 Reductions Read TADM 9.1-9.2
Fri 04/20 Satisfiability PS 7 out, Read TADM 9.4
Mon 04/23 SAT -> 3SAT  
(04/24) (Scholars Day) (Scholars Day)
Wed 04/25 3SAT -> VC Paper Due, Read TADM 9.5.2
Fri 04/27 VC -> IS Read 9.3, 9.6
Mon 04/30 Presentations Peer Review Due
Tue 05/01 Presentations  
Wed 05/02 P vs. NP Read 9.9-9.10
(Fri 05/04) (No class; other finals) PS 7 due.
Tues 05/08 6:30 PM Final Exam  

Monmouth College Services