CSE 101 Syllabus
Winter 2021
Lecture: Monday, Wednesday, Friday 1:00-1:50pm pacific over zoom meeting
https://ucsd.zoom.us/j/93843292201?pwd=a1FDQS9Da0ZWWjRKUnZ3a3FQWHo5QT09
(if it asks for a password use “algorithms”).
Discussion Sections: Monday 2:00-2:50pm pacific over zoom
https://ucsd.zoom.us/j/95096735278?pwd=LzVTanhKc2VlNm1SMGNzS0lNUzBxdz09
(if it asks for a password use “algorithms”).
Course Webpage: http://cseweb.ucsd.edu/~dakane/CSE101/
Professor: Daniel Kane
Email: dakane “at” ucsd.edu
Office Hours: Thursday and Friday 2:30-4:00pm pacific over zoom at
https://ucsd.zoom.us/my/dankane or by appointment.
TAs:
Jiabei Han: Monday, Thursday, Friday 4:00-5:00pm pacific over zoom at
https://ucsd.zoom.us/j/92571674513.
Vaishakh Ravindrakumar: Monday, Wednesday, Friday 11:00am-12:00pm pacific over zoom
at
https://ucsd.zoom.us/j/7577412678.
Manish Kumar Singh: Tuesday 4:00-6:00pm and Thursday 5:00-6:00pm pacific over zoom at
https://ucsd.zoom.us/j/9029365896.
Chutong Yang: Tuesday 8:00-9:00pm and Thursday 7:00-9:00pm pacific over zoom at
https://ucsd.zoom.us/s/5785340529.
Tutor:
Harrison Matt Ku: Tuesday, Thursday 1:00-2:30pm pacific over zoom at
https://ucsd.zoom.us/my/harrisonku.
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
1
https://ucsd.zoom.us/j/93843292201?pwd=a1FDQS9Da0ZWWjRKUnZ3a3FQWHo5QT09
https://ucsd.zoom.us/j/95096735278?pwd=LzVTanhKc2VlNm1SMGNzS0lNUzBxdz09
http://cseweb.ucsd.edu/~dakane/CSE101/
https://ucsd.zoom.us/my/dankane
https://ucsd.zoom.us/j/92571674513
https://ucsd.zoom.us/j/7577412678
https://ucsd.zoom.us/j/9029365896
https://ucsd.zoom.us/s/5785340529
https://ucsd.zoom.us/my/harrisonku
additional topics such as linear programming, number theoretic algorithms and quantum
computation.
Prerequisites: CSE 12, CSE 21, CSE 100
Textbook: The textbook for the course will be Algorithms by Sanjoy Dasgupta, Christos
Papadimitriou, and Umesh Vazirani.
Exams: There will be three in-class exams on January 22nd, February 12th and March 5th.
The final exam will be on March 19th from 11:30-2:30.
Homework:
Submission Policy: Homework will be assigned on weeks without exams, 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 GEE42K.
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(n3) operations, then even if your algorithm in actually ran in O(n2) time, your solution
would be graded as if it actually took the full Ω(n3) operations to run.
In addition to this you should make sure to write your solution either in clear hand-
writing or typed using a computer, use of LATEXor similar typesetting package is recom-
mended (for those unfamiliar, there is a basic introduction to LATEXon the course webpage
at http://cseweb.ucsd.edu/~dakane/CSE101/latexGuide.pdf). 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
2
http://cseweb.ucsd.edu/~dakane/CSE101/latexGuide.pdf
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.
It is also impermissible to seek advice on specific homework problems from anybody not
associated with the course. This includes submitting problems to websites for solution help.
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).
Grading: Course grades will be determined using the following breakdown:
Homework: 15%
Exams: 3 × 15%
Final 40%
I tend to assign difficult exams, so scores may well be lower than you will see in other
classes. The grade cutoffs for A-, B- and C- will be no higher than 75, 60, and 45, respectively,
though I reserve the right to lower these thresholds if the course proves to be especially
challenging.
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)
Time permitting:
Linear Programming (Chapter 7)
Number Theoretic Algorithms (Chapter 1)
Quantum Computation (Chapter 10)
3