**Most recent announcement posted:
04/29/2022.**

Name | E-mail (@usc) | Office | Office Hours |
---|---|---|---|

David Kempe | MW 5:10-6:00, T 4:00-5:00, Th 3:00-4:00 | ||

Jiapeng Zhang | jiapengz | F 10:00-12:00 |

Please e-mail your instructor directly to arrange in-person office hours. For now, Zoom office hours are the default.

Name | E-mail (@usc) | Office | Office Hours |
---|---|---|---|

Calvin Leng | cleng | Zoom (for now) | TBD |

Chandra Sekhar Mukherjee | chandrasekhar.mukherjee | Zoom (for now) | TBD |

Serban Stan | sstan | Zoom (for now) | TBD |

Name | E-mail (@usc) | Office | Office Hours |
---|---|---|---|

Natalie Abreu | nrabreu | Zoom (for now) | TBD |

Sammie Fan | sxfan | Zoom (for now) | TBD |

Adam Hamden | ahamden | Zoom (for now) | TBD |

Flora Jia | florajia | Zoom (for now) | TBD |

Aditya Prasad | aprasad4 | Zoom (for now) | TBD |

Alex Prieger | prieger | Zoom (for now) | TBD |

Amartya Ranganathan | amartyrr | Zoom (for now) | TBD |

Anthony Sauer | sauera | Zoom (for now) | TBD |

Cole Schroeder | coleschr | Zoom (for now) | TBD |

Kameron Shahabi | kyshahab | Zoom (for now) | TBD |

Aviv Shai | avivshai | Zoom (for now) | TBD |

Lucy Shi | lucys | Zoom (for now) | TBD |

Jarrett Spino | spino | Zoom (for now) | TBD |

Yibo Wen | yibowen | Zoom (for now) | TBD |

Albert Yan | albertzy | Zoom (for now) | TBD |

Tianyi (Lorena) Yan | tianyiy | Zoom (for now) | TBD |

Yuxing (Tom) Zhou | yuxingz | Zoom (for now) | TBD |

Changyu Zhu | changyuz | Zoom (for now) | TBD |

Event | Time | Location |
---|---|---|

Lecture (Kempe) | M/W 12:30-1:50 | THH 202 |

Lecture (Kempe) | M/W 3:30-4:50 | MHP 101 |

Lecture (Zhang) | Tue/Th 6:00-7:20 | MRF 340 |

Discussion | F 10:00-11:50 | SGM 101 |

Discussion | F 12:00-1:50 | GFS 106 |

Discussion | F 2:00-3:50 | THH 202 |

Event | Time | Location |
---|---|---|

Prerequisite Quiz | Friday, January 14, 7:00-8:00pm | online |

Midterm Exam | Friday, March 4, 7:00-8:50pm | THH 101 (Last names A-K) THH 102 (Last names L-Z) |

Final Exam | Wednesday, May 11, 7:00-9:00pm | THH 101 (Last names A-Q) THH 202 (Last names R-Z) |

Apart from these scheduled exams, the quiz section will not be used.

**04/29/2022:**: Location information has been added for the final exam.**04/23/2022:**The tenth homework assignment has been posted on Piazza. It is due by 11:00pm on Wednesday, 05/04. It cannot be submitted more than two days late.**04/13/2022:**The ninth homework assignment has been posted on Piazza. It is due by 11:00pm on Sunday, 04/24.**04/06/2022:**The eigth homework assignment has been posted on Piazza. It is due by 11:00pm on Wednesday, 04/13.**03/26/2022:**The seventh homework assignment has been posted on Piazza. It is due by 11:00pm on Sunday, 04/03.**03/19/2022:**The sixth homework assignment has been posted on Piazza. It is due by 11:00pm on Sunday, 03/27.**03/06/2022:**The fifth homework assignment has been posted on Piazza. It is due by 11:00pm on Sunday, 03/20.**03/06/2022:**The midterm scores are posted on Blackboard. We are trying to post the actual graded exams on GradeScope soon.**02/12/2022:**The fourth homework assignment has been posted on Piazza. It is due by 11:00pm on Sunday, 02/20.**02/05/2022:**There was a mistake in Question 2 on Homework 3. We updated the problem set on Piazza. Please download the latest version before solving it.**02/04/2022:**The third homework assignment has been posted on Piazza. It is due by 11:00pm on Sunday, 02/13.**02/04/2022:**The deadline for Homework 2 has been extended to 11:00pm today (Friday, 02/04).**02/02/2022:**Reminder: starting next week (02/07), lectures will be in person, in the locations posted above and on the USC course calendar.**02/02/2022:**We have posted the grading scale.**02/02/2022:**The second homework assignment has been posted on Piazza. It is due by 5:00pm on Friday, 02/04.**01/21/2022:**Despite USC returning to in-person instruction, we have made the call that we will keep lectures Zoom-only for the next two weeks, to keep everyone safe. We will announce whether the same will hold for discussion sections, and which (if any) of the office hours will be in person.**01/20/2022:**The first homework assignment has been posted on Piazza. It is due by 5:00pm on Friday, 01/28.**01/17/2022:**Due to MLK day, there will be no lectures today (01/17). To keep classes in synch, there will also be no lecture tomorrow (01/18). Lectures will resume as normal (on Zoom) on 01/19.**01/09/2022:**At least the first week of classes will be entirely on Zoom. The same applies to office hours, discussions, etc., of course. We (and USC) will keep you posted as further decisions are made.**01/04/2022:**Final exam date and course staff information have been added.**11/16/2021:**The course website is up.

- Week 1: Introduction, Stable Matching (2 lectures)
- Required Reading: KT chapter 1
- Review Reading: KT chapters 2 and 3
- Recommended Reading: Shaddin's note on optimizing and analyzing runtime, using the Gale-Shapley algorithm as an example.
- Optional reference: Chapter 10.4 from the Algorithmic Game Theory book (To freely view the contents, you'd have to go through the USC library proxy).
- Additional optional references: This paper by Irving et al on optimizing over stable matchings (no paywall if accessing on campus, or online through USC library proxy), and the book by Gusfield and Irving on algorithmic questions in stable matching (available online through USC library proxy).

- Weeks 2-4: Greedy Algorithms (4 lectures)
- Required Reading: KT chapter 4

- Weeks 4-6: Divide and Conquer (4 lectures)
- Required Reading: KT chapter 5

- Weeks 6-9: Dynamic Programming (5 lectures)
- Required Reading: KT chapter 6

- Weeks 9-11: Max Flow / Min cut (4 lectures)
- Required Reading: KT chapter 7
- Additional reference: Non-terminating example for the Ford-Fulkerson algorithm with real-valued capacities can be found in the Wikipedia article.
- Additional reference: Bobby Kleinberg's notes on the Edmonds-Karp algorithm and its analysis.
- Additional reference: David Kempe's notes on the Edmonds-Karp algorithm.

- Weeks 11-13: NP-Completeness (5 lectures)
- Required Reading: KT chapter 8
- Additional Reference: Compendium of NP optimization problems
- Additional Reference: Garey and Johnson
- Additional reference: Paper on the possible worlds of complexity theory

- Weeks 14-15: Computability theory (4 lectures)
- Required Reading: Chapter 1 of Arora/Barak
- Recommended Reading:
- Lecture notes by Jeff Erikson: Turing Machines, Undecidability, Universal Models of Computation
- Wikipedia has a nice summary of Cantor's diagonal argument.
- David Kempe's brief notes on recursion theory.

- Additional references: Turing's original 1936 paper
- Fun reading: The graphic novel Logicomix for a fictionalized account of the development of formal logic and the foundations of computation

- CSCI 170
- CSCI 104L

These prerequisites will be tested in a quiz in Week 1. More specifically, you should be familiar and comfortable with the following:

- Writing rigorous proofs, including using techniques such as induction and contradiction.
- Big-O notation (the meanings of O, Ω, Θ, their differences and how to apply them).
- Basic set, function, sum, and product notation, and how to use/manipulate them.
- Basics about relations and their properties.
- Some basic series, specifically, arithmetic, geometric, and Harmonic series.
- Runtime analysis, and what it means to prove upper and lower bounds on the runtime of an algorithm.
- Basic combinatorics: counting, pairs, permutations, subsets, inclusion/exclusion, Pigeon Hole Principle.
- Basic probability: probability, events, independence, expectations, conditioning, Birthday Paradox.
- Data Structures and the opertions they support, as well as the different implementations and their running times for the operations.
- In particular, you should know stacks, queues, heaps (priority queues), and maps. For maps, you should be comfortable with implementations as balanced search trees and hashtables, and understand their relative advantages.
- Breadth-First Search, Depth-First Search, Dijkstra's Algorithm
- The basic sorting algorithms: Insertion/Selection/Bubble Sort as well as Quick Sort, Merge Sort, and Heap Sort.
**Importantly, the quiz will also contain a question on the CSCI 270 academic integrity policy.**

If you want to check how well you've reviewed the material, a sample/practice quiz has been posted. We recommend that you only take the sample quiz at a point when you feel you have already reviewed the material well, so it serves as a useful calibration.

- Homework (40%): There will be homework assignments roughly every week (a total of about 11-12). This is a theory class, and therefore homeworks will be proof-based and will not involve any coding. The homeworks are intended to be challenging, with individual problems requiring possibly several days of thought, so plan ahead. We expect the
**average**student to spend about 10-15 hours on a homework - if this class is difficult for you, it might take you longer. - Midterm Exam (24%): The midterm exam will be held on Friday, March 04, during the scheduled quiz section from 7:00pm to 8:50pm. It will cover the class material up to that point.
- Final Exam (34%): The final exam will be held on Wednesday, May 11, from 7:00-9:00pm. It will be cumulative (i.e., cover the material of the entire semester), though more focus will be on the second half of the semester.
- Prerequisite Quiz (2%): The prerequisite quiz will be held on Friday, January 14 - from 7:00pm until about 8:00pm. It will cover material you should be very comfortable with from CSCI 104 and CSCI 170. See above for more detail on the material.

Based on the weighted percentage, the following table tells you the final grade. If our exams are more difficult than anticipated, we might make the scale slightly more lenient, but it will definitely not become more strict.

p | Grade |

86% | A |

79% | A- |

72% | B+ |

65% | B |

58% | B- |

54.5% | C+ |

51% | C |

47.5% | C- |

40% | D |

<40% | F |

Notice that we do not give D+ or D- grades.

If you feel that you were graded unfairly (too high or too low) on an exam or homework, you are welcome to request a regrade. Here are the relevant policies:

- Regrade requests must be submitted in writing to one of the TAs. For exams, they must be submitted in writing to one of the instructors.
- Except on the final exam, you must wait for at least 48 hours after the homework/exam is returned before you can ask for a regrade. (This is to give you time to think through the grading and make sure you still feel that the grading was wrong.)
- You have at most two weeks after the return of the homework/exam to submit your regrade request. If you have an insanely busy 2 weeks but know you want a regrade, you can send a brief "Heads up. I will submit a detailed regrade request on such-and-such date" e-mail instead. (This is to prevent desperate attempts to submit all homeworks for regrades at the end of the semester if you just need 2 more points for a higher grade.)
- When you ask for a regrade, we will regrade your entire homework/exam, not just the question which you feel was misgraded. This is to ensure fairness overall.

**We will use Gradescope for homework submission and grading. Your Gradescope accounts will be set up by us, and you will receive email notification.**

A guide for homework submission is available here.

If you have any questions about Gradescope and homework submission, please ask on Piazza or contact TBD. Contact the TAs and the professors if you have questions about grading or homework.

All homework submissions must be PDF files. Starting on Homework 3, the solutions must be typed up. Homeworks 1 and 2 can be submitted as photographed/scanned handwritten solutions, and the graders will make a reasonable attempt to read them. If as a result of the handwriting quality or the capturing, the solution is illegible, it may result in lost points.

For typing up solutions, we highly recommend the (free) LaTeX document processing language. It is a flexible markup language you can use with any editor, and the de facto standard for most CS and math papers. The output looks **much** nicer than MS-Word or others. You may really enjoy using this opportunity to learn it.

You will be allowed 10 total late days for homework, to be used in integer amounts and distributed over homeworks as you see fit. A late day is 24 hours from the original homework deadline, or any part thereof. Additional late submissions will only be considered in exceptional circumstances. In order to allow us to distribute sample solutions in a timely manner, no homework can be submitted more than 5 days late; in some cases, we may further constrain late submissions (e.g., close to an exam).

There are no special procedures to use a late day. We will make the final deadline 5 days after the regular deadline. Notice that Gradescope does not keep track of your late days. We will not accept late submissions that exceed your total late day limit without explicit prior approval.

All homeworks (and subsequently HW solutions) will be posted on Piazza once they are assigned.

We will expect the utmost in academic integrity from each of you, and we will trust you to abide by the commensense norms of academic integrity (see the statement on academic integrity below). A more detailed discussion of what is and is not appropriate in this class (as well as some general advice on plagiarism) is given below. Most importantly, if you have any doubts as to whether a certain practice is considered a violation of academic integrity, it is your responsibility to preemptively ask the instructors or graduate TAs (not the CPs) before engaging in the practice.

While we will not go out of our way to identify violations of academic integrity, those who are found to be in violation will be referred to the office of judicial affairs without exception. Furthermore, consistent with USC's recommended policy, we will suggest to SJACS a grade of F in the class for any confirmed violation. While this may be stricter than some introductory classes, it reflects the fact that by now, we expect you to be more mature, and have gotten the "high-school mindset" out of your system.

Aside from a handful of cases that are obviously cheating (e.g., consulting a textbook or other source in a closed-book exam, using a computer or calculator when you were not allowed to), most cases of cheating involve what is called "plagiarism" which is defined as "passing someone else's work off as your own without attribution" Plagiarim can thus take many forms:

- Copying solutions from a classmate.
- Copying solutions from a friend who took the class earlier.
- Copying solutions from a manual you found online, or some other textbook which happens to have the solution.
- Paying someone to do the homework for you.

It does not change anything if you make small changes while/before copying a solution, if the gist is still the same. A solution does not have to be copied verbatim to be considered plagiarism.

Notice from the definition that there is a surefire way to avoid committing plagiarism: attribute all sources you use. Even if you copied a solution word for word from an online source, you are not committing plagiarism if you clearly and visibly write on top "I copied this solution from the following source: ... This is not my own solution." In this scenario, you will likely receive a 0 on the question (since you did not actually solve it), but you did not commit plagiarism.

Zooming out a bit: in any paper or assignment you write, any project report in your professional life, or even a presentation, it is a great idea to attribute all ideas and text you took from somewhere else. Not only does it avoid plagiarising in an academic environment, but your colleagues will also really appreciate you for giving them credit for the slides/text/ideas you borrowed from them if you make it clear that it was theirs.

Zooming back in: on your homeworks, you should err on the side of safety, and cite all sources. That is, list all websites where you looked up ideas (even if you didn't copy them verbatim), and any classmates or other people that you had substantial discussions with. That way, we (the course staff) can make the call how much you added beyond your sources, but in any case, you will not be accused of plagiarizing.

Naturally, the prerequisite quiz, midterm and final will be individual work. However, since much of CS (and math) work is often collaborative, we allow collaboration and discussion among students for the homework. The focus should be on discussing high-level ideas, whereas you should not spell out all details in your collaborative work. More specifically, here are concrete guidelines for your collaborations:

- You must acknowledge everyone who you collaborated with. If you worked with different people on different problems, then list them on the specific problems. In the spirit of the preceding section, you should err on the side of over-reporting, and list people even if you just briefly chatted and exchanged high-level ideas. Feel free to specify how you collaborated, e.g., "I gave Edsger Dijkstra a little hint about the loop invariant." or "Donald Knuth suggested to use Dynamic Programming on Question 3."
- Your discussions should focus on high-level ideas. You should stop your group collaboration well short of writing out the details of an algorithm or proof.
- If you meet in a group to work on the homework, your group must include no more than 5 individuals.
- You are not allowed to take any written material with you out of the meeting, including screenshots or photographs. In other words, reconstruct the key ideas by yourself after you've worked them out with your classmates.
- You must wait at least 30 minutes after any discussion with fellow students, and then
*write up your solutions independently*. If your discussion was accidentally too detailed, then you should significantly extend this 30-minute interval, and avoid thinking about CSCI 270 material in between. (If you want to see the rationale for this rule, look at a homework solution you wrote, and try to memorize it. Wait for a day, and then try to write it again as closely as possible. If you compare the solutions, you will likely see that they are extremely different.)

Of course, asking the instructors, teaching assistants, or course producers for hints is always ok. If we feel that a hint would reveal too much, we will simply not answer your questions.

You may not discuss problems with (or seek solutions or hints from) anyone outside the class, be it strangers on the Internet (e.g., in discussion forums or homework-for-hire websites), or a friend who took the class previously.

You also must not consult solution manuals or google for solutions to similar problems. Both are absolutely considered cheating. That being said, you are allowed (and encouraged) to consult general sources (such as Wikipedia, books, or course notes) pertaining to course content in order to broaden your perspective, so long as you do not specifically seek out material related to a particular homework problem. As discussed above, you should cite all such materials that you consulted.

Plagiarism - passing someone else's ideas as your own, either verbatim
or recast in your own words - is a serious academic offense with serious
consequences. Please familiarize yourself with the discussion of
plagiarism in *SCampus* in Section 11, *Behavior Violating
University Standards*
https://scampus.usc.edu/1100-behavior-violating-university-standards-and-appropriate-sanctions/.
Other forms of academic dishonesty are equally unacceptable. See
additional information in SCampus and university policies on scientific
misconduct, http://policy.usc.edu/scientific-misconduct/.

The course covers the fundamentals of algorithm design and the theory of computing. Much of the work of a computer scientist is problem solving using computational artifacts (such as modern computers), and problem solving involves describing step-by-step procedures that can be followed by machines. These are called algorithms. Many fundamental techniques for algorithm design, as well as specific algorithms themselves, recur throughout all areas of computer science, and computer scientists must be able to apply design and analysis techniques to devise efficient algorithms and compare them.

The flipside of algorithm design is knowing the limits of algorithm design: when are problems so intractable that they either cannot be solved at all, or can --- to the current state of scientific knowledge --- only be solved by very inefficient algorithms? Such knowledge is necessary to avoid searching for solutions to problems that simply cannot be solved.

The course CSCI 270 provides an introduction to both of these complementary pieces: it covers greedy algorithms, Divide&Conquer algorithms, Dynamic Programming and their corresponding analysis techniques. It also contains an introduction to the theory of NP-completeness and computability theory. At the discretion of the instructor, it will contain a discussion of a subset of the following topics: algorithms for flows and cuts, linear programming, the role of randomization in computing, approximation algorithms, number-theory based cryptographic algorithms, and non-standard models of computing.

Discrimination, sexual assault, and harassment are not tolerated by the
university. You are encouraged to report any incidents to the *Office
of Equity and Diversity* http://equity.usc.edu/ or to the
*Department of Public Safety* http://capsnet.usc.edu/department/department-public-safety/online-forms/contact-us.
This is important for the safety whole USC community. Another member of
the university community - such as a friend, classmate, advisor, or
faculty member - can help initiate the report, or can initiate the report
on behalf of another person. *The Center for Women and Men* http://www.usc.edu/student-affairs/cwm/
provides 24/7 confidential support, and the sexual assault resource center
webpage sarc@usc.edu describes reporting
options and other resources.

A number of USC's schools provide support for students who need
help with scholarly writing. Check with your advisor or program staff to
find out more. Students whose primary language is not English should check
with the *American Language Institute*
http://dornsife.usc.edu/ali, which
sponsors courses and workshops specifically for international graduate
students. *The Office of Disability Services and Programs*
http://sait.usc.edu/academicsupport/centerprograms/dsp/home_index.html
provides certification for students with disabilities and helps arrange
the relevant accommodations. If an officially declared emergency makes
travel to campus infeasible, *USC Emergency Information*
http://emergency.usc.edu/ will
provide safety and other updates, including ways in which instruction will
be continued by means of blackboard, teleconferencing, and other
technology.

In case of a declared emergency if travel to campus is not feasible, USC executive leadership will announce an electronic way for instructors to teach students in their residence halls or homes using a combination of Blackboard, teleconferencing, and other technologies.