COURSE SYLLABUS FALL 2020
DESIGN AND ANALYSIS OF ALGORITHMS
DESIGN AND ANALYSIS OF ALGORITHMS (CSCI 174)
Semester FALL 2020: Computer Science
Design and Analysis of Algorithms California State University, Fresno
Units: 3 Instructor Name: Dr. Matin Pirouz
Time: MoWeFr 10:00AM - 10:50AM Office Location: Science II 246
Location: Synchronous Zoom Meetings E-Mail: mpirouz@csufresno.edu
Website: Office Hours:
https://fresnostate.instructure.com/courses/29722 Mon 11:00AM-12:30PM,
Wed 11:00AM-12:30PM,
or by appointment
Health Screening: Students who come to campus for face-to-face classes will be required to
complete a daily health screening which will include temperature checks. If you have
experienced COVID-19 symptoms and/or have tested positive within the past 10 days; or if you
have had close contact (less than 6 feet for longer than 15 minutes while unmasked) with a
suspected or confirmed COVID-19 patient within the past 14 days; you are not allowed to come
to campus. Please complete the campus online reporting form. A campus official will reply to
provide guidance and information.
Safety Measures: Consistent with the Governor’s order and updated state public-health
guidelines, face masks or cloth face coverings are required to be worn in public spaces on-
campus and during in-person classes to reduce possible exposure to COVID-19 and prevent the
spread of the virus. Physical distancing must be practiced by maintaining 6 feet of distance
between individuals. Good hygiene of hand washing for a minimum of 20 seconds or using hand
sanitizer is required. Please avoid touching your face with unclean hands. Disposable face masks
will be provided to anyone who arrives to campus without one.
Please see university website for the most updated information:
www.fresnostate.edu/coronavirus
As part of your participation in virtual/online instruction, please remember that the same student
conduct rules that are used for in-person classroom instruction also apply for virtual/online
classrooms. Students are prohibited from any unauthorized recording, dissemination, or
publication of any academic presentation, including any online classroom instruction, for any
commercial purpose. In addition, students may not record or use virtual/online instruction in any
manner that would violate copyright law. Students are to use all online/virtual instruction
exclusively for the educational purpose of the online class in which the instruction is being
provided. Students may not re-record any online recordings or post any online recordings on any
other format (e.g. , electronic, video, social media, audio recording, web page, internet, hard paper
copy, etc.) for any purpose without the explicit written permission of the faculty member providing
1
the instruction. Exceptions for disability-related accommodations will be addressed by Student
Disability Services working in conjunction with the student and faculty member.
Course Catalog Description: Prerequisites: Models of computation and measures of complexity,
algorithms for sorting and searching, set representation and manipulation, branch and bound,
integer and polynomial arithmetic, pattern-matching algorithms, parsing algorithm, graph
algorithm, NP-complete problems.
Prerequisites for the course: CSCI 115, CSCI 119
REQUIRED COURSE MATERIALS
Required Textbook: Introduction to Algorithms, by Cormen, Thomas H., Leiserson, Charles E.,
Rivest, Ronald L., Stein, Clifford, Isbn-13: 9780262033848, Publisher: Triliteral, Edition: 309th,
Pub Date: July 31, 2009.
COURSE SPECIFICS
Student Learning Outcomes:
After successful completion of this course, students should be able to:
● Understand complexity classes P/NP and their classic problems.
● Understand key algorithm design methods Divide-and-Conquer, Greedy, Dynamic
Programming w/ classic problems and analysis.
● Understand key analysis techniques of Recurrences, Probabilistic Analysis, Amortized
Analysis.
● Understand Trees & Graphs together w/ key algorithms & classic problems.
o Maximum Flow
o Minimum-Spanning Trees
o Understand advanced algorithms.
Grade Distribution:
Activities Percentage
Class Engagement and Quizzes 15%
Assignments 20%
Class Teach Back Presentation 15%
Term Project 30%
Final Exam 20%
Letter Grade Scales:
Percentage Letter Grade
88% - 100% A
2
76% - 87.9% B
64% - 75.9% C
52% - 63.9% D
<= 51.9% F
Exams: There will be a final exam and the final will be comprehensive and covers all materials
coverd.
Grading policy: The penalty for late assignments and projects will be calculated using 10×n
percent, where n is the number of days past the deadline. Authorized student absences are provided
make-up work if the following hold true: a) evidence is provided to the instructor prior to the
deadline; b) there is not an unreasonable number of authorized absences during the semester; and
c) make-up work can be accomplished without substantial additional cost in time or resources to
the academic department or the instructor. It must be recognized that not all learning activities and
exercises during class times and laboratory periods can be replicated in such cases, students are at
risk when they are absent.
COURSE POLICIES
Canvas:
● Check Canvas at least every other day for new announcements and assignments.
● The syllabus and course materials (except for quizzes and exams) will be posted on Canvas.
● Students are strongly encouraged to get email reminders from Canvas.
● Course grades will be uploaded to Canvas.
Quizzes:
● Unannounced quizzes may be held throughout the course.
● Quizzes are closed book, closed notes.
● You may expect up to 8 quizzes.
● Quizzes and class discussions will be based on assigned course readings and will be
supplemented with lecture slides and class notes.
Assignments:
● Assignments are due the midnight before the due date.
● The penalty for late assignments and projects will be calculated using 10×n percent, where n
is the number of days past the deadline.
● Students are expected to work independently. Offering and accepting solutions from others is
an act of plagiarism, which is a serious offense and all involved parties will be penalized
according to the Academic Honesty Policy. Discussion among students is encouraged, but
when in doubt, direct your questions to the instructor.
● The instructor may use automatic plagiarism detection services which may maintain a copy of
the submitted materials in their database. Let the instructor know in advance if you wish to opt
out.
● Assignments submissions are online, and you should use the template for all assignments.
● Show all the intermediate steps for possible credit.
3
● By submitting the assignments, students testify that they have neither given nor received
unauthorized assistance on the work.
Exam Policy:
● Exams are closed book, closed notes (no electronic devices are allowed).
● There will be no make-up for exams unless written proof of extraneous circumstances is
demonstrated in advance to the instructor's satisfaction.
● Cheating during the exam will not be tolerated.
● Final exam is comprehensive.
Attendance:
● Students are expected to attend, and be on time, for every class. Missing a class can impact
your performance as lectures are interdependent and students may experience an impact on
their grade by missing classroom activities and/or quizzes.
● Students are responsible for all missed work, regardless of the reason for absence. It is also the
absentee's responsibility to get all missing notes and materials.
● Students are expected to demonstrate professionalism and courtesy by either silencing or
turning off all cell phones and/or other alarm or audible indicator devices. Use of computers
and smart-phones are prohibited in classroom (unless taking notes).
● Taking photos, videos and/or voice recording during the lecture is not allowed. Such
accommodations need to be with written approval of the instructor.
● If you are absent, it is your responsibility to check on announcements made while you were
away.
● There might be times throughout the semester that the instructor is not available and will
provide you with the lectures or reading materials. You may be tested (as a pop quiz) on the
posted material next time we meet in class.
Class Engagement Rubric:
Excellent Very good Fair Unacceptable
(88%-100%) (76% - 87.9%) (52% - 75.9%) (0% - 51.9%)
Class Attendance Student Student Student Student rarely
(refer to the section attends all frequently sometimes attends lectures
attendance above) lectures attends lectures attends lectures
Student Student Student rarely Student never
regularly sometimes initiates initiates
In-class questions, initiates initiates contributions contributions
answers, and contributions contributions with relevant with relevant
comments with relevant with relevant questions and questions and
questions and questions and answers answers
answers answers
Student Student usually Student mostly Student rarely
Listening always listens listens listens listens
attentively attentively attentively attentively
4
Project: You will be given a project in which you may be expected to work in teams of 6 (or 7
with prior approval) students. You will need to present the project and submit a project report at
the end of the semester. The term project should include report, pseudocode, presentation, and
commented/organized code. Details will be provided throughout the semester. Outstanding
projects may be selected for publication and/or presentation at local, regional, national, or
international symposia. Submission of part and/or all of the class term project from/to other courses
is considered academic misconduct.
Plagiarism Detection: The campus subscribes to Turnitin and the SafeAssign plagiarism
prevention service, and you will need to submit written assignments to Turnitin/SafeAssign.
Student work will be used for plagiarism detection and for no other purpose. The student may
indicate in writing to the instructor that he/she refuses to participate in the plagiarism detection
process, in which case the instructor can use other electronic means to verify the originality of
their work. Turnitin/SafeAssign Originality Reports will not be available for your viewing.
Adding and Dropping Classes: Students are responsible for understanding the policies and
procedures about the adding/dropping of classes, academic renewals, etc. Students can find more
information on adding and dropping at
http://www.fresnostate.edu/studentaffairs/classschedule/registration/add-drop.html
Study Expectations: It is usually expected that students will spend approximately 2-3 hours of
study time outside of class for every one hour in class. Since this is a 4-unit class, you should
expect to study an average of 8-12 hours outside of class each week. Some students may need
more outside study time.
Emergency Procedures: In the event of an evacuation of the classroom, either due to Fire Alarm
or communication by responsible party, all equipment is to be turned off or students should follow
instructor to designate outside area. Do not use elevators, use stairs instead.
Audio/Video Recording: Audio and video recordings of class lectures are prohibited unless you
are given written permission from the instructor. Students with an official letter from the Services
for Students with Disabilities office may record the class if SSD has approved that service. Any
permissible recording shall not be distributed to others without the written permission of the
instructor. The instructor reserves the right to record and post to YouTube all class functions
(lectures, review sessions, office hours), including audio and video from the tablet screen.
If there are questions or concerns that you have about this course that you and I are not able to
resolve, please feel free to contact the Chair of the department to discuss the matter
Chair's name: Dr. Shih-Hsi "Alex" Liu, PhD
Department name: Computer Science
Chair's email: shliu@mail.fresnostate.edu
Department phone number: 559.278.4373
5
UNIVERSITY POLICIES
Students with Disabilities: Upon identifying themselves to the instructor and the university,
students with disabilities will receive reasonable accommodation for learning and evaluation. For
more information, contact Services to Students with Disabilities in the Henry Madden Library,
Room 1202 (278-2811).
The Following University polices can be found at:
● Adding and Dropping Classes
● Cheating and Plagiarism
● Computers
● Copyright Policy
● Disruptive Classroom Behavior
● Honor Code
● Students with Disabilities
● Title IX
UNIVERSITY SERVICES
The following University services can be found at:
● Associated Students, Inc.
● Dream Success Center
● Learning Center Information
● Student Health and Counseling Center
● Writing Center
COURSE CALENDAR:
Date Topic Reading Assignment
1 Wed., Aug 19 Introduction and Course Overview Review Materials from CSCI115
2 Fri., Aug 21 Review Quiz
3 Mon., Aug 24 The Role of Algorithms in Computing Chapter 1,2
4 Wed., Aug 26 Insertion vs. Merge Sort
5 Fri., Aug 28 Analyzing & Designing algorithms
6 Mon., Aug 31 Chapter 3
Asymptotic Analysis
7 Wed., Sept 2
6
Date Topic Reading Assignment
Standard Notations and Common
8 Fri., Sept 4
Functions
Mon., Sept 7 Chapter 4
HOLIDAY – Labor Day
9 Wed., Sept 9 The Maximum-Subarray Problem
10 Fri., Sept 11 Strassen’s Algorithm
11 Mon., Sept 14 Chapter 4
The Substitution Method, the Recursion-
tree Method, the Master Method for
12 Wed., Sept 16
Solving Recurrences
13 Fri., Sept 18 Proof of the Master Theorem
14 Mon., Sept 21 The Hiring Problem
15 Wed., Sept 23 Indicator Random Variables Chapter 5
16 Fri., Sept 25 Randomized Algorithms
17 Mon., Sept 28
Heapsort vs. Quicksort
18 Wed., Sept 30 Chapter 6,7,8
Sorting in Linear Time
19 Fri., Oct 2
20 Mon., Oct 5
21 Wed., Oct 7 Dynamic Programming Chapter 15
22 Fri., Oct 9
23 Mon., Oct 12 An Activity-Selection Problem
24 Wed., Oct 14 Elements of the Greedy Strategy Chapter 16
25 Fri., Oct 16 Huffman Codes
26 Mon., Oct 19
27 Wed., Oct 21 Amortized Analysis Chapter 17
28 Fri., Oct 23
29 Mon., Oct 26 Representations of Graphs
30 Wed., Oct 28 Breadth-First vs. Depth-First Search Chapter 22
31 Fri., Oct 30 Topological Sort
7
Date Topic Reading Assignment
32 Mon., Nov 2
Growing a Minimum Spanning Tree
33 Wed., Nov 4 Chapter 23
Kruskal and Prim
34 Fri., Nov 6
35 Mon., Nov 9 Bellman-Ford vs. Dijkstra’s Algorithm
Single-Source Shortest Paths in Directed
Wed., Nov 11 Acyclic Graphs Chapter 24
Difference Constraints and Shortest Paths
36 Fri., Nov 13 Proofs of Shortest-Paths Properties
HOLIDAY – Veterans Day
37 Mon., Nov 16 Shortest Paths and Matrix Multiplication
38 Wed., Nov 18 Floyd-Warshall Algorithm Chapter 25
39 Fri., Nov 20 Johnson’s Algorithm for Sparse Graphs
40 Mon., Nov 23 Flow Networks
Wed., Nov 25 Thanksgiving Break Chapter 26
Fri., Nov 27 Thanksgiving Break
41 Mon., Nov 30 Polynomial Time
42 Wed., Dec 2 Polynomial-time Verification Chapter 34
43 Fri., Dec 4 NP-Completeness and Reducibility
44 Mon., Dec 7 Project Presentation
45 Wed., Dec 9 Class Review
Finals week Days Dates
Final Exam Preparation & Faculty Consultation Days: Thursday and Friday Dec 10 – 11
Final Semester Examinations Monday – Thursday Dec 14 – 17
Final Exam
THIS SYLLABUS AND SCHEDULE ARE SUBJECT TO CHANGE IN THE EVENT OF
EXTENUATING CIRCUMSTANCES. THE INSTRUCTOR RESERVES THE RIGHT TO
ADD TO, AND/OR MODIFY ANY OF THE ABOVE POLICIES AS NEEDED TO
MAINTAIN AN APPROPRIATE AND EFFECTIVE EDUCATIONAL ATMOSPHERE IN
THE CLASSROOM AND THE LABORATORY. IN THE CASE THAT THIS OCCURS,
ALL STUDENTS WILL BE NOTIFIED IN ADVANCE OF IMPLEMENTATION OF THE
NEW AND/OR MODIFIED POLICY.
