Amir Goharshady - Honors Algorithms

↢ Back to the List of Courses

COMP 3711H - Honors Design and Analysis of Algorithms

Spring Semester 2023-24

Number of Students: 70

Average Rating by the Students: 4.95/5.0

YouTube Playlist

https://www.youtube.com/watch?v=irzrLdt7V5U&list=PLzZlJT-UOiwD1OSqOs00D0iW93BSJPjBR

Course Files

https://drive.google.com/drive/folders/134ayXCVlOXNQHJznJ4JSQOt24d71uJ2e?usp=sharing

Notes of the first 16 lectures

https://drive.google.com/file/d/1sdARQ6BtpxuPfKIkWsAe35mADBdUaDt6/view?usp=drive_link

Thanks to Zhang Tianrui for preparing these notes.

Course syllabus

Instructor:

Amir Goharshady
Office: CYT 3006
Office Hours: Please make appointments by email

Guest Lecturer:

Dr Harshit Motwani
Office Hours: Please make appointments by email

Teaching Assistants:

Chun Kit "John" Lam
Kerim Kochekov
Office Hours: Please make appointments by email

Times and Venues:

Wednesdays, 15:00 - 16:20, Room 5583, Lifts 27-30
Thursdays, 15:00 - 15:50, Room 2404, Lifts 17-18
Fridays, 15:00 - 16:20, Room 5583, Lifts 27-30

Every session is a mixture of lecture and lab/tutorial.

Guest lectures and extra problem-solving sessions will be scheduled on zoom separately. They will be recorded for students who cannot attend.

Recommended Textbooks:

Introduction to Algorithms (3rd ed)
- Cormen, Leiserson, Rivest and Stein (CLRS). MIT Press
- E-version available from the university library
Algorithms
- Jeff Erikson (free book)
Algorithms
- Dasgupta, Papadimitriou, and Vazirani. McGraw Hill.

Programming Pearls (2nd ed)
- Bentley. Addison Wesley
Algorithm Design
- Kleinberg and Tardos. Addison Wesley
Problems on Algorithms (2nd ed)
- Ian Parberry and William Gasarch (free book)

Acknowledgments:

Much of the syllabus and material, especially slides, were prepared by Prof. Mordecai J. Golin, who kindly agreed to share it with us.

Grading:

Homeworks: 4 x 10%
- You will have a chance to resubmit each homework
Midterm Exam: 30%, pen and paper
- Time: Friday, 22 March 2024, 19:30-22:30
- Place: CYT-LTL
Final Exam: 30%, pen and paper
- Time: Thursday, 23 May 2024, 08:30-11:30 am
- Place: LG1 Table Tennis Room
Required Coding Practice: 0%
- These are required and missing any of them leads to a grade of F

Policy on Plagiarism:

Students are expected to follow the HKUST Academic Honor Code.
All files submitted by the students must be 100% their own individual work.
All work submitted for grading, e.g. assignments and codes, must be your own. You are permitted to discuss problems with other students but you must write-up all solutions by yourself, in your own words. If you got the main idea for a solution from another student or a web-site you must acknowledge that source in your submission.
You are not allowed to copy code from any source, even if you acknowledge it.
Submission of non-acknowledged material will be considered as plagiarism.
You are not allowed to use ChatGPT or similar tools.
We have a zero-tolerance policy on plagiarism. The minimum penalty is a grade of F for the whole course.

Important notes on how to answer questions that involve designing an algorithm: Your solution should consist of all of the following 4 components:

the main ideas of your algorithm (This will help you gain partial credits if your algorithm is not completely correct),
pseudocode or plain language description of the algorithm (must be detailed and exact, to a level that allows implementation with ease),
a tight asymptotic analysis of the running time of your algorithm, and
a proof of correctness for your algorithm (especially for greedy and graph algorithms)

The proofs must be written rigorously and with consistent mathematical notation.

A secondary benefit of working on the assignments is to prepare for the exams, because exam questions are often variants of assignment problems. For this reason we encourage you to spend time alone thinking about each problem and your approach in solving it. You are allowed to and encouraged to discuss assignment problems with your classmates. However, you must write up the solutions on your own. In particular:

Assignment solutions must be written in your own words (not copied or modified from someone else's write-up). If you see someone else's write-up, that's already plagiarism.
You must understand your solution and its derivation. (I may randomly ask you to explain your solution to me.)
You must explicitly acknowledge in writing in the assignment your collaborators (whether or not they are classmates) or any other outside sources on each assignment.
Failing to do any of these will be considered plagiarism, and will result in a failing grade in the course and notification for appropriate disciplinary action.

LaTeX Requirement:

All written assignments must be submitted as high-quality pdf files generated by LaTeX. We do NOT accept any other formats. Handwritten files or files generated by other typesetting software will be rejected without grading. If you are not familiar with LaTeX, https://www.overleaf.com/ is a great resource.

Programming Language:

This course uses standard C++ as its sole programming language. All codes must be submitted in .cpp format and will be compiled using the latest version of g++ on Ubuntu.