COMP 340: Analysis of Algorithms, Spring 2024

This syllabus is subject to change based on specific class needs, especially the schedule. Significant deviations will be discussed in class. Individual exceptions to the policies and schedule are granted only in cases of true emergency. Please make arrangements with me if an emergency arises.

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 12 chapters of the main text (TADM) plus occasional material from other sources:

Sources

The required course textbook is:

We will occasionally pull material from other sources, especially for parallel algorithms. Any 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.

Assessment

Assignments and 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 Amount Final Grade Weight Average Time/Week (Hours)
Lectures 52 10% (Participation) 3.33
Problem Sets 6–8 25% 4.5
Quizzes 5–7 25% -
Research Project 1 20% 1.5
Exam/Quiz Study - - 1.67
Exams 2 20% -
Reading - - 2
      13

Generally problem sets and quizzes will alternate weeks. There will be a research project on any algorithms-related topic, culminating in a paper and presentation to the class. There are two exams – a midterm and a final – both worth 10% each. The final exam will focus primarily, but not exclusively, on material covered since the midterm. In other words, it will contain a few questions on material from the first half of the semester.

Grading

Your participation grade is based on a variety of activities. During class I will often make use of the Socrative app, so you’ll need to install this on your phones. Participating in Socrative questions and with in-class group activities is required for a decent participation grade; an A includes asking questions either in class or in office hours.

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. Assignments and final grades use a standard grading scale shown below and will not be curved except in rare cases when deemed necessary by the instructor.

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

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.

Policies

Schedule

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

Unless otherwise specified, the readings come from TADM.

Date Topic Assignment and Readings
Wed 01/17 (Week 1) Intro to Algorithm Design  
Fri 01/19 Interval Scheduling, Correctness 1.1-1.3, PS01 out
Mon 01/22 (Week 2) Proof Exercises 1.4-1.9
Wed 01/24 Big-O/Complexity Review 2.1-2.4
Fri 01/26 Analysis Examples 2.5-2.6, Quiz 01
Mon 01/29 (Week 3) PS01 Questions 2.7-2.9
Wed 01/31 Basic Data Structures, Dynamic Array 3.1-3.2
Fri 02/02 PS01 Questions PS02
Mon 02/05 (Week 4) Dictionaries 3.3
Wed 02/07 Trees, (Balanced) BSTs 3.4
Fri 02/09 Priority Queues, Heaps, Heapsort 3.5-3.6, 4.3, Quiz 02
Mon 02/12 (Week 5) Hashing 3.7-3.9
Wed 02/14 Sorting, Mergesort (idea) 4.1-4.3
Fri 02/16 PS02 Questions, Mergesort (analysis) 4.4-4.5, PS03
Mon 02/19 (Week 6) Quicksort Code/Analysis, Quickselect 4.6-4.8
Wed 02/21 Binary search 5.1-5.2
Fri 02/23 Recurrence Relations 5.3-5.4, Quiz 03
Mon 02/26 (Week 7) Review Master Theorem, D&C Examples I: MCSS 5.5-5.6
Wed 02/28 D&C: Closest Pair, Parallel Algorithms I 5.7-5.8
Fri 03/01 Parallel Algorithms II: Scheduling, Reduction Project
Mon 03/04 (Week 8) Parallel Algorithms III: Parallel Mergesort  
Wed 03/06 Midterm Review  
Fri 03/08 Midterm  
(Mon 03/11 – Fri 03/15) (Spring Break)  
Mon 03/18 (Week 9) Midterm Solutions  
Wed 03/20 Problem Set Review  
Fri 03/22 Probability, Hashing Details 6.1-6.3, PS04
Mon 03/25 (Week 10) Bloom Filters, Perfect Hashing 6.4-6.5
Wed 03/27 Graphs 7.1-7.4, Quiz 04
(Fri 03/29) (Easter Break)  
(Mon 04/01) (Week 11) (Easter Break)  
Wed 04/03 Graph Traversal, BFS 7.5-7.7
Fri 04/05 DFS 7.8-7.10, PS05
Mon 04/08 (Week 12) Applications of DFS on Directed Graphs  
Wed 04/10 MSTs 8.1-8.2
Fri 04/12 Union-Find, Shortest Paths 8.3-8.4, Quiz 05
Mon 04/15 (Week 13) Dijkstra’s, Floyd-Warshall  
Wed 04/17 Network Flows, Min-Cut 8.5-8.7
Fri 04/19 Backtracking 9.1-9.3, PS06
Mon 04/22 (Week 14) Intro to Dynamic Programming 10.1
Wed 04/24 Edit Distance 10.2
Fri 04/26 Longest Increasing Subsequence 10.3-10.4, Quiz 06
Mon 04/29 (Week 15) Reductions 11.1-1.2
Wed 05/01 Basic Reductions 11.3, 11.6-11.8
Fri 05/03 P vs. NP 11.9
Mon 05/06 (Week 16) Presentations  
Wed 05/08 Final Review  
Sat 05/11 3:00 PM–6:00 PM Final Exam  

Monmouth College Services