Syllabus

Syllabus:

Title:

            CSE 101: Introduction to Algorithms

Professors:

  •  Miles Jones (mej016@ucsd.edu). Office: 4208 CSE.
    • Office hours: Tuesdays 1-3
  •  Russell Impagliazzo (@ucsd.edu). Office: 4248 CSE.
    • Office hours: Mondays and Wednesdays 1-2

TA’s/tutors:

  • Sahil     (saa034@eng.ucsd.edu)
    • Office hours: Wednesdays 10-11am, Room: Computer Science 2236
  • Kriti     (kriti@eng.ucsd.edu)
    • Office hours: Mondays 3-5pm, Room: Computer Science 4109
  • Ivan     (imikhail@eng.ucsd.edu)
    • Office hours: Fridays 3-5pm room: 3109
  • Stefanos     (spoulis@eng.ucsd.edu)
    • Office hours: Thursdays 3-5pm
  • Mridul     (m1garg@eng.ucsd.edu)
    • Office hours: Thursdays 2-3pm (Room 3109)
  • Lilith     (lihuang@ucsd.edu)
    • Office hours: Mondays 5-7pm, Room: Computer Science Lab B220
  • Julia    (juc033@ucsd.edu)
    • Office hours: Tuesdays 3-5pm, Room: Computer Science Lab B220
  • David     (dmoll@ucsd.edu)
    • Office hours: Mondays 10am-12pm, Room: Computer Science Lab B220
  • Aamir     (aarashee@ucsd.edu)
    • Office hours: Mondays 3-5pm, Room: Computer Science 2236
  • Matthew     (m9yu@ucsd.edu)
    • Office hours: Fridays 11am-1pm, Room: Computer Science Lab B220

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

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.

Exams:

            There will be two exams

Exam 1: (Week 4)

Exam 2: (Week 8)

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:

        Your grade will be calculated as the maximum of the following two grading schemes

30% Homework, 15% Exam 1, 15% Exam 2, 40% Final Exam

35% Homework, 15% Best Exam, 50% Final Exam

In addition, you must earn a passing grade (60%) 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.)

A+        A          A-        B+        B          B-        C+       C            C-

97        93        89        85        81        77        73        69            65       

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.