CSCI 270: Introduction to Algorithms and the Theory of Computing (Spring 2024)

1. Basic Information

1.1 Course Staff

1.1.1 Instructors

Name E-mail (@usc) Office Office Hours
David Kempe SAL 232 Monday/Wednesday 5:10-6:00pm
Tuesday 1:30-3:30pm
or by appointment

1.1.2 Teaching Assistants

Name E-mail (@usc) Location Office Hours
Curtis Bechtel bechtel Tue 4:00-6:00
Thu 6:00-8:00pm
SAL labs
Fatih Kizilkaya kizilkay Tue 12:00-2:00
Thu 4:00-6:00
SAL labs
Neel Patel neelbpat Tue/Wed/Thu 9:00-10:20 Zoom (temporarily)
A. Grayson York agyork Mon/Wed 2:30-3:30
Tue 10:00-12:00
SAL labs

1.1.3 Course Producers

Course Producers will be staffing a Help Desk in the SAL labs every Monday-Thursday from 10:00-5:00, except during class times. In addition, we will have Help Desk on Fridays from 5:00-7:00pm, and on Sunday from 10:00-12:00 on Zoom.

Name E-mail (@usc)
Rohen Chawla rrchawla
Sammie Fan sxfan
Dutch Hansen jmhansen
David Lee dhlee
Yutong Li yli81711
Eric Liu eliu4913
Airi Phuong Pham phuongp
Aditya Prasad aprasad4
Bruno Segovia segovia
Nathan Sparks nsparks
Jarret Spino spino
Muyang Ye muyangye
Barrett Wang mwang424
Alice Wei alicewei
Wendy Wu wuwendy
Karina Yang karinaya
Daniel Youn younh
Eric Zhong etzhong
Yuxing Zhou yuxingz

1.2 Lectures, Discussion Sections, Textbook, Important Links

1.2.1 Lectures, Discussions

Event Time Location
Lecture M/W 12:30-13:50 MRF 340
Lecture M/W 15:30-16:50 THH 201
Discussion F 10:00-11:50 SGM 101
Discussion F 12:00-13:50 GFS 106
Discussion F 14:00-15:50 THH 202

1.2.2 Quizzes, Exams

Event Time Location
Midterm Exam 1 Friday, February 02, 18:00-19:50 SGM 124 (Last Names starting with A-O)
SLH 200 (Last Names starting with P-Z)
Midterm Exam 2 Friday, March 08, 18:00-19:50 SGM 124 (Last Names starting with A-O)
SLH 200 (Last Names starting with P-Z)
Midterm Exam 3 Friday, April 05, 18:00-19:50 SGM 124 (Last Names starting with A-M)
SLH 200 (Last Names starting with N-Z)
Final Exam Wednesday, May 08, 19:00-21:00 SGM 123 (all non-OSAS students)

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

1.2.3 Textbook and other material

The course textbook is Algorithm Design by Jon Kleinberg and Eva Tardos, referred to as KT below. We will lean heavily on the textbook, though we will occasionally assign additional reading which will be linked here.

Notes written during class will be posted on the Piazza page. They are not really intended as study material or a complete summary, but just as a reminder. A more comprehensive set of notes, written by a student in the Fall 2022 iteration, is available.

1.2.4 Important Links


2. Course Schedule by Week


3. Prerequisites

You should be familiar and comfortable with the following:


4. Grading and Homeworks

4.1 Grade percentage overview

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% 79%A
79% 72%A-
72% 65%B+
65% 58%B
58% 51%B-
54.5% 47.5%C+
51% 44%C
47.5% 40.5%C-
40% 33%D
<40% <33% F

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

4.2 Regrades

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:

4.3 Homework Submission and Late Submission

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. Contact the TAs and the professor if you have questions about grading or homework policies.

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.

4.3.1 Late Homework Policy

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.

We stress that late days are meant as an unbureaucratic way for you to give yourself extensions when you have legitimate reasons to submit late. You can also use them as "cushion" if a homework is giving you exceptional trouble or you have a lot going on. However, this does not mean that you are entiteled to 10 "cushion days" in addition to late days for legitimate reasons, such as illness, family emergency, etc. In particular, please do not make the (common) mistake of using up all your late days on the first three homeworks because you underestimated the difficulty, then finding yourself struggling a lot later in the semester.

4.4 Homeworks

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


5. Collaboration and Academic Integrity

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.

5.1 Plagiarism

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:

It does not change anything if you make 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 plagiarizing 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.

5.2 Collaboration on Homeworks

Naturally, the prerequisite quiz, midterm exams, and final exam 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:

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.

5.3 Consulting outside sources

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), any kind of Chatbot, 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.

5.4 USC's text on Academic Conduct

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


6. Additional Course Syllabus Items

6.1 Course Description

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.

6.2 Non-Discrimination

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.

6.3 Support Systems

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.

6.4 Emergency Preparedness / Course Continuity in a Crisis

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.