Overview

CSCI 140 is an introduction to algorithm design and analysis techniques. The course covers basic techniques used to analyze algorithms, basic techniques used in designing algorithms, and important classical algorithms. The goal is to learn how to apply all of the above to designing solutions to new problems (a skill that you will practice throughout the semester). Grades will be based on assignments, exams, and participation. The prerequisite for this class is CS 62.

Resources

Instructor: Dr. Dave
e-mail: David.last_name@pomona.edu
office hours: Edmunds 224

Mon
2:30 - 4pm

Wed
9 - 10:30am

Fri
9 - 10am

  and by appointment

Mentor hours:

Wed
7 - 9pm (Saatvik)

Thu
5:30 - 10:30pm (Max: 5:30-6:30, George: 6:30-8:30pm, Eshaan: 8-9pm, Michele (8:30-10:30pm)

Fri
9:30 - 10:30am (Sophia)

Fri
1 - 5pm (Sam: 1-4pm, Saatvik: 3-5pm)

Fri
5:30 - 7:30pm (Abe)

Sun
9am - 12 (Max: 9-10am, Sophia: 10am-12)

Sun
4 - 6pm (Abe)

Sun
7 - 9pm (Eshaan)

Assignment submission: Gradescope
Discussion/questions: Slack

Textbook: Introduction to Algorithms, 3rd/4th Edition by Cormen, Leiserson, Rivest, and Stein (CLRS). We will have some copies in the Edmunds lab library.

If you need accommodations please contact the Disability Coordinator on your home campus. The process for Pomona students is available here.

Logistics

The basic flow each week will be as follows:

Each week there will be a short, group assignment. You must attend one of the group sessions on Thursday/Friday and complete the group assignment with 2-4 of the attendees at that session. These group assignments will be low-stakes and are mostly designed to get you warmed up for the regular assignment that week.

In addition, there will be a weekly assignment. The assignments will mostly be done and submitted in pairs. For the first four assignments you will need to work with a different partner on each assignment. After that, you can choose whoever you would like to work with, but must still work with a partner. You may discuss the assignment problems with anyone else currently taking cs140 (or with the TAs or myself), but each pair must write up their own solution.

You may submit up to two assignments 24 hours late.

Finally there will be two midterms.

The breakdown of grades will be as follows:

Calendar

This is a high-level outline of the planned syllabus. Note that the calendar is subject to change. Unless otherwise specified, the readings are in CLRS.

Day Date Topic Reading Assignments
T 1/16 intro/math basics (ppt), pseudocode example (.tex) Ch 1, 2
Th 1/18 big-O (ppt)) Ch 3 Assign 0 (.tex) due 1/21 at 10pm
T 1/23 recurrences (ppt)
Th 1/25 more recurrences (ppt) Ch 7 Group 1 due 1/26 at 10pm
Assign 1 (.tex) due 1/28 at 10pm
T 1/30 sorting concluded (ppt) Ch 8 (optional)
Th 2/1 order statistics, data structures review (ppt) Ch 9, 10 Group 2 due 2/2 at 10pm
Assign 2 (.tex) due 2/4 at 10pm
test files
T 2/6 binary search trees (ppt) Ch 12, 13
Th 2/8 amortized analysis (ppt) Ch 16 Group 3 due 2/9 at 10pm
Assign 3 (.tex) due 2/11 at 10pm
T 2/13 heaps, binomial heaps (ppt) Ch 6
Th 2/15 dynamic programming (ppt) Ch 14 Group 4 (get from mentor) due 2/16 at 10pm
Assign 4 (.tex) due 2/18 at 10pm
T 2/20 more dynamic programming (ppt)
Th 2/22 even more dynamic programming (ppt) Group 5 due 2/23 at 10pm
Assign 5 (.tex) due 2/25 at 10pm11:59pm
T 2/27 review sample midterm (solutions)
Th 2/29 midterm 1 Group 6 due 3/1 at 10pm
Assign 6 (.tex) due 3/8 at 5pm
T 3/5 greedy algorithms (ppt) Ch 15
Th 3/7 more greedy algorithms (ppt) No group assignment
T 3/12 Spring Break
Th 3/14 Spring Break
T 3/19 hashtables (ppt) - recording - handout Ch 10
Th 3/21 graph basics (ppt) Ch 20 Group 7 due 3/22 at 10pm
Assign 7 (.tex) due 3/24 at 11:59pm
T 3/26 more graphs (ppt) Ch 21
Th 3/28 shortest paths (ppt) Ch 22 Group 8 due 3/29 at 10pm
Assign 8 (.tex) due 3/31 at 11:59pm
T 4/2 all-pairs shortest paths (ppt) Ch 23
Th 4/4 network flow (ppt) Ch 24 Group 9 due 4/5 at 10pm
Assign 9 (.tex) due 4/7 at 11:59pm
T 4/9 network flow applications (ppt) Ch 25
Th 4/11 misc Group 10 due 4/12 at 10pm
Assign 10 (.tex) due 4/22 at 11:59pm
T 4/16 midterm 2 sample problems (solutions)
Th 4/18 NP complete (ppt) Ch 34 Group 10b due 4/19 at 10pm
T 4/23 NP complete reductions (ppt)
example reduction
Th 4/25 linear programming Ch 29 Group 11 due 4/26 at 10pm
Assign 11 (.tex) due 4/28 at 11:59pm
T 4/30 review (ppt) - overview of topics
The take-home final exam will need to be completed by the end of the day on Wednesday, 5/8.