CSE 101: Design and Analysis of Algorithms

Fall 2018

Instructor: Ben Ochoa
Email: bochoa at
Office hours: Tu 6:30 PM-8:30 PM, EBU3B 3234, and at other times by appointment

TA: Yiyuan (Sparrow) Ma
Email: yim096 at
Office hours: W 8:50 AM-9:50 AM and F 8:50 AM-9:50 AM, EBU3B B215

TA: Harsh Lal
Email: hlal at
Office hours: Tu 10:00 AM-11:00 AM and Th 10:00 AM-11:00 AM, EBU3B B215

TA: Waquar Ahmad
Email: w2ahmad at
Office hours: M 1:30 PM-2:30 PM and F 12:00 noon-1:00 PM, EBU3B B215

TA: Sameeksha Khillan
Email: skhillan at
Office hours: W 3:30 PM-4:30 PM, EBU3B B275

Tutor: Toan Bui
Email: tkb001 at
Office hours: W 6:00 PM-7:00 PM, EBU3B B275, and Th 11:00 AM-1:00 PM, EBU3B B215

Tutor: Eric Liu
Email: esl036 at
Office hours: M 8:00 AM-10:00 AM, EBU3B B260A, and Tu 9:00 AM-10:00 AM, EBU3B B270A.

Note: when emailing the instructor, TAs, or tutors with questions about the class, please put "CSE 101" in the subject line.

Lecture: TuTh 5:00 PM-6:20 PM, SOLIS 107

F 2:00 PM-2:50 PM, CENTR 222 (section ID: 947829)
F 3:00 PM-3:50 PM, CENTR 222 (section ID: 947830)
F 4:00 PM-4:50 PM, CENTR 222 (section ID: 947831)
Class discussion: Piazza

The course covers the design and analysis of efficient algorithms with emphasis on non-numerical algorithms such as sorting, searching, pattern matching, and graph and network algorithms. This includes measuring the time and storage complexity of algorithms. NP-completeness will also be discussed.

Prerequisites: Advanced data structures

Homework assignments: There will be seven homework assignments. The one with the lowest grade will be dropped. Assignments must be prepared using LaTeX, Word, or another software application that typesets or formats mathematical expressions. It is allowable for figures to be hand-drawn, but any other hand-written portion of a submitted assignment reduces the maximum credit on that portion to 80%.

Quizzes: There will be three 40 minute in-class quizzes, each contributing to 10% of your final grade. See below for an alternative that drops the your lowest quiz and increases the weight of your final exam.

Most problems will be mathematical or theoretical in nature, involving designing and analyzing an algorithm. Although some assignments will require students to design and analyze pseudo-code programs, implementation is not required to complete these assignments. Grading of all problems will be both on the basis of correctness and on logical consistency and completeness, i.e., "mathematical style". It is your obligation to provide a compelling argument that forces the reader to believe the result, not just notes from which an argument could be constructed. In particular, the correct formulas or pseudo-code are not a complete solution by themselves; their significance and the logic of their application need to be explained.

When giving an algorithm, the following three items should always be included, unless the problem explicitly says not to.

Descriptions need to be unambiguous. You should be able to give the description to any other student and have them easily implement a correct program from it. Proofs need to be completely clear, completely unambiguous, and logically compelling, but can be in high-level mathematical English. Time analysis needs to give a true upper bound 2 on the time taken by the algorithm, in big O notation. You need not argue that the bound is tight, but your grade will be partially based on how fast you show your algorithm is, not just how fast it really is. So if your algorithm takes time O(n^2) and you claim it is O(n^3), this is also correct, but you will be graded on efficiency as if your algorithm really took Ω(n^3) time. Some relaxation of this rule will apply to problems of a computational nature, where you are merely expected to present a solution and give some informal justification. Such problems will be designated by a key phrase, e.g., "Find a solution and justify your answer."

Collaboration Policy: You are encouraged to collaborate. As such, homework assignments will be completed in groups of size 1-4. However, collaboration or copying on exams of any kind is not allowed.

Academic Integrity Policy: Integrity of scholarship is essential for an academic community. The University expects that both faculty and students will honor this principle and in so doing protect the validity of University intellectual work. For students, this means that all academic work will be done by the individual or group to whom it is assigned, without unauthorized aid of any kind.

You should not attempt to search for homework solutions online or in sources outside of the course text. If you accidentally stumble upon a homework solution in an outside source you must cite it in your homework solution. If your solution proves to be too similar to the cited one, you may lose credit on the problem; however, failure to cite the other solution will be treated as an academic integrity violation.

If the work you submit is determined to be other than your own or your group, you will be reported to the Academic Integrity Office for violating UC San Diego's Policy on Integrity of Scholarship. In accordance with the CSE department academic integrity guidelines, students found committing an academic integrity violation will receive an F in the course.

Grading: There will be seven homework assignments (drop lowest one), three quizzes, and a final exam. The final grade will be determined by taking the maximum of the following two schemes.

In both cases, in order to pass the class, you must pass the final exam.

Any regrade requests for all assignments, quizzes, and exams must be submitted within 24 hours after the initial grades are published.

Late Policy: Assignments will have a submission procedure described with the assignment. Maximum credit on a homework assignment reduces to 50% immediately after the submission deadline. Assignments will not be accepted 24 hours after the submission deadline. If you are a group of one (i.e., working as an individual) and require an extension (for personal reasons only) to a due date, you must request one as far in advance as possible. Extensions requested close to or after the due date will only be granted for clear emergencies or clearly unforeseeable circumstances.


Assignments, quizzes, and final exam:

Lecture topics (tentative) and slides:


Required textbook:

Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani
McGraw-Hill, 2008
[McGraw-Hill] [Amazon] [Google]

Optional textbook:

Algorithm Design
Jon Kleinberg and Eva Tardos
Pearson, 2005
(relevant sections will be placed on course reserves)

Other helpful textbooks:

How to Read and Do Proofs: An Introduction to Mathematical Thought Processes, 6th edition
Daniel Solow
Wiley, 2014
How to Prove It: A Structured Approach, 2nd edition
Daniel Velleman
Cambridge University Press, 2006
Book of Proof, 3rd edition
Richard Hammack

Last update: December 5, 2018