Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS344: Design and Analysis of Algorithms

Fall 2021 (Asynchronous Remote)

1. Course Description:

In this course we distinguish between an abstract data type (such as a list, stack, queue, tree, or hash table) and a data structure that represents how the abstract data type is represented and stored in the computer's memory. We learn about algorithms for manipulating information in a variety of fundamental abstract data types and data structures.

Information tasks such as searching, retrieving, inserting, updating, sorting and deleting arise frequently in Computer Science problems that are central to many computer applications. We focus on algorithms to correctly and efficiently accomplish these types of core tasks.

What do we mean by "efficiently?" We measure efficiency in terms of speed and space (storage) usage. We use techniques from theoretical computer science and discrete mathematics for our analyses.

Why does efficiency matter in computing environments in which processors are very fast and storage space is abundant? Here are two reasons that have significant practical impact: 1) The amount of information continues to explode quickly, and for large amounts of information the differences in speed and storage requirements across different algorithm/data structure combinations can be huge; 2) Some types of problems are inherently difficult and we cannot expect to solve them as efficiently as we can solve easier ones. It is important to learn to recognize such problems and be familiar with ways to tackle them.

The algorithms we study represent a variety of important Computer Science problem-solving strategies, or algorithmic paradigms. We examine major characteristics of several algorithmic paradigms.

2. Topics

Algorithms, Data Structures, Time and Space Complexity Analysis

3. Prerequisites

112: Data Structures; 206: Introduction to Discrete Structures II

4. Learning Goals

Upon finishing this course, the students should be able to:

● Analyze the computational complexity of basic algorithms;

● Be familiar with frequently used data structures, such as tree, list, queue, stacks;

● Be familiar with frequently used algorithms, such as sorting, searching, and selection;

● Design appropriate data structures and algorithms for programming tasks;

Computer Science major:

● will be prepared to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and foundations of computer science (e.g., techniques of program design, creation, and testing; key aspects of computer hardware; algorithmic principles).

● will acquire a deeper understanding on (elective) topics of more specialized interest, and be able to critically review, assess, and communicate current developments in the field.

● will be prepared for the next step in their careers, for example, by having done a research project (for those headed to graduate school), a programming project (for those going into the software industry), or some sort of business plan (for those going into startups).

5. Textbooks and Readings

Textbook: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition, MIT Press. ISBN 978-0-262-03384-8 (hardcover: alk. paper). ISBN 978-0-262-53305-8 (pbk. : alk. paper)

6. Grading

● Four homework assignments (40%)

● Midterm exam (30%)

● Final exam (30%)

The final grade depends on the percentage of points you have earned, and the definition of letter grades is:

● A               90 – 100

● B+             80 – 89

● B               70 – 79

● C+             60 – 69

● C               50 – 59

● F               < 50.3.

7. Tentative Schedule

Class happens on a week-to-week schedule. On the Monday of each week, the video recording, slides, and class notes for that week will be uploaded to Canvas. Students are expected to complete videos and slides before Tuesday/Thursday meetings of that week. Students would then join the interactive office hours on Tuesday/Thursday for Q&A (not required, but highly encouraged). Based on your learning schedule, students can choose one of the two office hours on the first page of the syllabus.

Class #	The week of	Topics	Readings	Note
1	9/6	Algorithmic Analysis, big-O notation	Ch 1, 2, 3
2	9/13	Divide and Conquer	Ch 4, 9
3	9/20	Sorting Algorithms	Ch 8.1, 8.2	Assignment 1
4	9/27	Binary Search Trees, Red-Black Trees	Ch 12, 13
5	10/4	Randomized Algorithms I	Ch 5, 7
6	10/11	Randomized Algorithms II	Ch 11	Assignment 2
7	10/18	Graph Algorithms I	Ch 22, 24.1, 24.3
8	10/25	Graph Algorithms II	Ch 22.5
Midterm	10/25-29			Midterm exam
9	11/1	Greedy Algorithms I	Ch 16.1, 16.2, 16.3
10	11/8	Greedy Algorithms II	Ch 23
11	11/15	Dynamic Programming I
12	11/22	Dynamic Programming II	Ch 15.4
13	11/29	Max-flow, Min-cut, Intractable Problems	Ch 26	Assignment 4
14	12/6	Final review
-	12/14-15		Reading day, QA
Final	12/16-23			Final exam

8. Technology Requirements

To complete the course, students need a laptop, desktop, cellphone, tablet, or other similar devices that can connect to the internet, play videos, and conduct video/audio communications. Please visit the Rutgers Student Tech Guide page for resources available to all students. If you do not have the appropriate technology for financial reasons, please email Dean of Students [email protected] for assistance. If you are facing other financial hardships, please visit the Office of Financial Aid at https://financialaid.rutgers.edu/.

9. Self-Reporting Absence Application

Students are expected to attend all classes; if you expect to miss one or two classes, please use the University absence reporting website https://sims.rutgers.edu/ssra/ to indicate the date and reason for your absence. An email is automatically sent to me.

10. Honor Pledge

The Rutgers honor pledge will be included on all (major) assessments for you to sign: On my honor, I have neither received nor given any unauthorized assistance on this examination (assignment).

11. Academic Integrity

Students are expected to maintain the highest level of academic integrity. You should be familiar with the university policy on academic integrity. Violations will be reported and enforced according to this policy.

Use of external website resources such as Chegg.com or others to obtain solutions to homework assignments, quizzes, or exams is cheating and a violation of the University Academic Integrity policy. Cheating in the course may result in grade penalties, disciplinary sanctions or educational sanctions. Posting homework assignments, or exams, to external sites without the instructor's permission may be a violation of copyright and may constitute the facilitation of dishonesty, which may result in the same penalties as plain cheating.

12. Student-Wellness Services

Counseling, ADAP & Psychiatric Services (CAPS)

(848) 932-7884 / 17 Senior Street, New Brunswick, NJ 08901/ http://health.rutgers.edu/medical-counseling-services/counseling/

CAPS is a University mental health support service that includes counseling, alcohol and other drug assistance, and psychiatric services staffed by a team of professionals within Rutgers Health services to support students’ efforts to succeed at Rutgers University. CAPS offers a variety of services that include: individual therapy, group therapy and workshops, crisis intervention, referral to specialists in the community, and consultation and collaboration with campus partners.

Crisis Intervention: http://health.rutgers.edu/medical-counseling-services/counseling/crisis-intervention/

Report a Concern: http://health.rutgers.edu/do-something-to-help/

Violence Prevention & Victim Assistance (VPVA)

(848) 932-1181 / 3 Bartlett Street, New Brunswick, NJ 08901 / www.vpva.rutgers.edu/

The Office for Violence Prevention and Victim Assistance provides confidential crisis intervention, counseling and advocacy for victims of sexual and relationship violence and stalking to students, staff and faculty. To reach staff during office hours when the university is open or to reach an advocate after hours, call 848-932-1181.

Disability Services

(848) 445-6800 / Lucy Stone Hall, Suite A145, Livingston Campus, 54 Joyce Kilmer Avenue, Piscataway, NJ 08854 / https://ods.rutgers.edu/

Rutgers University welcomes students with disabilities into all of the University's educational programs. In order to receive consideration for reasonable accommodations, a student with a disability must contact the appropriate disability services office at the campus where you are officially enrolled, participate in an intake interview, and provide documentation: https://ods.rutgers.edu/students/documentation-guidelines. If the documentation supports your request for reasonable accommodations, your campus’s disability services office will provide you with a Letter of Accommodations. Please share this letter with your instructors and discuss the accommodations with them as early in your courses as possible. To begin this process, please complete the Registration form on the ODS web site at: https://ods.rutgers.edu/students/registration-form.

13. Rutgers CS Diversity and Inclusion Statement

Rutgers Computer Science Department is committed to creating a consciously anti-racist, inclusive community that welcomes diversity in various dimensions (e.g., race, national origin, gender, sexuality, disability status, class, or religious beliefs). We will not tolerate micro-aggressions and discrimination that creates a hostile atmosphere in the class and/or threatens the well-being of our students. We will continuously strive to create a safe learning environment that allows for the open exchange of ideas while also ensuring equitable opportunities and respect for all of us. Our goal is to maintain an environment where students, staff, and faculty can contribute without the fear of ridicule or intolerant or offensive language. If you witness or experience racism, discrimination micro-aggressions, or other offensive behavior, you are encouraged to bring it to the attention to the undergraduate program director, the graduate program director, or the department chair. You can also report it to the Bias Incident Reporting System http://inclusion.rutgers.edu/report-bias-incident/