CSCI140 PO-01 Algorithms

Fall 2021

Monday and Wednesday

1:20 PM to 3:35 PM Pacific Time

EDMS Room 114 (Edmunds)

Instructors

Professor Anthony Clark

Research Website

Philosophy

I’d like to give a few brief thoughts on my philosophy and the common traits I’ve seen in successful students.

Philosophy

Traits of Success

See my advising page for additional information on CS and being a student at Pomona College.

Teaching Assistants

Jett Bronstein
Meghna Lohia
Alan Zhou
Eric Zhu
Jett Bronstein
Meghna Lohia
Alan Zhou
Eric Zhu

TAs have the following duties:

Office and Mentor Hours

Zoom links are pinned in the course Slack Channel.

You can also contact me on Slack to setup additional office hours.

I highly recommend showing up to mentor sessions with the intent that you’ll work on your homework and then ask the occasional question as it pops up.

Objectives

Catalog Description: Algorithm design, computer implementation and analysis of efficiency. Discrete structures, sorting and searching, parsing, pattern matching and data management. Reducibility and theoretical limitations.

Course Learning Objectives: Upon completion of this course, students will be able to:

Resources

We will not have a book for this class. But our course structure if fairly close to that of the Algorithms Illuminated book series.

This document from fall 2020 is a nice starting point for help. It includes resources for:

Please let me know if you have any other concerns.

Some helpful links to algorithms tutorials, lessons, and visualizations:

Finally, I’d like to recommend listening to the Happiness Lab.

Logistics

These plans are subject to change based on our experiences and your feedback.

For the most part, we will plan on meeting in person, but I have included plans for remote and asynchronous courses below since it may very well come up.

Meeting Periods

Class periods will be used to discuss lecture materials and complete checkpoints. You can find more information about lecture topics and materials in the course schedule and more information about checkpoints below. We will optionally have some asynchronous days throughout the semester. Whenever everyone is feeling the need for a break from routine (I will regularly poll the class).

Zoom Etiquette

You are not expected to have your video on, but it would be nice to turn it on during group discussions in breakout rooms. Also, please set your display name to your preferred name (and include your pronouns if you’d like; for example, “Prof. Clark he/him/his).

During Zoom lectures, I will provide a link to a google sheet that we can use for anonymous discussions.

After lectures, I’d like to leave the zoom room open for an additional 15 minutes for all of you. So, I’ll likely choose willing people to make the host once I leave.

Communication with Slack

Please use Slack (not email) for all communication. If you email me questions, I will likely ask you to make a comment on Slack. This has several benefits:

Slack has text, video, and audio options that the TAs and I will use (along with Zoom) to hold office hours and mentoring sessions. I will also use Slack to solicit anonymous feedback on how the course is going. You can create group messages that include you, other classmates, the TAs, and me if you want to discuss a question asynchronously.

Useful Slack commands:

Working Together

I recommend using Slack (text, audio, or video) for communication, and using the Visual Studio Code Live Share Extension for pair programming. We will spend some time in class getting this setup, but these instructions will also be of use.

Feedback

If you have any question for me, I would love for you to ask them on Slack. I will enable a bot that will allow you to make comments anonymously. The CS department also has an anonymous feedback form if you would like to provide feedback outside of class channels.

Grading

Throughout this semester, I will ask you to complete seven assignments and seven checkpoints. Assignments include written and programming parts (14 parts total) and checkpoints include individual and group parts (14 parts total).

We are using specifications grading for this course. Here are highlights of the grading policy:

To pass an individual checkpoint part you must pass or correct all questions on the checkpoint. If you have a question marked as “No-pass,” then you may correct it by:

  1. Explaining why your answer was marked “No-pass” and how it should be corrected.
  2. Creating and then solving similar problem (not all questions will have this requirement–check your feedback on gradescope).
  3. Walking me through your problem and its solution.

You do not have any limit to the number of corrections you can make during the semester or on a single checkpoint.

Group checkpoints follow the same procedure except that your entire group will be involved in the correction process.

Specifications grading:

  1. gives you a chance to receive feedback and adjust your expectations without affecting your final grade (it gives you space to learn);
  2. should eliminate any compulsion to violate the department’s Academic Honesty Policy; and
  3. will make it easier to provide critical feedback without worrying about your grade (particularly for TAs that might be your acquaintances).

Think of it as having assignments as your practice (e.g., shooting the basketball by yourself in the gym or practicing your lines in front of a mirror) and having checkpoints serve as the performance (e.g., your basketball game or live performance). These ideas, in part, come from Grading for Equity (a nice summary here).

Assignments

You will submit assignments to gradescope. You may work on assignments individually or with a partner of your choice. If you’d like to be assigned a partner, please send me a message on Slack and I will randomly assign partners when I have a pool of students.

Assignments will not be graded per se; instead, you will meet with a TA and walk them through your answers and code. They will then mark your assignment as “passed” or not. You should not meet with a TA until you have completed your assignment. Of course, you can still visit them during mentor sessions to ask for help.

If you do not pass an assignment on the first meeting, then you will need to work on your answers, resubmit, and then schedule a new time to meet with a TA. As a rule-of-thumb, you can think of a “pass” as at least a 90% on the assignment.

I will provide deadlines for meeting with TAs.

Checkpoints

We will have checkpoints during Wednesday class periods. If you foresee a problem with this, please let me know as soon as you can. All checkpoints are on the course schedule and will comprise two-stages:

  1. You will take the quiz individually.
  2. You will retake the quiz in groups.

During the group part, students receive immediate, targeted feedback on their solutions from their fellow students and see alternative approaches to the problems. This makes the exam itself a valuable learning experience. — Gilley and Clarkston

I will grade checkpoints as pass or no-pass using a similar scale to the assignments (90% for a pass).

General Sequence of Assignments and Checkpoints

sequence

Policies

Accommodations

If you have a disability (for example, mental health, learning, chronic health, physical, hearing, vision, neurological, etc.) and expect barriers related to this course, it is important to request accommodations and establish a plan. I am happy to help you work through the process, and I encourage you to contact the Student Disability Resource Center (SDRC) as soon as possible.

I also encourage you to reach out to the SDRC if you are at all interested in having a conversation. (Upwards of 20% of students have reported a disability.)

Academic Honesty and Collaboration

I encourage you to study and work on assignments with your peers (unless otherwise specified). If you are ever unsure about what constitutes acceptable collaboration, please ask!

For more information, see the Computer Science Department and the Pomona College policies.

I take violations of academic honesty seriously. I believe it is important to report all instances, as any leniency can reinforce (and even teach) the wrong mindset (“I can get away with cheating at least once in each class.”).

Academic Advisory Notice

I will do my best to update you if I think you are not performing at your best or if you are not on pace to pass the class. I will first reach out to you and then use the system built-in to my.pomona.edu that will notify your advisor so you are encouraged to work with a mentor or advisor on a plan.

Attendance

I expect you to attend every class, but I will not penalize you for missing class. Know that there is a strong correlation between attendance and grades, and you will almost certainly be indirectly penalized.

You are responsible for any discussions, announcements, or handouts that you miss, so please reach out to me. If you need to leave class early for any reason, please let me know before class begins so that I am not concerned when you leave.

Late Submissions

Late assignments will not be accepted. However, if you plan ahead you can ask for an extension prior to the assignment deadline (at least four days).

Unless requested ahead of time, some assessments (e.g., exams) cannot be completed after the class period in which they are scheduled.

Covid Safety Awareness

During the past academic year, we built community remotely, and this year we will build on the pedagogical improvements we acquired last year. For example, we might meet on zoom from time to time, or hold discussions online.

Our health, both mental and physical, is paramount. We must consider the health of others inside and outside the classroom. All Claremont Colleges students have signed agreements regulating on-campus behavior during the pandemic; in the classroom, we will uphold these agreements. We need to take care of each other for this course to be successful. I ask you therefore to adhere to the following principles:

The pandemic is fast-moving, and we might have to adjust these principles as the semester evolves. I am always happy to receive your feedback to make this course work.

Let’s care for each other, show empathy, and be supportive. While there will likely be some community transmission and breakthrough infections, together, we can minimize their effect on our community and on your learning.

Calendar

August
Sun
Mon
Tue
Wed
Thu
Fri
Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
31
1
2
3
4
September
Sun
Mon
Tue
Wed
Thu
Fri
Sat
29
30
31
2
3
4
5
7
10
11
12
14
16
17
18
19
21
24
25
26
28
30
1
2
October
Sun
Mon
Tue
Wed
Thu
Fri
Sat
26
27
28
29
30
1
2
3
5
8
9
10
12
14
16
17
19
22
23
24
26
29
30
31
1
2
3
4
5
6
November
Sun
Mon
Tue
Wed
Thu
Fri
Sat
31
2
4
5
6
7
9
12
13
14
16
18
19
20
21
25
26
27
28
30
1
2
3
4
December
Sun
Mon
Tue
Wed
Thu
Fri
Sat
28
29
30
2
3
4
5
7
10
11
12
13
14
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1

Schedule

If the schedule below doesn’t look up-to-date, you might need to reload the page while overriding cache.
Here are all resources from the previous time this course was taught

The check-boxes are for your own use so that you can easily come back to this page and see where you left off (I can’t see what you do on this page). I’m using localstorage to get this working, so no guarantees it will work on your device.

DatePre-ClassIn-ClassAssignment
Mon Aug 30
Wed Sep 01
Mon Sep 06Labor Day -- No class
Wed Sep 08
Thu Sep 09
Mon Sep 13
Wed Sep 15

Checkpoint 1: Running Time and Invariants

  • Loop Invariants
  • Total Running Time
  • Asymptotic Running Time Proofs
Mon Sep 20
Wed Sep 22
Thu Sep 23
Mon Sep 27
Wed Sep 29

Checkpoint 2: Recursion and Probability

  • Recurrences and Recursion Trees
  • Divide and Conquer Algorithms
    • Merge Sort
    • Closest Pair
    • Quicksort
    • Randomized Selection
    • ~~Deterministic Selection~~
  • Master Method
  • Expected Values
  • Linearity of Expectation
Mon Oct 04
Wed Oct 06
Thu Oct 07
Mon Oct 11
Wed Oct 13

Checkpoint 3: Graph Theory

  • Connectivity
  • BFS and DFS
  • Topological Orderings
  • Graph Representations
  • Kosaraju's Algorithm (and SCCs)
  • Dijkstra's Algorithm (and SSSP)
Fri Oct 15Family Weekend
Mon Oct 18Fall break -- No Class
Wed Oct 20
Thu Oct 21Last day to drop
Mon Oct 25
Wed Oct 27
Thu Oct 28
  • Assignment 4 is due
    • Dijkstra's Algorithm Coding
    • Data Structures
Mon Nov 01
Wed Nov 03

Checkpoint 4: Data Structures and Memory

  • Heaps
  • Binary Search Trees
  • Red-Black Trees
  • Hash Tables
  • Universal Hashing
  • Data Locality
Mon Nov 08
Wed Nov 10
Thu Nov 11
  • Assignment 5 is due
    • Minimum Spanning Trees Coding
    • Greedy Algorithms
Mon Nov 15
Wed Nov 17

Checkpoint 5: Greedy Algorithms

  • Greedy scheduling
  • Minimum spanning trees (Prim's and Kruskal's)
  • Huffman Codes
  • Max-Spacing K-Clustering
  • Exchange Arguments
Mon Nov 22
Tue Nov 23
Wed Nov 24Thanksgiving recess -- No Class
Mon Nov 29
Wed Dec 01

Checkpoint 6: Dynamic Programming

  • Dynamic Programming Properties
  • The Knapsack Problem
  • The Bellman-Ford Algorithm
  • The Floyd-Warshall Algorithm
  • Assignment 6
Mon Dec 06
Wed Dec 08
Thu Dec 09
Wed Dec 15

Checkpoint 7: Complexity and Reductions

2:00 - 5:00 p.m.

  • Complexity Classifications
  • Reductions
  • Approximation Algorithms (removed)

Modules

Module 1: Introduction

In this first module we will focus on the language of algorithms and how we will conduct proofs and time complexity analysis.

Module 2: Divide-and-Conquer Algorithms

Next we will discuss algorithms that work by repeatedly “simplifying” the problem and combining solutions to simplified problems.

Module 3: Randomized Algorithms

We will transition from divide-and-conquer algorithms into algorithms that leverage randomness to have provably “good” average performance.

Module 4: Graph Theory

Our next module will cover graph theory. These algorithms and data structures have a surprisingly large number of practical applications.

Module 5: Advanced Data Structures

Related to graphs, we will next discuss binary trees, which are typically an ordered data structure. After BSTs we will discuss one of the most widely used data structures: hash tables. When in doubt, use an array or a hash table.

Module 6: Greedy Algorithms

We’ll wrap up the course discussing two types of algorithm design paradigms. First, we’ll discuss greedy algorithms, which focus on repeatedly making simple decisions and never going back to look for better results.

Module 7: Dynamic Programming

Contrasted to greedy algorithms, dynamic programming algorithms (effectively) look at many possible solutions by leveraging overlapping subproblems and optimal substructure.

Module 8: Complexity

Finally, we’ll look at some of our known algorithms and classify them in terms of space and time complexity.