DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

UNIVERSITY OF CALIFORNIA, SAN DIEGO

Instructor: Ben Ochoa

Email: bochoa at ucsd.edu

Office hours: Tu 6:30 PM-8:30 PM, EBU3B 3234, and at other times by appointment

TA: Yiyuan (Sparrow) Ma

Email: yim096 at eng.ucsd.edu

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 eng.ucsd.edu

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 eng.ucsd.edu

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 eng.ucsd.edu

Office hours: W 3:30 PM-4:30 PM, EBU3B B275

Tutor: Toan Bui

Email: tkb001 at ucsd.edu

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 ucsd.edu

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

Discussion:

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

F 3:00 PM-3:50 PM, CENTR 222 (section ID: 947830)

F 4:00 PM-4:50 PM, CENTR 222 (section ID: 947831)

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.

- a clear and complete description of your algorithm, including a high-level description
- a correctness proof, showing why the algorithm solves the problem in question
- a time analysis, giving the worst-case runtime (up to order, in big O notation)

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.

- 30% homework assignments, 30% three quizzes, 40% final exam
- 30% homework assignments, 20% two quizzes (drop lowest quiz), 50% final exam

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.

Handouts/Readings:

- Order notation summary by Leeann Bent
- Algorithm Design (
*J. Kleinberg and E. Tardos*), Chapter 4

Assignments, quizzes, and final exam:

- LaTeX class file (needed for all provided LaTeX homework source files)
- Homework 1 LaTeX source (assigned Oct 2, due Oct 9)
- Homework 2 LaTeX source (assigned Oct 9, due Oct 16)
- Quiz 1 (Graph search; Oct 18)
- Homework 3 LaTeX source (assigned Oct 16, due Oct 23)
- Homework 4 LaTeX source (assigned Oct 23, due Oct 30)
- Homework 5 LaTeX source (assigned Oct 30, due Nov 6)
- Quiz 2 (Graph search and minimum spanning trees; Nov 8)
- Homework 6 LaTeX source (assigned Nov 13, due Nov 20)
- Quiz 3 (Greedy algorithms and divide and conquer algorithms; Nov 27)
- Homework 7 LaTeX source (assigned Nov 29, due Dec 6)
- Final exam (Dec 14)

Lecture topics (tentative) and slides:

- Lecture 1 Overview and time analysis (chapter 0; Sep 27)
- Lecture 2 Max bandwidth path and depth-first search (sections 3.1 and 3.2; Oct 2)
- Lecture 3 Directed acyclic graphs and strongly connected components (sections 3.3 and 3.4; Oct 4)
- Lecture 4 Strongly connected components and breadth-first search (sections 3.4, 4.1, 4.2, and 4.3; Oct 9)
- Lecture 5 Dijkstra's algorithm and priority queue implementations (sections 4.4 and 4.5; Oct 11)
- Lecture 6 Priority queue implementations and minimum spanning trees (sections 4.5 and 5.1; Oct 16)
- Lecture 7 Minimum spanning trees and union-find (section 5.1; Oct 18)
- Lecture 8 Greedy algorithms (Kleinberg and Tardos sections 4.1, 4.2, and 4.3; Oct 23)
- Lecture 9 Greedy algorithms (Kleinberg and Tardos sections 4.1, 4.2, and 4.3; Oct 25)
- Lecture 10 Greedy algorithms (Kleinberg and Tardos sections 4.1, 4.2, and 4.3; Oct 30)
- Lecture 11 Greedy algorithms and divide and conquer multiplication (Kleinberg and Tardos sections 4.1, 4.2, and 4.3; and section 2.1; Nov 1)
- Lecture 12 Divide and conquer multiplication and master theorem (section 2.1 and 2.2; Nov 6)
- Lecture 13 Divide and conquer fast Fourier transform (section 2.6; Nov 8)
- Lecture 14 Divide and conquer mergesort and medians (sections 2.3 and 2.4; Nov 13)
- Lecture 15 Divide and conquer examples (Nov 15)
- Lecture 16 Divide and conquer examples, and backtracking (Nov 20)
- No lecture meeting (Nov 22)
- Lecture 17 Dynamic programming (chapter 6; Nov 27)
- Lecture 18 Dynamic programming (chapter 6; Nov 29)
- Lecture 19 Dynamic programming (chapter 6; Dec 4)
- Lecture 20 NP-complete problems (chapter 8; Dec 6)

Links:

Required textbook:

Algorithms

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

[Amazon]

How to Prove It: A Structured Approach, 2nd edition

Daniel Velleman

Cambridge University Press, 2006

[Amazon]

Book of Proof, 3rd edition

Richard Hammack

2018

[Amazon]

*Last update: December 5, 2018*