**Piazza link**

**Syllabus:**

**Title:**

**CSE 101: Introduction to Algorithms**

**Professors:**

- Office hours:
- Tuesday/Thursday
- 10:00-11:00
- Lecture:
- Tuesday/Thursday
- 8:00-9:20
- Center 115

- Office hours: (We'll move to 4258 if crowded and if available.)
- Tuesday 12-1
- Thursday 2-3
- Lecture:
- Monday/Wednesday
- 5:00-6:20
- Center 214

**TA’s**

**/tutors:**

- Prerit Dak (pdak@ucsd.edu)
- Office Hours: Friday 1:00p -3:00p, CSE B240A

- Asmitha Rathis (arathis@ucsd.edu)
- Office Hours: Tuesday 2:00p - 4:00p, CSE B240A
- Kriti Aggarwal (kriti@ucsd.edu)
- Office Hours: Friday 11:00a-1:00p , CSE Basement 240A
- Sasank Mouli (galivenk@ucsd.edu)
- Office Hours: Tuesday, Thursday 11:00a-12p, CSE Basement B240A
- Lihao He (lih046@ucsd.edu)
- Office Hours: Monday 8:00 am - 9:00am, Wednesday 12:00 p - 1:00 p, CSE Basement B220
- Side Li (s7li@eng.ucsd.edu)
- Office Hours: CSE Basement B240A, Thursday, 12pm-2pm
- Joseph Chen (joc009@ucsd.edu)
- Office Hours: CSE Basement B240A, Saturday 3pm-5pm
- Julia Kapich (juc033@ucsd.edu)
- Office Hours: CSE Basement B220, Monday 11pm-12pm and 1pm-2pm
- Sim Singh (sis034@ucsd.edu)
- Office Hours: CSE Basement B240A, Sunday 12pm-2pm

**Discussion Sections:**

- W 9:00-9:50 WLH 2113
**W 10:00-10:50 WLH 2113****W 11:00-11:50 WLH 2113****F 8:00-8:50 CENTER 222****F 9:00-9:50 CENTER 222****F 10:00-10:50 CENTER 222**

**Textbook:**

**(required text.)**Algorithms, by Dasgupta, Papadimitriou, Vazirani

**(optional text.)**Algorithm Design, by Jon Kleinberg, Éva Tardos

**Subject Material:**

We shall cover Graph Algorithms, Greedy Algorithms, Divide and Conquer, Algorithms, Dynamic Programming Algorithms, Max FlowComplexity

**Homework:**

Homework will be assigned on this website and you will upload your homework via Gradescope.

Due Mondays on gradescope with groups of size 1-4. Your lowest Homework grade will be dropped. First homework has two grades: grade based on problems attempted (only recorded grade) and ``as if this were an actual assignment grade’’.

**(Gradescope code: MX32YJ) (Gradescope link)**

**Quizzes:**

There will be 4 quizzes. We will drop the lowest quiz score.

**Participation: **

You will have opportunities to earn participation credits that will amount to 5% of your total grade. Each credit is worth 1/2 % so you can get a maximum of 10 credits. Any additional credits you earn are just good karma. You can earn a credit by completing a quiz in discussion (8 total will be given.) or by submitting a group report during in-class discussions that will be held once every two weeks in lecture (5 total.) In addition, you may earn credits when you have a Piazza post that is marked Good Question or Good Answer by the instructional team.

**Standards for assignments:**

Most required assignments will be mathematical or theoretical in nature, involving designing and analysing 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; a correctness proof, showing why the algorithm solves the problem in question; and a time analysis, giving the worstcase runtime (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 2 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.”

### Implementation Problems:

About every other homework assignment will have an algorithmic experiment problem. This will involve implementing an algorithm and running it on test examples. However, the point is to run the experiment; it is assumed that you can implement the algorithm successfully. The experiment may involve comparing the time used by or performance of several algorithms or versions of an algorithm. You can use any programming language, and do not need to turn in your code. What you need to turn in is a clear description of the experiment you ran (e.g., what algorithm you implemented, which programming language you used, which program library you used, what the programming environment you ran on is like.) Then clearly present the results, giving a table or graph of the results in terms of input sizes. Often, a log-log scale (log of the input size vs. log of the time used) is useful in giving a clear picture of algorithm performance.

Please write your homeworks clearly or typeset it using an editor such as LaTex and take clear scans or pictures.

**Collaboration Guidelines:**

Students are encouraged to collaborate on homework assignments. You may work in groups of up to four students.

**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; you should not enroll in this class if you cannot take the final examination at its scheduled time.

**Final Grade:**

30% Homework, 5% Participation, 30% 3/4 best quizzes (lowest quiz score is dropped.), 35% Final Exam

In addition, you must earn a passing grade (50%) on the final examination in order to pass the course.

**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.)**

**Academic Dishonesty:**

Academic dishonesty is considered a serious offense at UCSD. Students caught violating the UCSD Policy on Integrity of Scholarship will face an administrative sanction which may include suspension or expulsion from the university. You should read the UCSD Policy on Integrity of Scholarship, especially the Students’ Responsibility section.

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).
- Collaboration or copying on exams of any kind.
- Use of aids on exams outside of explicitly allowed materials (this may vary by exam)

**Use of Outside Resources:**

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