CSCI140 PO-01 Algorithms

Spring 2021

Monday and Wednesday

12:45 PM to 2:00 PM Pacific Time

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

Teaching Assistants

Naomi Amuzie
Alex Franklin
Camilla Guo
Matthew Ivler
Naomi Amuzie
Alex Franklin
Camilla Guo
Matthew Ivler

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 treating online mentor sessions in the same way that you would treat in-person mentor sessions. Just show up 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.

I must apologize, as I am new to the 7Cs almost all of my information is specific to Pomona College students. If you are looking for a similar resource at a different college, please reach out to me and I will help you find it. This document is a nice starting point for help. It includes resources for:

Ask yourself the following questions and reach out to me if you need help filling in any gaps:

  1. Do you have reliable Internet at home?
  2. Do you have a computer at home?
  3. Does your computer have a camera?
  4. Do you have a cell phone with a camera?

I’d also like to know if you have any trouble with:

  1. Do you have a quiet, private place you can comfortably take part in video conferences?
  2. In what time zone do you expect you will complete our course?
  3. Do you have any accessibility requests for me regarding online teaching?

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.

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.

Checkpoints

For better or worse, we will have synchronous 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 (worth 85% of your quiz grade).
  2. You will retake the quiz in groups (worth 15% of your quiz grade).

Your grade cannot go down because of the group portion of the exam. Here is how I will calculate quiz grades:

max[Scoreindividual, 0.85 · Scoreindividual + 0.15 · Scoregroup],

where Scoreindividual and Scoregroup are your individual and group grades, respectively. Basically, if your group does better, then your grade improves.

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

To submit your checkpoints, you will potentially need to take pictures of your handwritten answers and upload them to gradescope.

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:

Assignments

Assignments will be submitted to gradescope. You may work on assignments individually or with a partner of your choice (I would normally randomized partners, so let me know if that interests you). 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.

Working Together

I encourage you to work in partners for your assignments. 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.

Teaching Assistants

TAs have the following duties:

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

Here are the highlights of the grading policy:

Clearly, the biggest oddity in this scheme is that your assignments are graded pass/no-pass and that they have relatively little impact on your final grade (particularly when compared to the amount of time they take). I am doing this for several reasons:

  1. it should provide more flexibility and less stress on completing assignments while we all work in environments not necessarily well suited to study;
  2. it gives you a chance to receive feedback and adjust your expectation without affecting your final grade (it gives you space to learn);
  3. it should eliminate any compulsion to violate the department’s Academic Honesty Policy;
  4. it will make it easier to provide critical feedback without worrying about your grade (particularly for TAs that might be your acquaintances); and
  5. it eliminates assigning much credit to work that you can optionally do with a partner.

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). Unfortunately, it also means that you cannot use homework to bolster your grades. These ideas, in part, come from Grading for Equity (a nice summary here).

You will submit assignments to gradescope, but grades should also be available through Sakai.

Letter Grade Scale

I will be using a slightly modified “+/- grading scale”. See the following scale (n.b., I remove the “A-” grade):

PercentLetter
≥ 90%A
87%B+
83%B
80%B-
77%C+
73%C
70%C-
67%D+
63%D
60%D-
< 60%F

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’d like to encourage you to contact the Student Disability Resource Center (SDRC) as soon as possible so we can make this semester go well from the beginning.

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

I encourage you to study and work on assignments with your peers (unless specified otherwise in the assignment description). You will complete individual checkpoints without any assistance–you should not use the Internet, ask questions on Slack, or use textbooks or course notes.

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. If you need to leave class early for any reason, please let me know before class begins.

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, checkpoints cannot be completed after the class period in which they are scheduled.

Recordings

I will record Zoom lectures (I will record my screen), so you will not need to do so.

Calendar

January
Sun
Mon
Tue
Wed
Thu
Fri
Sat
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
26
28
29
30
31
1
2
3
4
5
6
February
Sun
Mon
Tue
Wed
Thu
Fri
Sat
31
2
5
6
7
9
11
12
13
14
16
19
20
21
23
25
26
27
28
1
2
3
4
5
6
March
Sun
Mon
Tue
Wed
Thu
Fri
Sat
28
2
5
6
7
9
11
12
13
14
16
18
19
20
21
23
26
27
28
30
1
2
3
April
Sun
Mon
Tue
Wed
Thu
Fri
Sat
28
29
30
31
1
2
3
4
6
9
10
11
13
15
16
17
18
20
23
24
25
27
29
30
1
May
Sun
Mon
Tue
Wed
Thu
Fri
Sat
25
26
27
28
29
30
1
2
4
7
8
9
10
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5

Schedule

If the schedule below doesn’t look up-to-date, you might need to reload the page while overriding cache.
Here are all PDFs from fall 2020

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 Jan 25
Wed Jan 27
Mon Feb 01
Wed Feb 03
Thu Feb 04
Fri Feb 05
  • Last day to add a course or change board plan; last day for course fee refunds.
Mon Feb 08
Wed Feb 10

Checkpoint 1: Running Time and Invariants

  • Loop Invariants
  • Total Running Time
  • Asymptotic Running Time Proofs
Mon Feb 15
Wed Feb 17
Thu Feb 18
Mon Feb 22
Wed Feb 24

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 Mar 01
Wed Mar 03
Thu Mar 04
Mon Mar 08Spring Recess
Wed Mar 10Spring Recess
Mon Mar 15
Wed Mar 17

Checkpoint 3: Graph Theory

  • Connectivity
  • BFS and DFS
  • Topological Orderings
  • Graph Representations
  • Kosaraju's Algorithm (and SCCs)
  • Dijkstra's Algorithm (and SSSP)
Mon Mar 22
Wed Mar 24
Thu Mar 25
Mon Mar 29
Wed Mar 31

Checkpoint 4: Data Structures and Memory

  • Heaps
  • Binary Search Trees
  • Red-Black Trees
  • Hash Tables
  • Universal Hashing
  • Data Locality
Mon Apr 05
Wed Apr 07
Thu Apr 08
Mon Apr 12
Wed Apr 14

Checkpoint 5: Greedy Algorithms

  • Greedy scheduling
  • Minimum spanning trees (Prim's and Kruskal's)
  • Huffman Codes
  • Max-Spacing K-Clustering
  • Exchange Arguments
Mon Apr 19
Wed Apr 21
Thu Apr 22
Mon Apr 26
  • Sequence Alignment (Optional)
    • slides
    • VidGrid
    • Sequence alignment will not appear on the checkpoint.
  • Gerrymandering
Wed Apr 28

Checkpoint 6: Dynamic Programming

  • Dynamic Programming Properties
  • The Knapsack Problem
  • The Bellman-Ford Algorithm
  • The Floyd-Warshall Algorithm
  • Assignment 6
Mon May 03
Wed May 05
Thu May 06
Tue May 11

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.