Piazza Link

Entry Code: 942X4W
(please include your PID if you are using the entry code.)
(:

Syllabus:

Title:             CSE 101: Introduction to Algorithms 
Professors:
  •  Miles Jones (mej016@ucsd.edu). Office: 4208 CSE.
    • Office hours: Wed 1-3 CSE 4208
    • Lecture: 
      • TuTh 
      • 8:00-9:20 (B00)
      • 9:30-10:50 (C00)
      • CENTER 212
  • Russell Impagliazzo (russell@ucsd.edu) Office: 4248
    • Office hours: Thursday, 11-1 starting in 4248 CSE
    • Lecture:
      • MWF 4:00-4:50 (A00)
      • CENTER 212
  • Discussion:
      • Mondays:
        • 4:00-4:50 WLH 2204
        • 5:00-5:50 WLH 2204
      • Wednesdays:
        • 8:00-8:50am PETERSON 104
        • 9:00-9:50am PETERSON 104
      • Fridays:
        • 4:00-4:50 WLH 2204
        • 5:00-5:50 WLH 2204
Instructors/TA’s/tutors:


Name Role Office hours Location email
Russell Impagliazzo Instructor

russell@eng.ucsd.edu
Miles Jones Instructor Wed 12-2 4208 mej016@eng.ucsd.edu
Gu, Shuyu Teaching Assistant Tues 2-4pm B275 sgu@ucsd.edu
Mishra, Archit Teaching Assistant Mon 10-11am, Tues 1-2pm B250A
Schueroff de Souza, Heitor Teaching Assistant Tue 4-5pm
Thu 3:30-4:30p
B270A
B275
hdesouza@ucsd.edu
Soliev, Bekhzod Teaching Assistant Tue 7-9pm
B215
bsoliev@eng.ucsd.edu
Hasan Al JamalyTutor Mon 1 - 3 B250A haljamal@ucsd.edu
Bui, Toan Khanh Tutor Thu 11am-1pm B215 tkb001@ucsd.edu
Kubatko, Daniil Tutor Mon 3-4pm
Th    2-3pm
B250A
B240A
dkubatko@ucsd.edu
Le, Bella Bao Han Tutor Mon 4 - 6 PM B250A bbl003@ucsd.edu
Yu, Tianyi Tutor Wed 3:30-5PM 
Fri 3 - 4 PM
CSE 4258
B260A
tiy059@ucsd.edu
Sasank Mouli TA Tues 11-1
B260A


Divya Pitta TA Mon 1-3pm B250A dpitta@eng.ucsd.edu
Sparrow Ma TA Weds 5-7 pmCSE 3109 yim096@ucsd.edu

Textbook:        
    (required text.) Algorithms, by Dasgupta, Papadimitriou, Vazirani        
    (optional text.) Algorithm Design, by Jon Kleinberg, Éva Tardos

Subject Material:

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.  

Homework: 

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

Due Thursdays on gradescope with groups of size 1-4. Your lowest Homework grade will be dropped.

It is required to type your homework. (using latex, word, ....) (Figures can be hand-drawn.)

Points will be taken off for hand-written homework.

Regrade Policy:

Please make regrade requests on gradescope. Regrade requests will 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 bring that up during office hours.

    

Quizzes:

There will be three quizzes. Each will be 10% of your grade. There is an option to drop your  lowest quiz score and have the final exam count for more. You must take your quiz during the lecture you are enrolled in.

Standards for HOMEWORK 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, 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 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.”

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

You may work with student from other CSE 101 sections regardless of the professor.

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:         

The final grade will be computed by taking the maximum of the two schemes:

30% Homework, 30% 3 quizzes,  40% Final Exam

30% Homework,  20% 2 best quizzes (lowest quiz dropped.),  50% Final Exam

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