CSC 510.01 & .02: Analysis of Algorithms I
(#1705, #2836)
Fall 2024 (3 units)
|
Instructor: Dr. Kazunori Okada |
|||
|
Section 01 Section 02 |
WED: 4:00 - 6:45 pm TTH: 2:00 – 3:15 pm |
Location 01 Location 02 |
HSS Building 248 Thornton Hall 329 |
|
Office Phone |
(415) 338-7687 |
Office |
Thornton Hall 911 |
|
CS Office |
(415) 338-1244 |
Office Hours |
Thr: 11:30 am - 12:30 pm |
|
Email Address |
Web Page |
||
|
Mailing Address |
Computer Science Department, San Francisco State
University |
||
|
Teaching Assistant 01 |
Xiaoxuan Wang |
TA Office Hour TA Office |
Mon: 1:00 pm - 2:00 pm Online (see Canvas) |
|
Teaching Assistant 02 |
Xiaoxuan Wang |
TA Office Hour TA Office |
Mon: 1:00 pm - 2:00 pm Online (see Canvas) |
Course Outline:
|
Subjects |
Estimated Duration |
|
Overview & Math Review |
1 week |
|
Complexity Functions |
1.5 weeks |
|
Asymptotic Notations |
0.5 week |
|
Recurrence Relations |
1 week |
|
Divide and Conquer |
2 weeks |
|
Dynamic Programming |
2 weeks |
|
MIDTERM: Section-01 MIDTERM: Section-02 |
Tentative: Oct 30 (Reviews: 10/23) Tentative: Oct 29 (Reviews: 10/22 & 10/24) |
|
Greedy Algorithm |
2 weeks |
|
Backtracking |
1 week |
|
Branch and Bouund |
1 week |
|
FINAL: Section-01 FINAL: Section-02 |
Dec 18 Wed, 4:45 pm - 6:45 pm (Review: 12/11) Dec 17 Tue, 2:45 pm - 4:45 pm (Review: 12/10 & 12/12) |
Course Summary:
The goal of this course is to introduce students to ideas and techniques of main algorithm analysis and design methodologies. We study topics in such areas as measures of algorithm complexity in space and time, algorithms of classical problems such as sorting and shortest-path and solving problems by determining and applying an appropriate designing methodology.
Recommended Textbooks:
No textbooks are assigned for this course. Slides used in lectures will be shared with students to help you learn the materials. To aid your self-study, you may use free texts on algorithms such as one by Jeff Erickson
https://jeffe.cs.illinois.edu/teaching/algorithms/
Contents of this course will not be synchronized with this text or others.
Course Web Page:
https://bidal.sfsu.edu/~kazokada/csc510/
Contents of this document serve as
the syllabus of this course and will be available through the above URL. Canvas
course page will contain all other course materials including a copy of this
syllabus. Note that a single iLearn page titled
510.01 will serve for both sections 01 and 02. It is your duty to read them carefully, use only
materials assigned to your section, and attend the events specific to each
section at the correct assigned time (e.g., final exam).
Prerequisites:
CSC 340 (Programming Methodology) and MATH 324 (Probability and Statistics with Computing) with a grade of C or better. Concurrent registration is not allowed. And students who do not meet these prerequisites will not be permitted to take this course.
No show for the first class meeting will result in automatic drop from the roster to make room for other students in waitlist.
Office Hours:
Office hours will be available for consulting with both the instructor and the TA during the time specified above. If online, zoom links for them will be available on the Canvas course page. Students are requested to make yourself visible by turning the video on. Students will be met on a first-come first-served basis. Please email the instructors ahead of time to reserve a specific time slot of 10-20 minutes, should you have important issues to consult with.
Homework:
Homework assignments will be given to assist your self-study and to prepare you for exams. Assignments will be available through Canvas. Submit your answer also via Canvas in a single PDF scan file by a due date specified by the instructor. In your submission, write your name, student ID, and homework number clearly on each page. No late homework submission will be accepted.
Exams:
There will be a midterm test as well as the final exam. The final exam may cover all the materials taught in this course. These exams will be administered in -person. See the tentative schedule of them in the course outline table above. No make-up exams will be given.
Grade Weights:
· 30%: Homework
· 30%: Midterm
· 40%: Final Exam
· Attendance may be used as a small extra credit for those who attend all or most classes.
· Other ad hoc assignments may be given as extra credits.
· The default grade distribution is as follows: A (100% - 92.5%), A- (92.4%-90%), B+ (89.9% - 87.5%), B (87.4% - 82.5%), B- (82.4% - 80%), C+ (79.9% - 75%), C (74.9% - 65%), C- (64.9% - 60%), D+ (59.9% - 57.5%), D (57.4% - 52.5%), D- (52.4% - 50%), F (49.9% - 0%)
Grade Appeal:
To appeal your grades on assignments and exams, you must do so within one week after graded assignments/exams were returned or made available to students. There will be no exception even if you miss those classes and/or announcements. You are responsible to find out your own grades.
Regular attendance is recommended as attending lectures is the best way to learn the material. From the SFSU bulletin: “Students are expected to attend classes regularly because classroom work is one of the necessary and important means of learning and of attaining the educational objectives of the institution.” In the event of an absence, it is the student’s responsibility to learn of any material missed and acquire assignments and announcements given during the class. Lectures and demonstrations will not be repeated during office hours. In case of extraordinary circumstance, it is the student’s responsibility to inform the instructor and submit supporting documents as soon as s/he can.
Canvas Usage:
Distribution and submission of your homework will be handled through the Canvas course page. After the instructor made it available, click the specified Canvas link to view the assignment. Work on your problems and write down your answers on your own papers (make sure you write your name and SID# for each page). After you complete it, sort your answer papers according to the problem numbers and scan them by using a PDF-Scan tool (e.g., CamScanner, Scannable, GeniusScan, AdobeScan, Multifunction Printer, Google Drive Scanner etc) and save it to a single PDF file, combining all pages into one file. After checking that all pages are present and readable, submit your PDF file by using the specified Canvas’s assignment submission link. Always double-check what you submitted for its completeness and readability.
Both the midterm and final exams will be handled in-person using paper.
Syllabus is Subject to Change:
This syllabus and schedule are subject to change. The official syllabus will be maintained at the course website. It is your responsibility to check on the site frequently and even when revisions are made while you are absent.
Academic Integrity & Plagiarism:
Academic integrity, the ethical presentation of one's own work in accordance with the rules established for this class, is required. Instances of academic misconduct will be reported to the College in which the course is housed, the Division of Graduate Studies (if a graduate student), and the Office of Student Conduct with the report being kept in those offices until a student earns his/her degree. Any instances of cheating, deceit, fabrication, forgery, plagiarism, unauthorized altering of records or submitting false documents, unauthorized collaboration, unauthorized submission of work previously given credit, or other forms of academic misconduct will be assigned a grade penalty, likely an F or a grade of zero. Failing one or more assignments or examinations for reasons of academic integrity violations may result in a final class grade of F. Students may not withdraw from classes in which they have committed academic misconduct. Consequences for violations of academic integrity may exceed an F on the assignment, examination, or class as determined by the Academic Integrity Review Committee.
Members of our academic community have a responsibility to develop an awareness of academic integrity, to cultivate skills to realize honesty in academic and community work, and to sustain actively academic honor as a core value of our community. Students are expected to engage in behaviors that reflect well upon the university. In addition to attending to one's own actions, the Standards for Student Conduct require that students who witness academic dishonesty notify their faculty/instructor, department chair, or the Office of Student Conduct. Supporting academic integrity enhances the reputation of the University and the value attributed to degrees awarded by the University.
I encourage discussion among students, but I expect each student to hand in their original work. You are responsible for doing your own work and for ensuring that your work is protected from copying. Usage of online cheating sites, such as a use of Chegg.com and CourseHero.com, is strictly forbidden. Use of AI tools, such as ChatGPT, is discouraged. Violation of this rule will be treated seriously without any leniency. Your continued enrollment in this class indicates that you have carefully and entirely read and pledge to abide by the Honor Code published on the Canvas page of this course and accept the consequences to violations of its terms. Violation of the university and departmental rules (found in below links) is a serious offence and can result in severe penalties. It is your responsibility to familiarize yourself with the following rules:
· SFSU Code of Student Conduct: http://conduct.sfsu.edu/standards
· Academic Dishonesty: http://conduct.sfsu.edu/academic-dishonesty
· Plagiarism: http://conduct.sfsu.edu/plagiarism
· Computer Science Department Policy: https://cs.sfsu.edu/student-policies#accordion-collapse-accordion-824-2
Learning Assistances:
The Tutoring and Academic Support Center (TASC) is a new university-wide center that supports the academic success of all San Francisco State students. They are offering services online via Zoom. Please email tutoring@sfsu.edu from your SF State email address with your name, student ID, course for which you are seeking tutoring, and available days/times for an appointment. They will reply with details for your online appointment. More information can be found at https://tutoring.sfsu.edu/.
· Phone Number: 415-405-5516
· Location: LIB 220 (In-person) & Zoom (Online)
· Hours: Mon-Thr, 9:00 a.m. to 5:00 p.m. and Fri, 10:00 a.m. to 2:00 p.m.
· Email: tutoring@sfsu.edu
Religious Holidays:
Reasonable accommodations will be made for you to observe religious holidays when such observances require you to be absent from class activities. It is your responsibility to inform the instructor during the first two weeks of class, in writing, about such holidays.
Disability Access:
Students with disabilities who need reasonable accommodations are encouraged to contact the instructor. The Disability Programs and Resource Center (DPRC: https://access.sfsu.edu/) is available to facilitate the reasonable accommodations process. The DPRC is located in the Student Service Building and can be reached by telephone (voice/415-338-2472, video phone/415-335-7210) or by email (dprc@sfsu.edu).
Student Disclosures of Sexual Violence:
SF State fosters a campus free of sexual violence including sexual harassment, domestic violence, dating violence, stalking, and/or any form of sex or gender discrimination. If you disclose a personal experience as an SF State student, the course instructor is required to notify the Title IX Coordinator by completing the report form available at http://titleix.sfsu.edu, emailing equityprograms@sfsu.edu or calling 338-2032.
To disclose any such violence confidentially, contact:
· The SAFE Place - (415) 338-2208; http://www.sfsu.edu/~safe_plc/
· Counseling and Psychological Services Center - (415) 338-2208; http://psyservs.sfsu.edu/
· For more information on your rights and available resources: http://titleix.sfsu.edu
Kazunori Okada © 2024, All rights are reserved.