CSE 101 - Design & Analysis of Algorithm - Jones [SP24]
Welcome to CSE 101.
This class is about algorithms. There are two main goals; introducing students to common algorithms and analyzing their runtime and correctness, and developing broad problem solving techniques related to the algorithms we discuss.
We will concentrate on general techniques that have been used to develop and analyze efficient algorithms for a wide variety of applications. We organize algorithms by technique, rather than application domain. Students will be expected to master these techniques, not just to understand the standard algorithms, but to design new algorithms using similar methods.
We shall cover the most widely used algorithm techniques in depth: Graph Algorithms (DFS/BFS/etc.), Greedy Algorithms, Divide and Conquer Algorithms, Dynamic Programming Algorithms, and Hill-climbing (e.g.,Max Flow). We will also give a quick introduction to Complexity, especially NP-completeness and its consequences for algorithm design.
There is no particular programming language you need to know for this class since most of the content is based on pseudocode. That being said, there will be some optional exercises in python using Jupyter notebooks.
Learning outcomes:
- Write clear high-level and implementation-level descriptions of algorithms.
- Write clear justifications of correctness and clear runtime analysis of algorithms.
- Demonstrate familiarity with common algorithms and data structures.
- Trace common algorithms on simple examples to gain familiarity.
- Analyze the runtime and correctness of algorithms.
- Develop algorithmic problem solving techniques for novel problems based on common algorithms, data structures and design paradigms (including divide and conquer, dynamic programming, greedy algorithms...).
Prerequisites
The main prerequisites for this class are CSE 21 and CSE 20 (mainly CSE 21). From CSE 20, you should know basic proof techniques (especially induction) and basic logical reasoning. From CSE 21, you should know basic algorithm analysis, graph theory, and basic probability.
CSE 100 is not a prerequisite anymore but it used to be. From this class, it is nice for you to know how to use basic data structures (stack, queue, min/max heap, adjacency list, ....) but is not necessary.
Instructional Staff:
(Piazza (private post) is the preferred way for you to communicate with the instructional staff.)
[PLEASE DO NOT USE CANVAS MESSAGES TO COMMUNICATE WITH THE INSTRUCTIONAL STAFF]
|
Name |
Position |
Email Address |
Office hours |
|
|
Miles Jones |
Instructor |
Monday 3:30-4:30 Tuesday: 2:30-3:30 CSE 4208 |
|
|
|
Chandrasekaran, Rishikanth |
Teaching Assistant |
Wed: 3:00-4:00 |
|
|
|
Giridharan, Aditya |
Teaching Assistant |
Tue 6-8p @B275 |
|
|
|
Lin, Xinsong |
Teaching Assistant |
Mon 2-3 @B240A Wed 2-3 zoom |
|
|
|
Ram, Manav |
Teaching Assistant |
07/15 Wed 5-6 pm (Zoom) Thu 3:15pm-4:15 pm (Zoom) |
|
|
|
Thorat, Shubham |
Teaching Assistant |
Tue 1-3 pm Note: 05/14 OH shifted to 05/16 (9-11 am). |
|
|
|
Bychenkov, Oleg |
Tutor |
Tue 5-6pm B240A Thur 5:30-6:30pm Zoom |
|
|
|
Flar, Tyler |
Tutor |
Tue 4-5 pm (Zoom) Fri 4:30-5:30 pm (Zoom) |
|
|
|
Ho, Nicholas |
Tutor |
Tuesday 1:30 - 2:30 pm B240a Thursday 1:00 - 2:00 pm (Zoom) |
|
|
|
Jiang, Yuhang |
Tutor |
Tue 6-8 pm B250A or Basement |
|
|
|
Nguyen, Valerie Thao |
Tutor |
Wed 11:00am-12:00pm B260A Thurs 1-2pm Zoom |
|
|
|
Reyes, Xicotencatl Sebastian |
Tutor |
Mon, Wed 11:00am - 12:00pm Zoom |
|
|
|
Shen, Marcelo |
Tutor |
Wed 11am-12pm Zoom Fri 12:00pm-1:00pm B270A |
|
|
|
Tran, Kyle Huy-Khoa |
Tutor |
Mon 12-1pm Zoom Wed 12-1pm B270A |
|
|
|
Wang, Justin |
Tutor |
Mon 7-8pm Zoom Thurs 4-5pm B250A |
|
To make an appointment for a 1-on-1 with a TA/tutor, follow the instructions in this spreadsheet:
Office hours and One-on-One sessions
The instructor, TAs and tutors will hold office hours (locations TBD). During office hours, you can ask questions about lecture or homework. There may be other students there from different groups. It is okay to share some strategies and hints but it is discouraged to share your answers directly with other students. Office hours are a great way to get ideas and hints on how to start and finish the homework. This class is challenging and it is recommended to attend office hours in order to succeed.
One on one sessions are 30 minute sessions that you can sign up for to meet one-on-one with a TA or tutor. (Or, if you like, you can schedule a session for your whole group.) One-on-one sessions are not intended for discussing the current homework assignment, they are for discussing previous homeworks and lectures. They are designed to help students who may feel behind in the class and want to revisit some concepts from previous lectures.
Time and Location
| Date |
Day |
Time | Room |
| Lecture | Tu/Th | 11:00am-12:20pm |
GH 242 |
| Discussion Section |
Fridays
|
11:00am-11:50am |
|
| Final Exam |
Tuesday June 11 |
Scheduled for 11:30am-2:29pm Details to come |
TBD |
-
Lectures
- The lecture slides will be posted before class on the content calendar link.
- You may interrupt lecture to ask questions, make comments or express doubts (Please raise your hand and [In case of emergency, I may have to teach remotely. In which case:] for those via zoom, you can use the chat feature. There will be TAs monitoring the zoom chat.)
- All lectures will be recorded and posted for students to watch when they want on podcast.ucsd.edu.
- If I have to teach remotely then you are not required to have a webcam.
Course Resources:
Gradescope (link on canvas sidebar)
Gradescope entry code: YD4VJ6
Piazza (link on canvas sidebar)
Textbooks:
(required text) Algorithms, by Dasgupta, Papadimitriou, Vazirani
(optional text.) Algorithm Design, by Jon Kleinberg, Éva Tardos
Coursework and grades:
Assignments/Graded work:
Your grade will be based on the following:
- Homework
- 2 Midterms
- 1 Final Exam
Homework:
Homeworks can be downloaded from the homework page.
Homework should be done in groups of 1-4 people. So you may do them on your own if you prefer not to work in a group. You are free to change group member at any time throughout the quarter. Problems should be solved together, not divided up between partners.
We will drop the lowest homework score.
Homework solutions should be typed (NOT HANDWRITTEN) and turned in through Gradescope by 11:59pm on the due date. You will be able to look at your scanned work before submitting it. Please ensure that your submission is legible or your homework may not be graded. You may resubmit updated versions of your homework up until the deadline. Only your most recent Gradescope submission will be graded.
Late Homework:
You may hand in your homework up to 24 hours late with a penalty of 1 point.
Regrade Policy:
Please make regrade requests on gradescope. Regrade requests should be open for 4 days. The entire problem will be reevaluated so grades may go down. Please only make a regrade request if you believe that the assignment was graded incorrectly. If you would like to understand how the assignment was graded please book a one-on-one session or bring it up during office hours.
Standards for HOMEWORK assignments:
Most required assignments 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, no implementation will be needed to complete these assignments. However see below for algorithm experiments. Grading of all problems (homework and exam) 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 things 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 run-time (up to order, in 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 on the time taken by the algorithm, in 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 key phrases such as “Find a solution and justify your answer.”
Collaboration Guidelines:
Students are encouraged to collaborate on homework assignments. You may work in groups of up to four students. Your group will submit one assignment and Gradescope will give you the opportunity to add all of your group members to the assignment. Groups do not have to be the same people for every assignment. You can change group members at any time.
If you are discussing problems with students outside of your group, please only share hints and basic techniques. DO NOT share your answers or allow other students to copy your written work. The bottom line is to submit YOUR OWN work. If we find that your work is too similar to another group's then you may be suspected of an academic integrity violation. All students whose names are on the assignment must have participated in answering all questions, at the minimum by carefully proof-reading the submitted answers. If there is a member of your group that did not participate, you cannot list them as a group member for this assignment. If some other student or teaching staff gave you a tip that was particularly useful, please give them an acknowledgement in the assignment. That will help us avoid unnecessary accusations of academic integrity violations.
You may not collaborate with anyone outside of the class. You are not permitted to ask homework questions to message boards or websites such as Chegg or GenAI software such as ChatGPT.
You may use some materials not from class, such as other textbooks, notes from previous sections of the class, Khan Academy videos or something similar, but with some caution. If an outside source has something relevant to a particular homework or exam problem, you must give the source a reference when you submit your assignment. We will review how similar the reference is to your answer. If it is too similar, you may lose some points for the assignment, but as long as you give the reference, it will not be an Academic Integrity issue. (It is considered an academic integrity violation to enter homework questions into ChatGPT or other GenAI software and present the results as your own.)
Midterms:
There will be two midterms.
Test 1: Graph algorithms
Test 2: Greedy and Divide and conquer
There is an option to drop your lowest midterm score and have the final exam count for more.
Each midterm must be taken during the class time. For extenuating circumstances, if you are unable to physically come to class, then please let me know.
Final Examination:
The final examination will be held at the date and time stated in the course calendar. It is your responsibility to ensure that you do not have a schedule conflict involving the final examination.
Final Grade:
The final grade will be computed by taking the maximum of the two schemes:
Grading option 1: 35% Homework, 15% MT1, 15% MT2, 35% Final Exam
Grading option 2: 35% Homework, 20% best midterm, 45% Final Exam
Tentative Grade Scale: Your final grade will be based on the following scale. (You will earn the grade in the table based on your numerical score or higher.)
A+ A A- B+ B B- C+ C C- D
97 93 89 85 81 77 73 69 65 60
Course Policies
Academic Integrity
In this course we expect students to adhere to the UC San Diego Integrity of Scholarship Policy. This means that you will complete your work honestly, with integrity, and support an environment of integrity within the class for which you are tutoring. Some examples of specific ways this policy applies to CSE 21 include:
- Do not discuss solutions to homework problems with people besides your homework partner (except during office hours, with the instructional team).
- Do not share written solutions with other groups.
- Do not collaborate or copy exams.
- You should not attempt to search for homework solutions or exam solutions online or in sources outside of the course content. (Example: you should not consult content from CSE 21 of past quarters.) 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.
- Follow the golden rule for Academic Integrity: Always give credit for any outside help on any assignment, except for those whose job it is to help you (Instructors, TAs, tutors, the textbook, your teammates, and class handouts.)
- Note on ChatGPT and other GenAI software: Inputting homework or exam questions into ChatGPT or any other GenAI software and turning in the answer that is given is considered an Academic integrity violation. As with any other resource, I expect your words and work to be your own.
- Please let me know if you have any questions about these guidelines and if you are unsure if something is considered a violation, you can always ask.
Collaboration Policy
For homework collaboration policy, see the paragraph above.
For the exams, you are not permitted to collaborate with anyone else (including people from outside of the class like message boards or Chegg). We will give you the opportunity to ask questions to the teaching staff during exams.
Regrade Policy
Please be prompt (three days) in reporting to your TA any errors in the grading of your work, or in the recording of your grade. All grades become permanent three days after they are recorded. Regrade requests for homework assignments must be made on Gradescope. Please note that by requesting a regrade for a problem, it will be completely regraded and your grade may go up or down. When you make a regrade request, you should specify exactly what the mistake in grading is, i.e., the wrong rubric item was selected or the rubric itself is inaccurate. Vague requests for more partial credit will not be granted.
Late or Missed Assignments/Missed Exam Policy
Late Homework:
You may hand in your homework up to 24 hours late with a penalty of 1 point.
Exams:
Other than extenuating circumstances, there is no credit for late or missed exams.
Technology Policy
For homework assignments and for exams, you are permitted to use calculators. (See the section on Academic integrity for more details.)
Outside Tutoring
Individuals are not permitted to approach students to offer services of any kind in exchange for pay, including tutoring services. This is considered solicitation for business and is strictly prohibited by University policy.
Resources for Students
Getting Help
We provide many office hours and 1-1 sessions. Please use them. This class can be challenging if you don't engage with the teaching staff.
The IDEA Engineering Student Center, located just off the lobby of Jacobs Hall, is a hub for student engagement, academic enrichment, personal/professional development, leadership, community involvement, and a respectful learning environment for all. The Center offers a variety of programs, listed on the IDEA Center Facebook page at http://www.facebook.com/ucsdidea/ (you are welcome to Like this page!) and the Center website at http://idea.ucsd.edu/ . The IDEA Center programs support both undergraduate students and graduate students.
Diversity and Inclusion
We are committed to fostering a learning environment for this course that supports a diversity of thoughts, perspectives, and experiences, and respects your identities (including race, ethnicity, heritage, gender, sex, class, sexuality, religion, ability, age, educational background, etc.). Our goal is to create a diverse and inclusive learning environment where all students feel comfortable and can thrive.
Our instructional staff will make a concerted effort to be welcoming and inclusive to the wide diversity of students in this course. If there is a way we can make you feel more included please let one of the course staff know, either in person, via email/discussion board, or even in a note under the door. Our learning about diverse perspectives and identities is an ongoing process, and we welcome your perspectives and input.
We also expect that you, as a student in this course, will honor and respect your classmates, abiding by the UCSD Principles of Community ( https://ucsd.edu/about/principles.html ). Please understand that others’ backgrounds, perspectives, and experiences may be different than your own, and help us to build an environment where everyone is respected and feels comfortable.
If you experience any sort of harassment or discrimination, please contact an instructor as soon as possible. If you prefer to speak with someone outside of the course, please contact the Office of Prevention of Harassment and Discrimination: https://ophd.ucsd.edu/ .
Students with Disabilities
We aim to create an environment in which all students can succeed in this course. If you have a disability, please contact the Office for Students with Disability (OSD), which is located in University Center 202 behind Center Hall, to discuss appropriate accommodations right away. We will work to provide you with the accommodations you need, but you must first provide a current Authorization for Accommodation (AFA) letter issued by the OSD. You are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance so that accommodations may be arranged.
Basic Needs/Food Insecurities
If you are experiencing any basic needs insecurities (food, housing, financial resources), there are resources available on campus to help, including The Hub and the Triton Food Pantry. Please visit http://thehub.ucsd.edu/ for more information.
Course Summary:
| Date | Details | Due |
|---|---|---|