CSE 101 Syllabus
Winter 2023

Lecture: Monday, Wednesday, Friday 12:00-12:50pm in Price Theater.

Discussion Sections: Wednesday 3:00-3:50pm and 4:00-4:50pm in MOS 0113. Please feel free to attend whichever section is most convenient for you.

Course Webpage: http://cseweb.ucsd.edu/~dakane/CSE101/

Professor: Daniel Kane

Email: dakane ”at” ucsd.edu

TAs: Anuj Ahuja, Akhila Chekuri, Sihan Liu, Anthony Ostuni, Oishi Poddar, Stanislaw Strzelecki, Onur Tepencelik, Prashant Vaidyanathan

Tutors: Dian Jiao

Course Description: CSE 101 will cover the basics of the design and analysis of algorithms with a focus on non-numerical algorithms. We will cover general algorithmic techniques such as divide and conquer, greedy algorithms and dynamic programming. We will also discuss some important graph algorithms as well as NP-completeness and techniques for dealing with it. In the process of doing so, we will investigate several important algorithms such as sorting, shortest paths and longest common substrings. Time permitting we may also cover additional topics such as linear programming, number theoretic algorithms and quantum computation.

Prerequisites: CSE 12, CSE 21

Textbook: The textbook for the course will be Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani.

Submission Policy: Homework will be assigned on weeks without exams other than the last week of class, and will be due on gradescope on Friday at 11:59pm. I will attempt to have new homeworks available on the course webpage at least a week before they are due. We will put time limits on when regrade requests can be submitted, which will typically be about a week after when your grades have been returned. To accommodate exceptional situations such as accidents or serious illness, your lowest homework score will be dropped. To get an account for the gradescope for this course (if one was not created for you automatically), use entry code J38PZE.

Write-up Guidelines: Unless otherwise specified, all homework problems will require you to justify your answers. This will usually mean that you provide some sort of mathematical proof to justify your claims. As an example, a common type of homework question will be to provide an efficient algorithm to solve some particular computational problem. A full solution to such a problem should consist of the following:

• A description of your proposed algorithm and a claimed bound on the runtime: This description should preferably be a high level English language description of what your algorithm does (though detailed enough that it can be reasonably analyzed). This description may be supplemented with pseudocode if desired.

• A proof of correctness. In particular, a proof that your algorithm does correctly solve the computational problem in question.

• A proof that your algorithm runs in time given by your stated runtime bound.

The runtime analysis you give should provide an upper bound on the running time of the algorithm (generally given in terms of the big-O notation). This upper bound is not required to be tight (though you are encouraged to think about what the actual runtime of the algorithm is and to see if you can find further improvements), but your solution will be graded as if it were. For example, if you submit an algorithm and prove a runtime bound of O(n 3 ) operations, then even if your algorithm in actually ran in O(n 2 ) time, your solution would be graded as if it actually took the full Ω(n 3 ) operations to run.

In addition to this you should make sure to write your solution either in clear handwriting or typed using a computer, use of LATEXor similar typesetting package is recommended. If the graders are unable to decipher your writing, you will not get credit for it. Collaboration Guidelines: Students are encouraged to collaborate on homework assignments. You should feel free to discuss the problems and talk about how to come up with solutions with each other. On the other hand, you are expected to write up your solution independently of any collaborators, and you should not share written solutions to homework problems with other students before the homework deadline. If you do collaborate with other students on the homework, you should make sure to list any collaborators that you had on any given problem.

Use of Outside Resources: You should not attempt to search for homework solutions online or in sources outside of the course text. You may use such sources as a study guide, but if you accidentally stumble upon a homework solution in such an outside source you should 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 academic dishonesty.

Academic Integrity: Academic integrity will be taken very seriously be the course staff. Breaches of integrity may have broader consequences outside of the assignment in question. The following will all considered to be breaches of academic integrity:

• Collaboration on homeworks beyond the scope outlined in the section above (including sharing of homework solutions with other students before the homework deadline).

• Failure to cite collaborators on homeworks or outside sources used to find homework solutions.

• Collaboration or copying on exams of any kind.

• Use of aids on exams outside of explicitly allowed materials (this may vary by exam).

Homework: 15%

Exams: 3 × 15%

Final 40%

I will attempt to keep the grade distribution for this class similar to what it has been historically for CSE 101 (though I may adjust this slightly if I am particularly impressed or disappointed with the class as a whole). That said, I often give very difficult exams, so you should not be worried by low exams scores unless the rest of the class did much better. Historically, the cutoffs for A- and B- have been about 75 and 60, respectively.

Schedule: Below is a rough schedule for topics covered in the class:

Graph Algorithms (Chapters 3 and 4)

Divide and Conquer (Chapter 2)

Greedy Algorithms (Chapter 5)

Dynamic Programming (Chapter 6)

NP-Completeness (Chapters 8 and 9)